many algorithms concerning BSTs are O(h) where h is the height of the BST
as we insert into a BST, there are two extreme cases
best case: items inserted in pre-order such that the tree is perfectly balanced
tree height = log(n) ⇒ search cost = O(log n)
worse case: items inserted in ascending or descending order such that the tree is completely unbalanced (no different from a linked-list)
tree height = n ⇒ search cost = O(n)
weight-balanced BST = for all nodes, we have
abs(number of nodes in left subtree - number of nodes in right subtree) < 2
height-balanced tree = the heights of each left and right node do not differ by more than one, and the left and right subtree are themselves balanced
right rotation
left rotation
performance analysis:
left + right rotations are opposites
insertion at root (splay trees)
randomised BST insertion
partition