What is exactly mean log n height?

Question

I came to know the height of Random-BST/Red-Black trees and some other trees are O(log n).

I wonder, how this can be. Lets say I have a tree like this

The height of the tree is essentially the depth of the tree, which is in this case will be 4 (leaving the parent depth). But how could people say that the height can be represented by O(log n) notion?

I'm very to algorithms, and this point is confusing me a lot. Where I'm missing the point?

Answer 1

In algorithm complexity the variable n typically refers to the total number of items in a collection or involved in some calculation. In this case, n is the total number of nodes in the tree. So, in the picture you posted n=31. If the height of the tree is O(log n) that means that the height of the tree is proportional to the log of n. Since this is a binary tree, you'd use log base 2.

⌊log₂(31)⌋ = 4

Therefore, the height of the tree should be about 4—which is exactly the case in your example.

Answer 2

As I explained in a comment, a binary tree can have multiple cases:

• In the degenerate case, a binary tree is simply a chain, and its height is O(n).
• In the best case (for most search algorithms), a complete binary tree has the property that for any node, the height of the subtrees are the same. In this case the length will be the floor of log(n) (base 2, or base k, for k branches). You can prove this by induction on the size of the tree (structural induction in the constructors)
• In the general case you will have a mix of these, a tree constructed where any node has subtress with possibly different height.