cpppro

Posts Tagged ‘Balanced Trees’

Balanced (AVL) Binary Search Trees

In C Tidbits, Data Structures in C/C++ on December 28, 2007 at 6:55 pm

An AVL (adelson-velskii-landis) tree also known as balanced tree is a binary search tree with a balance condition.
The balance condition is that for every node in the tree, the height of left and right subtrees can differ by at most 1. The condition ensures that the depth of the tree is O(log N).

      9                           9
     / \                         / \
    /   \                       /   \
   /     \                     /     \
  5      15                   5      15
 / \     /                   / \     / \
2   6   /                   2   6   /   \
       13                          13   20
      /                           /
     /                           /
    12                          12

fig1:BST but               fig2:BST and is balanced(AVL) tree
not balanced tree

as the node 15 in fig1 is out of balance because height of left sub tree is 2 and height of right sub tree is 0.
You might be wondering how to compute height, here it is

height(Tree) = MAX(height(left-sub-tree), height(right-sub-tree)) + 1;

for example, height(9) = MAX(height(5), height(15)) + 1;
height(5) = MAX(height(2), height(6)) + 1 = 1;
height(15) = MAX(height(13), -1) + 1 = 2
so, height(5) = MAX(1, 2) + 1 = 3;

Maintaining height information of each node is necessary to check the balancing condition in AVL (balanced) tree.
So, here is the AVL (balanced) tree node representation

struct Tree
{
  Tree * left,
  Tree * right;
  int element;
  int height;
};

Here are the operations which are possible on Balanced (AVL) tree ADT,

1)Make Empty
2)Height
3)Find
4)FindMin
5)FindMax
6)Insert
7)Delete

 

Please referĀ http://www.refcode.net/2013/02/balanced-avl-binary-search-trees.html

 

 

Advertisements