FIT1008 Lecture Notes - Lecture 11: Binary Search Tree, Binary Tree, Bit Array
18 Jun 2018
School
Department
Course
Professor
Binary'tree
="every"node"has"at"most"2"children
Every"subtree"is"itself"a"binary"tree!
Balanced if"every"node"is"such"that:
|"height(left"subtree)"-height(right"subtree)"|"<="1
Perfect if"every"parent"has"2"children,"and"all" leaves"are"same"level
Height/depth
Leaves
="nodes"at"lowest"level
Nodes
="total"number
0
1
1
1
2
3
2
4
7
3
8
15
O(logN)"-if"balanced
O(N)"-if"unbalanced
-
N
Representing"a"node
self.item (entry/item"to"be"stored)
•
self.left (link"to"left"child)
•
self.right (link"to"right"child)
•
Ops:
__init__(self):
self.root = None
○
•
add(self, item, position_bitstring)
[eg.]"add(9, '10')
0"="left
§
1"="right
§
○
Make"bitstring"an"iterator,"then"call"recursive
Recursive"shld"have"args
§
current, item, bitstring_iterator
1.
If"tree"doesn't"exist"yet,
Make"one
i.
2.
Iterate"through"bitstring"to"place"item"in"tree
bit = next(bitstring_iterator)i.
if bit == "0",
current.left = recursive,"with"return"value"being"
current.left
a.
ii.
if bit == "1",
current.right = recursive,"with"return"value"being"
current.right
a.
iii.
3.
Stops"when"iteration"through"bitstring"has"ended
○
•
**"height starts"from"0,"not"1!!
Traversal
="systematic"way"of"writing/processing"all"the"nodes
Methods:
Preorder•
Root Left"subtree Right"subtree
Inorder"--- just"go"STRAIGHT"across!•
Left"subtree Root Right"subtree
Postorder•
Left"subtree Right"subtree Root
Time"complexities"are"all"O(n),"since"each"node"is"visited"exactly"once.
Preorder:"+,"-,"*,"a,"b,"/,"c,"d,"*,"e,"f
Inorder:"a,"*,"b,"-,"c,"/,"d,"+,"e,"*,"f"==>"infix"arithmetic"expression
Postorder:"a,"b,"*,"c,"d,"/,"-,"e,"f,"*,"+
Binary'search'tree
="a"binary"tree"such"that"every"node"entry"has"a"key
All"keys"in"left"subtree"of"a"node"are"smaller"than"the"node's"key•
All"keys"in"right"subtree"of"a"node"are"larger"than"the"node's"key•
Key"can"be"integer/string,"associated"items"not"shown"in"tree•
Deletion:
Predecessor:"right-most"child"of"left"subtree,"or"left"child"itself"(if"no"children)•
Successor:"left-most"child"of"right"subtree,"or"right"child"itself"(if"no"children)•
Afterwards,"child(ren)"of"that"are"moved"up"to"parent"of"original•
Binary'Search'Tree'vs'Hash'Table?
Better:
Uses"more"memory"than"a"relatively"full"hash"table,"since"it"needs"to"keep"two"
references"for"each"item"on"the"structure.
Worse:
If"hash"function"has"a"good"constant,"search"will"far"outperform"the"logarithmic"
time"of"BST."O(1)"instead"of"O(logn).
Week$11:$dictionary$ADTs$-binary$(search)$tree
Friday,"15"June"2018
16:30
Document Summary
Week 11: dictionary adts - binary (search) tree. = every node has at most 2 children. | height(left subtree) - height(right subtree) | <= 1. Perfect if every parent has 2 children, and all leaves are same level. N self. item (entry/item to be stored) self. left (link to left child) self. right (link to right child) Iterate through bitstring to place item in tree. = systematic way of writing/processing all the nodes. Time complexities are all o(n), since each node is visited exactly once. Preorder: +, -, *, a, b, /, c, d, *, e, f. Inorder: a, *, b, -, c, /, d, +, e, *, f ==> infix arithmetic expression. Postorder: a, b, *, c, d, /, -, e, f, *, + = a binary tree such that every node entry has a key. All keys in left subtree of a node are smaller than the node"s key.
