Assume I have a binary search tree, and I managed to prove that its height is upper bounded by $1.44 \log(n)$. Now, can I say with confidence that it is, for sure, an AVL tree? or is this condition not an if and only if?.
$\begingroup$ $\endgroup$
Add a comment |
1 Answer
$\begingroup$ $\endgroup$
If a binary search tree on $n$ nodes is an AVL tree, then its height $h$ is at most about $1.44 \log n$. The converse doesn't hold: Take a large complete binary tree, and add a short path (consisting of three new nodes, say) emanating from one of the leaf nodes. This augmented binary search tree will violate the AVL property at the root node of this path (i.e. at the original leaf node), but the height is still at most $1.44 \log n$.
A complete binary tree is generally shorter than an AVL tree, and so the inequality gap $h-1.44 \log n$ is initially large enough that after adding the path the inequality continued to hold.
