BST Flashcards
binary search tree
EACH VERTEX CAN HAVE UP TO 2 CHILDREN
2 CHILDREN
LEFT - SMALL , RIGHT-LARGER
DUPLICATES ARE STORED AS FREQUENCY - MULTISET
AVL trees are self balancing binary tree with height O(log (n))
Find Successor
- if RIGHT exist, then min in the right subtree
- no RIGTH exist, go to parent and traverse until the the first right turn from searching. Then parent of that right successor. Basically, it gives the first max of V (right turn)
- if MAX in BST, then we go until root and not found. Result is -1
RIGHT (find min) or parent first right’s parent
Find Predecessor
- if left exist, then max in the subtree
- if left not exist, parents’ first left, then parent
- if no left find until ROOT then -1
PRE, IN, POST
PPE- print as we visit FIRST time
IN - print as we visit SECOND time
POST - print as we visit THIRD time
https://www.youtube.com/watch?v=WLvU5EQVZqY
BST element rank
Use IN ORDER to write in sorted order and find the index - starting with 1
Ascending order
In order traversal
Kth-smallest
Use ranking BST
https://www.youtube.com/watch?v=adAQs2FNuFo for later exam study
Static/Dynamic
If no update, insert or delete then static. If there is then dynamic
lower-bound
smallest value that is bigger than the value V to be found
search/lower_bound/searchMin/SearchMax time complexity
O(h)
h- as tall as N for normal BST
Skewed BST
only RIGHT or only LEFT
time complexity: O(N Log(N)) to insertions of N elements and then O(N) for in-order to get sorted
But rarely used
Height is ZERO based
root - 0
in normal BST, O(h) for finding find for others
insertion O(1) as at the leaf
deletion of no child - O(1)
deletion with one child - O(1)
deletion with two child - O(h) for finding successor
skewed BST is nothing but
linked list
Height
Number of edges under the rode to leaf
-max route
AVL lower bound height
log2(N)
AVL two soviet inventors
Georgy Adelson-Velskii
Evgenii Landis
1962
AVL height
< 2 * log(N)
AVL BF - balance factor
number of left edges - number of right edges. And should be in {-1,0,1}
https://www.youtube.com/watch?v=u3OVSkuOdqI
rotations
More on left -> rotate right
More on right -> rotate left
LL -> Left rotation
RR -> Right rotation
LR -> from root left followed by right
so, first child left rotation
then right rotation
RL -> from root right followed by left