FREE C PROGRAMS

Data Structures and C Programming

  DATA STRUCTURES USING C

 HOME PAGE

Data Structures Interview Questions

Pg : 1 , 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14

AVL Tree

An AVL tree is a special type of binary tree that is always partially balanced. The criteria that is used to determine the level of balanced-ness is the difference between the heights of subtrees of a root in the tree. The height of tree is the number of levels in the tree. Or to be more formal, the height of a tree is defined as follows:

  1. The height of a tree with no elements is 0
  2. The height of a tree with 1 element is 1
  3. The height of a tree with > 1 element is equal to 1 + the height of its tallest subtree.
Height of a node
  • The height of a leaf is 1. The height of a null pointer is zero.
  • The height of an internal node is the maximum height of its children plus 1

 

 AVL trees are height-balanced binary search trees

Balance factor of a node

height(left subtree) - height(right subtree)

An AVL tree has balance factor calculated at every node

For every node, heights of left and right subtree can differ by no more than 1

Store current heights in each node

 

Animated AVL Tree

 

http://www.cs.jhu.edu/~goodrich/dsa/trees/avltree.html

 

Notes on AVL Trees

 

http://pages.cs.wisc.edu/~siff/CS367/Notes/AVLs/

 

AVL Tree Rotations Tutorial

 

http://fortheloot.com/public/AVLTreeTutorial.rtf

 

AVL Tree C Program

 

http://www.freecprograms.com/AVL.htm

 

---------------------------------------------------------------------------------------