Studying for an algorithms exam, and I read that the height of every BST is not O(log n). Does this fact have something to do with the tree being balanced? Is the height of every balanced BST O (log n), and unbalanced tree something else (if so what is it)?
2 Answers
The height of every unbalanced BST is not O(lg n)
because imagine a tree with keys in increasing/decreasing order, where the tree becomes skewed to one side. This happens to be the O(n)
worst-case for an unbalanced BST where the height is equal to n
.
On the other hand, with a balanced tree such as an AVL tree, rotations during insertion/deletion allow these trees to maintain an approximate (not perfect) O(lg n)
height.
Yes, it because the tree is unbalanced. Consider what happens when you insert a sorted sequence of numbers into the tree. Each would be a child of the previous number you inserted. The height of the tree would be O(n).
h = Ω(log n)
, I suppose.