Analysis of AVL tree
I am reading on AVL tres in Data structures and analysis by Weiss
One of the balance condition would insist that every node must have left and right subtrees of the same height. If the height of an empty subtree is defined to be -1 (as is usual), then only perfec开发者_如何转开发tly balanced trees of ((2 to power of k) - 1) nodes would satisfy this criterion. Thus, although this guarantees trees of small depth, the balance condition is too rigid to be useful and needs to be relaxed.
Request help in understanding above text by giving an example 1. like how author came with ((2 to power of k) - 1) nodes would satisfy this criteria? 2. What does statement "although this guarantees trees of small depth, the balance condition is too rigid to be useful and needs to be relaxed" mean ?
Thanks!
A perfectly balanced tree, as described here, has the same number of nodes on either side of any node. Trees that can satisfy this have total node counts of:
1: *
3: *
/ \
* *
7: *
/ \
* *
/ \ / \
* * * *
etc
Mathematically, this means the number of nodes in the tree is 2k-1, where k
is an integer.
"Small depth" means trees of this form have the largest possible number of nodes for their given depth: adding one more node must increase the depth.
精彩评论