CODEWITHSUNDEEP
data-structurestreebinary-tree
bysreg
bysreg

Reputation: 803

Definition of balanced binary search tree

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

Upvotes: 2

Views: 1540

Answers (1)

xpda
xpda

Reputation: 15813

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

Upvotes: 1

Related Questions