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

operations ➗

• right rotation

• left rotation

• performance analysis:

left + right rotations are opposites

methods for maintaining balance / improving search time

• insertion at root (splay trees)

• randomised BST insertion

• partition