binary search trees Flashcards
additional properties of BST
nodes can be compared by some value
nodes on the left are less that node
nodes on the right are greater than node - can also define one side as equals
advant and disadvantages of BST
faster search
more work when adding/removing nodes
BST insert algorithm
if root = null –> new node becomes entire tree
value node add new node to RHS
recured until the node gets added as a new leaf node - nodes are only added as new leaf nodes
BST find algorithm
start at root
- if search == root return root
- if searchroot recurse into RHS subtree
delete algorithm
find element to delete - if element is a leaf - just delete - 1 child - replace node with its child - 2 children \+++ find x = min node in RHS subtree \+++ remove x from RHS subtree \+++ replace deleted element with x
how to handle duplicate keys
assume all keys are unique
- issue:
++is it identical items copies or different items with identical identifier keys
options =
++ duplicates in adjacent tree positions - modify all operations to deal with this
++ counter for dupes
++list of items attached to each node
complexity analysis for operations (find insert delete)
best case - O(1)
worst case -O(n)
why is the worst case not O(log n )
the tree could be linear in shape
things to go over and add
- little o notations
- findK
- level order traversals explanations
height
maximum edges from root to leaf
size
number of nodes
level
number of rows h+1
full tree
no single child nodes
complete tree-
has minimum height
all levels have every node except last and last is filled from left to right
balanced tree
nodes are distributed according to some balancing factor
