Binary Search Tree 2-3 Trees Flashcards
what are the two types of nodes in a 2-3 BST
2 nodes (have one key and two children) 3 nodes (have two keys and three children)
for the three children of a three node, which order are they i
the leftmost child is smaller than both the keys
the middle child is in between both the keys
the rightmost child is larger than both of they keys
are 2-3 trees always complete
yes
what does perfect balance mean
that every path from root to null link has the same lenght
how does search method work in a 2-3 BST
compare value being searched for against node
find interval containing search node, follow that link (recursively)
return value if found
how does inserting into a 2-3 tree work
always add a key into an existing node
insert key into the last node we visited when searching for the key
2 node can become a 3 node
how to insert into a 2 node at the bottom of the BST
add a new key, making a 3 node from the 2 node
how to insert into a 3 node at the bottom of the tree
make a temp 4 node
move middle key into parent
repeat up the tree if necessary
if the root is a 4 node, split into 2 nodes (only case where height increases)
where is height of tree grown from
root only
what is the worst case height of a 2-3 bst
lgN
all of the nodes are 2 nodes and it acts the same as a normal BST
worst case input of keys into a normal bst tree which will result in worst case height
insert keys in ascending order
best case height of 2-3 bst
logbase3N
=lg N
all the nodes are 3 nodes
is there a worst case input into a 2-3 bst that will result in wosrt case tree height
no
guaranteed performance of search and insert in a 2-3 BST
logarithmtic
why is a 2-3 BST difficult to implement
all the different ways of splitting nodes
every time a 2 node is encountered, more comparisons are needed
