Definition of balanced binary search tree

2
votes

So, i have been studying about the balanced binary search tree.

I've googled it, and this is what i've found :

Binary tree in which the depth of the two subtrees of every node differ by 1 or less (from wikipedia)

Can't we just define balanced binary tree as a tree that has height no more than ceil(log(n+1) / log 2) ?

And it seems from this answer Is Binary Search tree balanced?, the questioner seems have already asked very much the same thing, but the accepted answer rejects that idea by giving the example of fibonacci tree. Fibonacci tree isnt a balanced tree right ? I think the answerer may be confused with the definition of balanced tree in AVL tree in which, to my understanding, allow certain unbalanced tree

1
data-structurestreebinary-tree
the best case for a BST is log(n) and the worst case is n. the idea of a balanced BST is like what you say the depth of the two subtrees of every node differ by 1 or less. However AVL tree or Red-Black tree are an implementation of the self balancing BST, depending on the algorithm, they won't implement a perfectly balanced tree of log(n) but rather in the order of nlog(n) which is much better than n. – john
are you sure its nlogn(n)? it should be clog(n) right ? because n is actually better than nlog(n) – bysreg
Ah yeah it should have been clog(n) with c < n – john

1 Answers

1
votes

Unless my calculations are wrong, the definition won't work. If you take a full binary tree of height 6, for example, it has 63 nodes. If you remove two siblings at the bottom and their parent, you have 60 nodes. This tree is not balanced, but its height is still equal to ceil(log(n+1) / log 2).