1

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
  • Yes, it has to do with balanced/unbalanced. Imagine a tree where the root is the minimum item, and none of the nodes have left children. Its height would be N (the number of items).
    – ahruss
    Jun 5, 2015 at 2:08
  • You could say that h = Ω(log n), I suppose.
    – Amadan
    Jun 5, 2015 at 2:09

2 Answers 2

5

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.

0

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).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.