Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C++ (http://www.go4expert.com/articles/cpp-tutorials/)
-   -   AVL Binary Tree for C++ (http://www.go4expert.com/articles/avl-binary-tree-cpp-t2951/)

Sanskruti 10Feb2007 19:26

AVL Binary Tree for C++
 

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: CPP

// 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: CPP

// 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: CPP

// 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: CPP

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));
     }
   }


rahul.mca2001 6Mar2008 13:42

Re: AVL Binary Tree for C++
 
i needed this


All times are GMT +5.5. The time now is 14:48.