1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

AVL Binary Tree for C++

Discussion in 'C++' started by Sanskruti, Feb 10, 2007.

  1. Sanskruti

    Sanskruti New Member

    Joined:
    Jan 7, 2007
    Messages:
    108
    Likes Received:
    17
    Trophy Points:
    0
    Occupation:
    Software Consultant
    Location:
    Mumbai, India

    Introduction To Binary Trees



    A binary tree is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element. The "root" pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller "subtrees" on either side. A null pointer represents a binary tree with no elements -- the empty tree. The formal recursive definition is: A binary tree is either empty or is made of a single node, where the left and right pointers each point to a binary tree.

    AVL Trees



    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.

    An AVL tree is a binary tree in which the difference between the height of the right and left subtrees (or the root node) is never more than one.

    The idea behind maintaining the "AVL-ness" of an AVL tree is that whenever we insert or delete an item, if we have "violated" the "AVL-ness" of the tree in anyway, we must then restore it by performing a set of manipulations (called "rotations") on the tree.

    These rotations come in two : single rotations and double rotations .

    Implementing AVL Trees in C++



    Before we begin our AVL tree implementation in C++, lets assume we have a template class named "Compare1" defined as follows:

    Code:
       // cmp_t is an enumeration type indicating the result of a
       // comparison.
       enum  cmp_t {
          MIN_CMP = -1,   // less than
          EQ_CMP  = 0,    // equal to
          MAX_CMP = 1     // greater than
       };
    
       // Class "Compare" corresponds to an arbitrary Compare1 element
       // with a keyfield that has an ordering relation. The template parameter
       // KeyType is the "type" of the keyfield
       
       template <class KeyType>
       class Compare {
       private:
          KeyType  myKey;
       
       public:
          Compare (KeyType  key) : myKey(key) {};
       
          // Use default copy-ctor, assignment, & destructor
       
             // Compare this item against the given key & return the result
          cmp_t Compare(KeyType  key) const;
       
            // Get the key-field of an item
          KeyType Key() const { return  myKey; }
       };
    Like the "Compare1" class, our AVL tree will also be a template class parameterized by a KeyType:
    Code:
       // Class AvlNode represents a node in an AVL tree. The template parameter
       // KeyType is the "type" of the keyfield
       //
       template <class KeyType>
       class AvlNode {
       private:
          Compare1<KeyType> * myData;         // Data field
          AvlNode<KeyType>    * mySubtree[2];   // Subtree pointers
          short                 myBal;          // Balance factor
    
          // ... many details omitted
       };

    Calculating New Balances After a Rotation



    To calculate the new balances after a single left rotation. The left is what the tree looked like BEFORE the rotation and the right is what the tree looks like after the rotation. Capital letters are used to denote single nodes and lowercase letters are used to denote subtrees.

    The "balance" of a tree is the height of its right subtree less the height of its left subtree. Therefore, we can calculate the new balances of "A" and "B" as follows (ht is the height function):

    Code:
      NewBal(A) = ht(b) - ht(a)
    
      OldBal(A) = ht(B) - ht(a)
                = ( 1 + max (ht(b), ht(c)) ) - ht(a)
    subtracting the second equation from the first yields: 
       NewBal(A) - OldBal(A) = ht(b) - ( 1 + max (ht(b), ht(c)) )
                               + ht(a) - ht(a)
    canceling out the ht(a) terms and adding OldBal(A) to both sides yields: 
       NewBal(A) = OldBal(A) - 1 - (max (ht(b), ht(c)) - ht(b) )
    Noting that max(x, y) - z = max(x-z, y-z), we get: 
       NewBal(A) = OldBal(A) - 1 - (max (ht(b) - ht(b), ht(c) - ht(b)) )
    But ht(c) - ht(b) is OldBal(B) so we get: 
       NewBal(A) = OldBal(A) - 1 - (max (0, OldBal(B)) )
                 = OldBal(A) - 1 -  max (0, OldBal(B))
    Thus, for A, we get the equation: 
       NewBal(A) = OldBal(A) - 1 - max (0, OldBal(B))
    
    To calculate the Balance for B we perform a similar computation: 
       NewBal(B) = ht(c) - ht(A)
                 = ht(c) - (1 + max(ht(a), ht(b)) )
    
       OldBal(B) = ht(c) - ht(b)
    
    subtracting the second equation from the first yields: 
       NewBal(B) - OldBal(B) = ht(c) - ht(c)
                               + ht(b) - (1 + max(ht(a), ht(b)) )
    canceling, and adding OldBal(B) to both sides gives: 
       NewBal(B) = OldBal(B) - 1 - (max(ht(a), ht(b)) - ht(b))
                 = OldBal(B) - 1 - (max(ht(a) - ht(b), ht(b) - ht(b))
    But ht(a) - ht(b) is - (ht(b) - ht(a)) = -NewBal(A), so ... 
       NewBal(B) = OldBal(B) - 1 - max( -NewBal(A), 0)
    Using the fact that min(x,y) = -max(-x, -y) we get: 
       NewBal(B) = OldBal(B) - 1 + min( NewBal(A), 0)
    So, for a single left rotation we have shown the the new balances for the nodes A and B are given by the following equations:

    Code:
    NewBal(A) = OldBal(A) - 1 - max(OldBal(B), 0)
    NewBal(B) = OldBal(B) - 1 + min(NewBal(A), 0)
    If we perform the same calculations we will see that the new balances for a single right rotation are given by the following equations:
    Code:
    NewBal(A) = OldBal(A) + 1 - min(OldBal(B), 0)
    NewBal(B) = OldBal(B) + 1 + max(NewBal(A), 0)
    Hence, C++ code for single left and right rotations would be:
    Code:
       // Indices into a subtree array
       enum  dir_t { LEFT = 0, RIGHT = 1 };
    
          // Return the minumum of two numbers
       inline int
       MIN(int a, int b) { return  (a < b) ? a : b; }
       
          // Return the maximum of two numbers
       inline int
       MAX(int a, int b) { return  (a > b) ? a : b; }
    
          // Note that RotateLeft and RotateRight are *static* member
          // functions because otherwise they would have to re-assign
          // to the "this" pointer.
    
       template <class KeyType>
       void
       AvlNode<KeyType>::RotateLeft(AvlNode<KeyType> * & root) {
         AvlNode<KeyType> * oldRoot = root;
    
               // perform rotation
         root = root->mySubtree[RIGHT];
         oldRoot->mySubtree[RIGHT] = root->mySubtree[LEFT];
         root->mySubtree[LEFT] = oldRoot;
    
               // update balances
         oldRoot->myBal -=  (1 + MAX(root->myBal, 0));
         root->myBal    -=  (1 - MIN(oldRoot->myBal, 0));
       }
    
    
       template <class KeyType>
       void
       AvlNode<KeyType>::RotateRight(AvlNode<KeyType> * & root) {
         AvlNode<KeyType> * oldRoot = root;
    
               // perform rotation
         root = root->mySubtree[LEFT];
         oldRoot->mySubtree[LEFT] = root->mySubtree[RIGHT];
         root->mySubtree[RIGHT] = oldRoot;
    
               // update balances
         oldRoot->myBal +=  (1 - MIN(root->myBal, 0));
         root->myBal    +=  (1 + MAX(oldRoot->myBal, 0));
       }
    We can make this code more compact however by using only ONE rotate method which takes an additional parameter: the direction in which to rotate. Notice that I have defined LEFT, and RIGHT to be mnemonic constants to index into an array of subtrees. I can pass the constant LEFT or RIGHT to the rotation method and it can calculate the direction opposite the given direction by subtracting the given direction from the number one.

    It does not matter whether LEFT is 0 or RIGHT is 0 as long as one of them is 0 and the other is 1. If this is the case, then:
    1 - LEFT = RIGHT
    and
    1 - RIGHT = LEFT

    Using this and the same type definitions as before (and the same inline functions), the C++ code for a single rotation becomes:
    Code:
       inline  dir_t
       Opposite(dir_t dir) { return dir_t(1 - int(dir)); }
    
       // RotateOnce -- static member function that performs a single
       //               rotation for the given direction.
       
       template <class KeyType>
       void
       AvlNode<KeyType>::RotateOnce(AvlNode<KeyType> * & root, dir_t  dir) {
         AvlNode<KeyType> * oldRoot  = root;
         dir_t              otherDir = Opposite(dir);
    
               // rotate
         root = tree->mySubtree[otherDir];
         oldRoot->mySubtree[otherDir] = tree->mySubtree[dir];
         root->mySubtree[dir] = oldRoot;
    
               // update balances
         if (dir == LEFT)  {
            oldRoot->myBal -=  (1 + MAX(root->myBal, 0));
            root->myBal    -=  (1 - MIN(oldRoot->myBal, 0));
         } else  /* dir == RIGHT */  {
            oldRoot->myBal +=  (1 - MIN(root->myBal, 0) );
            root->myBal    +=  (1 + MAX(oldRoot->myBal, 0));
         } 
       }
     
  2. rahul.mca2001

    rahul.mca2001 New Member

    Joined:
    Feb 13, 2008
    Messages:
    103
    Likes Received:
    0
    Trophy Points:
    0
    i needed this
     

Share This Page