AVL tree
You are not Member of this Project.
Project Owner : vani.R
Created Date : Thu, 15/03/2012 - 11:35
Project Description :
AVL Trees
10.1 Definitions
Named after Adelson, Velskii, and Landis.
Trees of height O(log n) are said to be balanced. AVL trees consist of a special case in which the subtrees of each node differ by at most 1 in their height.
Balanced trees can be used to search, insert, and delete arbitrary keys in O(log n) time. In contrast, height-biased leftist trees rely on non-balanced trees to speed-up insertions and deletions in priority queues.
10.2 Height
Claim: AVL trees are balanced.
Proof. Let N_{h} denote the number of nodes in an AVL tree of depth h
N_{h} | > N_{h-1} + N_{h-2} + 1 |
> 2N_{h-2} + 1 | |
> 1 + 2(1 + 2N_{h-4}) | |
= 1 + 2 + 2^{2}N_{ h-4} | |
> 1 + 2 + 2^{2} + 2^{3}N_{ h-6} | |
... | |
> 1 + 2 + 2^{2} + 2^{3} + ... + 2^{h/2} | |
= 2^{h/2} - 1 | |
Hence,
2^{h/2} - 1 | < n |
h/2 | < log _{2}(n + 1) |
h | < 2 log _{2}(n + 1) |
A more careful analysis, based on Fibonacci numbers theory, implies the tighter bound of 1.44 log _{2}(n + 2).
You are not authorized to access this content.
You are not authorized to access this content.
You are not authorized to access this content.
You are not authorized to access this content.
You are not authorized to access this content.