Projects

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 Nh denote the number of nodes in an AVL tree of depth h

 

Nh > Nh-1 + Nh-2 + 1
  > 2Nh-2 + 1
  > 1 + 2(1 + 2Nh-4)
  = 1 + 2 + 22N h-4
  > 1 + 2 + 22 + 23N h-6
  ...
  > 1 + 2 + 22 + 23 + ... + 2h/2
  = 2h/2 1
 

Hence,

 

2h/2 1 < n
h/2 < log 2(+ 1)
h < 2 log 2(+ 1)
 

A more careful analysis, based on Fibonacci numbers theory, implies the tighter bound of 1.44 log 2(+ 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.