AVL Trees in C++

AVL tree
Type	tree
Invented	1962
Invented by	Georgy Adelson-Velsky and Evgenii Landis
Time complexity in big O notation
Algorithm Average Worst case Space O(n) O(n) Search O(log n) O(log n) Insert O(log n) O(log n) Delete O(log n) O(log n)

In computer science, an AVL tree is a self-balancing binary search tree. It was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.

The AVL tree is named after its two Soviet inventors, Georgy Adelson-Velsky and Evgenii Landis, who published it in their 1962 paper "An algorithm for the organization of information".

AVL Tree Rotations

The Russian mathematicians Georgy Adelson-Velsky and Evgenii Landis were the first to notice that certain operations can be performed on binary trees without affecting their validity. For example, please consider the following diagram.

The second tree is obtained from the first by rotating the node 7 left and upwards. It is called a left rotation. The things to notice about this transformation are:

• the resultant tree (with 7 at the root) is still in key order and
• the transformation has altered the heights of the left and right subtrees.

There is also a right rotation. Once left and right rotations have been discovered, it is possible to use them to maintain balancing when adding and removing entries from a tree. The type of tree to be considered is constrained in that left and right subtrees of any node are restricted to being at most 1 different in height (both of the trees above satisfy this condition). This type of tree is almost balanced, and is referred to as an AVL tree in honour of the Russian mathematicians mentioned above. It is possible (using rotations) to always satisfy the AVL condition when adding and removing entries from the tree.

Definition of an AVL Set

An AVL set is a binary tree in which the heights of the left and right subtrees of the root differ by at most 1 and in which the left and right subtrees are again AVL sets.

With each node of an AVL set is associated a balance factor that is either left high, equal or right high according to whether the left subtree has height greater than, equal to or less than the height of the right subtree (respectively).

Balance Factor

In addition to the tree states mentioned in the definition above, we include a fourth state indicating that the node is a header node. This precludes having to define a separate boolean in the node.

struct State
 {
  enum
  {
   Header,
   Balanced,
   LeftHigh,
   RightHigh
  };
 };

Incidentally, we define the enum this way so that the notation is compatible with Managed C++ enum classes, C# enums and Java enums.

Properties

Balance factors can be kept up-to-date by knowing the previous balance factors and the change in height – it is not necessary to know the absolute height. For holding the AVL balance information, two bits per node are sufficient.

The height h of an AVL tree with n nodes lies in the interval:

log₂(n+1) ≤ h < c log₂(n+2)+b

with the golden ratio φ := (1+√5) ⁄₂ ≈ 1.618, c := ¹⁄ log₂ φ ≈ 1.44,  and  b := ^c⁄₂ log₂ 5 – 2 ≈ –0.328. This is because an AVL tree of height h contains at least F_h+2 – 1 nodes where {F_h} is the Fibonacci sequence with the seed values F₁ = 1, F₂ = 1.

Direction

When a node is inserted or deleted, it is known whether the left or right node is being inserted or deleted. This leads to the following enum for direction.

struct Direction
{
 enum {FromLeft, FromRight};
}

Node Classes

A non-generic base class will be used for nodes. This is so that non-generic balancing and iteration routines can be developed. This precludes code bloat. The above definition leads to the following base class for node and class for a set node.

struct Node  // Base Node Class for all Trees
{
 Node* Left;
 Node* Right;
 Node* Parent;
 char Balance;
 
 Node()
 {
  Balance = State::Header;
  Left    = this;
  Right   = this;
  Parent  = 0;
 }
 
 Node(Node* ParentSet)
 {
  Balance = State::Balanced;
  Left    = 0;
  Right   = 0;
  Parent  = ParentSet;
 }
 
 bool IsHeader() const {return !Balance;}
};

Then set nodes are defined to inherit from the base class node, as shown below.

template<class T>
struct setNode : public Node
{
 T Element;
 
 setNode(const T& ElementSet,
         Node* Parent) : Node(Parent), Element(ElementSet) {}
 
 operator T&() {return Element;}
};

There is a non-generic base class Node. This facilitates non-generic balancing. The header node is an instance of the class Node, whereas all other nodes are instances of the class SetNode<T>. Apart from the references to the left and right subtrees and parent, a node contains a balance factor. The balance factor is one of the values from the above enumeration State. With just the addition of the member (Balance), sets can be balanced (which is quite efficient in terms of node storage).

AVL Utilities

Once these definitions are in place, the utilities that use the base node class only can be defined as follows.

inline void RotateLeft(Node*& Root)
{
 Node* Parent = Root->Parent;
 Node* x = Root->Right;
 
 Root->Parent = x;
 x->Parent = Parent;
 if (x->Left) x->Left->Parent = Root; 
 
 Root->Right = x->Left;
 x->Left = Root;
 Root = x;
}    
 
inline void RotateRight(Node*& Root)
{
 Node* Parent = Root->Parent;
 Node* x = Root->Left;
 
 Root->Parent = x;
 x->Parent = Parent;
 if (x->Right) x->Right->Parent = Root; 
 
 Root->Left = x->Right;
 x->Right = Root;
 Root = x;
} 
 
inline void BalanceLeft(Node*& Root)
{
 Node* Left = Root->Left; // Left Subtree of Root Node
 
 switch (Left->Balance)
  {
   case State::LeftHigh:
    Root->Balance = State::Balanced;
    Left->Balance = State::Balanced;
    RotateRight(Root);
    break;           
 
   case State::RightHigh:
    {
     Node* subRight = Left->Right;  // Right subtree of Left
     switch (subRight->Balance)
      {
       case State::Balanced:
        Root->Balance = State::Balanced;
        Left->Balance = State::Balanced;
        break;
 
       case State::RightHigh:
        Root->Balance = State::Balanced;
        Left->Balance = State::LeftHigh;
        break;
 
       case State::LeftHigh:
        Root->Balance = State::RightHigh;
        Left->Balance = State::Balanced;
        break;
      }
     subRight->Balance = State::Balanced;
     RotateLeft(Left);
     Root->Left = Left;
     RotateRight(Root);
    }
    break;
 
   case State::Balanced:
    Root->Balance = State::LeftHigh;
    Left->Balance = State::RightHigh;
    RotateRight(Root);
    break;           
  }
} 
 
inline void BalanceRight(Node*& Root)
{
 Node* Right = Root->Right; // Right Subtree of Root Node
 
 switch (Right->Balance)
  {
   case State::RightHigh:
    Root ->Balance = State::Balanced;
    Right->Balance = State::Balanced;
    RotateLeft(Root);
    break;
 
   case State::LeftHigh:
    {
     Node* subLeft = Right->Left; // Left Subtree of Right
     switch (subLeft->Balance)
      {
       case State::Balanced:
        Root ->Balance = State::Balanced;
        Right->Balance = State::Balanced;
        break;
 
       case State::LeftHigh:
        Root ->Balance = State::Balanced;
        Right->Balance = State::RightHigh;
        break;
 
       case State::RightHigh:
        Root ->Balance = State::LeftHigh;
        Right->Balance = State::Balanced;
        break;
      }
     subLeft->Balance = State::Balanced;
     RotateRight(Right);
     Root->Right = Right;
     RotateLeft(Root);
    }
    break;         
 
   case State::Balanced:
    Root ->Balance = State::RightHigh;
    Right->Balance = State::LeftHigh;
    RotateLeft(Root);
    break;           
  }
} 
 
inline void BalanceTree(Node* Root, unsigned long From)
{
  bool Taller = true;
 
  while (Taller)
   {
    Node* Parent = Root->Parent;
    unsigned long NextFrom = (Parent->Left == Root) ? Direction::FromLeft
                                                    : Direction::FromRight;
 
    if (From == Direction::FromLeft)
    {
     switch (Root->Balance)
      {
       case State::LeftHigh:
        if (Parent->IsHeader())
          BalanceLeft(Parent->Parent);
        else if (Parent->Left == Root)
          BalanceLeft(Parent->Left);
        else
          BalanceLeft(Parent->Right);
        Taller = false;
        break;
 
        case State::Balanced:
         Root->Balance = State::LeftHigh;
         Taller = true;
         break;
 
        case State::RightHigh:
         Root->Balance = State::Balanced;
         Taller = false;
         break;
       }
     }
    else
     {
      switch (Root->Balance)
       {
        case State::LeftHigh:
         Root->Balance = State::Balanced;
         Taller = false;
         break;
 
        case State::Balanced:
         Root->Balance = State::RightHigh;
         Taller = true;
         break;
 
        case State::RightHigh:
         if (Parent->IsHeader())
           BalanceRight(Parent->Parent);
         else if (Parent->Left == Root)
           BalanceRight(Parent->Left);
         else
           BalanceRight(Parent->Right);
         Taller = false;
         break;
        }
      }
 
      if (Taller) // skip up a level
      {
       if (Parent->IsHeader())
        Taller = false;
       else
       {
        Root = Parent;
        From = NextFrom;
       }
     }
   }
 }
 
 
inline void BalanceTreeRemove(Node* Root, unsigned long From)
{
  if (Root->IsHeader()) return;
  bool Shorter = true;
 
  while (Shorter)
   {
    Node* Parent = Root->Parent;
    unsigned long NextFrom = (Parent->Left == Root) ? Direction::FromLeft
                                                    : Direction::FromRight;
 
    if (From == Direction::FromLeft)
     {
      switch (Root->Balance)
       {
        case State::LeftHigh:
         Root->Balance = State::Balanced;
         Shorter = true;
         break;
 
        case State::Balanced:
         Root->Balance = State::RightHigh;
         Shorter = false;
         break;
 
        case State::RightHigh:
         if (Root->Right->Balance == State::Balanced)
          Shorter = false;
         else
          Shorter = true;
        if (Parent->IsHeader())
         BalanceRight(Parent->Parent);
        else if (Parent->Left == Root)
         BalanceRight(Parent->Left);
        else
         BalanceRight(Parent->Right);
        break;
       }
    }
   else
    {
     switch (Root->Balance)
      {
       case State::RightHigh:
        Root->Balance = State::Balanced;
        Shorter = true;
        break;
 
       case State::Balanced:
        Root->Balance = State::LeftHigh;
        Shorter = false;
        break;
 
       case State::LeftHigh:
        if (Root->Left->Balance == State::Balanced)
         Shorter = false;
        else
         Shorter = true;
        if (Parent->IsHeader())
          BalanceLeft(Parent->Parent);
        else if (Parent->Left == Root)
          BalanceLeft(Parent->Left);
        else
          BalanceLeft(Parent->Right);
        break;
       }
     }
 
     if (Shorter)
      {
       if (Parent->IsHeader())
        Shorter = false;
       else
        {
         From = NextFrom;
         Root = Parent;
        }
      }
   }
}
 
Node* PreviousItem(Node* node)
{
 if (node->IsHeader()) {return node->Right;}
 
 else if (node->Left != 0)
  {
   Node* y = node->Left;
   while (y->Right != 0) y = y->Right;
   node = y;
  }
 else
  {
   Node* y = node->Parent;
   if (y->IsHeader()) return y;
   while (node == y->Left) {node = y; y = y->Parent;}
   node = y;
  }
 return node;
}
 
Node* NextItem(Node* node)
{
 if (node->IsHeader()) return node->Left;
 
 if (node->Right != 0)
  {
   node = node->Right;
   while (node->Left != 0) node = node->Left;
  }
 else
  {
   Node* y = node->Parent;
   if (y->IsHeader()) return y;
   while (node == y->Right) {node = y; y = y->Parent;}
   node = y;
  }
 return node;
}
 
inline Node* Minimum(Node* node)
{
 while (node->Left) node=node->Left;
 return node;
}
 
inline Node* Maximum(Node* node)
{
 while (node->Right) node=node->Right;
 return node;
}
 
void AdjustAdd(Node* Root)
{
 Node* Header = Root->Parent;
 while (!Header->IsHeader()) Header=Header->Parent;
 
 if (Root->Parent->Left == Root)
 {
  BalanceTree(Root->Parent,Direction::FromLeft);
  if (Header->Left == Root->Parent) Header->Left = Root;
 }
 else
 {
  BalanceTree(Root->Parent,Direction::FromRight);
  if (Header->Right == Root->Parent) Header->Right = Root;
 }
}
 
void AdjustRemove(Node* Parent, unsigned long Direction)
{
 BalanceTreeRemove(Parent,Direction);
 
 Node* Header = Parent;
 while (!Header->IsHeader()) Header=Header->Parent;
 
 if (Header->Parent == 0)
 {
  Header->Left = Header;
  Header->Right = Header;
 }
 else
 {
  Header->Left = Minimum(Header->Parent);
  Header->Right = Maximum(Header->Parent);
 }
}
 
unsigned long Depth(const Node* root)
{
 if (root)
  {
   unsigned long left  = root->Left  ? Depth(root->Left)  : 0;
   unsigned long right = root->Right ? Depth(root->Right) : 0;
   return left < right ? right+1 : left+1;
  }
 else
  return 0;
}
 
 
unsigned long Count(const Node* root)
{
 if (root)
  {
   unsigned long left  = root->Left  ? Count(root->Left)  : 0;
   unsigned long right = root->Right ? Count(root->Right) : 0;
   return left + right + 1;
  }
 else
  return 0;
}

inline void SwapNodeReference(Node*& first, Node*& second)
{Node* temporary = first; first = second; second = temporary;}
 
void SwapNodes(Node* A, Node* B)
{
 if (B == A->Left)
  {
   if (B->Left) B->Left->Parent = A;
   if (B->Right) B->Right->Parent = A;
 
   if (A->Right) A->Right->Parent = B;
 
   if (!A->Parent->IsHeader())
    {
     if (A->Parent->Left == A)
      A->Parent->Left = B;
     else
      A->Parent->Right = B;
    }
   else A->Parent->Parent = B;
 
   B->Parent = A->Parent;
   A->Parent = B;
 
   A->Left = B->Left;
   B->Left = A;
 
   SwapNodeReference(A->Right,B->Right);
  }
 else if (B == A->Right)
  {
   if (B->Right) B->Right->Parent = A;
   if (B->Left) B->Left->Parent = A;
 
   if (A->Left) A->Left->Parent = B;
 
   if (!A->Parent->IsHeader())
    {
     if (A->Parent->Left == A)
      A->Parent->Left = B;
     else
      A->Parent->Right = B;
    }
   else A->Parent->Parent = B;
 
   B->Parent = A->Parent;
   A->Parent = B;
 
   A->Right = B->Right;
   B->Right = A;
 
   SwapNodeReference(A->Left,B->Left);
  }
 else if (A == B->Left)
  {
   if (A->Left) A->Left->Parent = B;
   if (A->Right) A->Right->Parent = B;
 
   if (B->Right) B->Right->Parent = A;
 
   if (!B->Parent->IsHeader())
    {
     if (B->Parent->Left == B)
      B->Parent->Left = A;
     else
      B->Parent->Right = A;
    }
   else B->Parent->Parent = A;
 
   A->Parent = B->Parent;
   B->Parent = A;
 
   B->Left = A->Left;
   A->Left = B;
 
   SwapNodeReference(A->Right,B->Right);
  }
 else if (A == B->Right)
  {
   if (A->Right) A->Right->Parent = B;
   if (A->Left) A->Left->Parent = B;
 
   if (B->Left) B->Left->Parent = A;
 
   if (!B->Parent->IsHeader())
    {
     if (B->Parent->Left == B)
      B->Parent->Left = A;
     else
      B->Parent->Right = A;
    }
   else B->Parent->Parent = A;
 
   A->Parent = B->Parent;
   B->Parent = A;
 
   B->Right = A->Right;
   A->Right = B;
 
   SwapNodeReference(A->Left,B->Left);
  }
 else
  {
   if (A->Parent == B->Parent)
    SwapNodeReference(A->Parent->Left,A->Parent->Right);
   else
    { 
     if (!A->Parent->IsHeader())
      {
       if (A->Parent->Left == A)
        A->Parent->Left = B;
       else
        A->Parent->Right = B;
      }
     else A->Parent->Parent = B;
 
     if (!B->Parent->IsHeader())
      {
       if (B->Parent->Left == B)
        B->Parent->Left = A;
       else
        B->Parent->Right = A;
      }
     else B->Parent->Parent = A;
    }
 
   if (B->Left)  B->Left->Parent = A;
   if (B->Right) B->Right->Parent = A;
 
   if (A->Left)  A->Left->Parent = B;
   if (A->Right) A->Right->Parent = B;
 
   SwapNodeReference(A->Left,B->Left);
   SwapNodeReference(A->Right,B->Right);
   SwapNodeReference(A->Parent,B->Parent);
  }
 
 unsigned long Balance = A->Balance;
 A->Balance = B->Balance;
 B->Balance=(char)Balance;
}

Explanation of Balancing

In BalanceSet, if the direction is from the left, left set balancing is instigated. If the direction is from the right, right set balancing is performed. This algorithm progresses up the parent chain of the set until the set is balanced. Certain cases can be taken care of immediately. For example, when inserting into the right subtree (FromRight), if the current node is left high, the balance factor is immediately set to State.Balanced and the job is done. Yet other cases require the set to be restructured. Ancilliary procedures BalanceLeft and BalanceRight have been created for this job. They restructure the set as required.

In BalanceLeft and BalanceRight, reference rotations are performed based upon the cases of the insertion. The procedures BalanceLeft and BalanceRight are symmetric under left/right reflection.

In the procedure BalanceSet, the case (with FromRight) where a new node has been inserted into the taller subtree of the root and its height has increased will now be considered. Under such conditions, one subtree has a height of 2 more than the other so that the set no longer satisfies the AVL condition. Part of the set must be rebuilt to restore its balance. To be specific, assume the node was inserted into the right subtree, its height has increased and originally it was right high. That is, the case where BalanceRight is called from BalanceSet will be covered. Let the root of the set be r and let x be the root of the right subtree. There are three cases to be considered depending upon the balance factor of x.

Case1: Right High

The first case (in BalanceRight) is illustrated in the diagram below.

The required action is a left rotation. In the diagram, the node x is rotated upward and r is made the left subtree of x. The left subtree T2 of x becomes the right subtree of r. A left rotation is described in the appropriate C# function (see rotateLeft). Note that when done in the appropriate order, the steps constitute a rotation of three reference values. After the rotation, the height of the rotated set has decreased by 1 whereas it had previously increased because of the insertion, thus the height finishes where it began.

Case2: Left High

The second case is when the balance factor of x is left high. This case is more complicated. It is required to move two levels to the node w that is the root of the left subtree of x to find the new root. This process is called a double rotation because the transformation can be obtained in two steps (see diagram below). First, x is rotated to the right (so that w becomes its root) and then the set with root r is rotated to the left (moving w up to become the new root).

The code for BalanceRight (and BalanceLeft) should now be carefully considered with the above diagrams in mind.

Case3: Equal Height

It would appear that a third case must be considered. The case where the two subtrees of x have equal heights, but this case can never happen. To see why, recall that a new node has just been inserted into the subtree rooted at x and this subtree has height 2 more than the left subtree of the root. The new node was placed into either the left or right subtree of x. Its placement only increased the height of one subtree of x. If those subtrees had equal heights after the insertion then the height of the full subtree rooted at x was not changed by the insertion - contrary to the hypothesis. While the case of equal height does not occur for insertions, it does occur for deletions, hence it has been coded in the algorithms.

Set Iterators

Because sets will be defined to be enumerable, it is required to define a set enumerator. That definition is shown below.

template <class T>
class setIterator
{
 public:
 
  Node* _node; 
 
  setIterator() : _node(0) {}
 
  setIterator(Node* in) : _node(in) {}
 
  setIterator(const setIterator<T>& i) : _node(i._node) {}
 
  T& operator*() const
  {
   return ((setNode<T>*)_node)->Element;
  }
 
  T* operator->() const
  {
   return &((setNode<T>*)_node)->Element;
  }
 
  T* operator&() const
  {
   return &((setNode<T>*)_node)->Element;
  }
 
  setIterator<T>& operator++()
  {_node = NextItem(_node); return *this;}
 
  setIterator<T> operator++(int)
  {setIterator<T> save = *this; ++*this ;return save;}
 
  setIterator<T>& operator+=(unsigned long increment)
  {for (unsigned long i=0; i<increment; i++) ++*this; return *this;}
 
  setIterator<T> operator+(unsigned long increment) const
  {
   setIterator<T> result(*this);
   for (unsigned long i=0; i<increment; i++) ++result;
   return result;
  }
 
  setIterator<T>& operator--()
  {_node = PreviousItem(_node); return *this;}
 
  setIterator<T> operator--(int)
  {setIterator<T> save = *this; --*this ;return save;}
 
  setIterator<T>& operator-=(unsigned long decrement)
  {for (unsigned long i=0; i<decrement; i++) --*this; return *this;}
 
  setIterator<T> operator-(unsigned long decrement) const
  {
   setIterator<T> result(*this);
   for (unsigned long i=0; i<decrement; i++) --result;
   return result;
  }
 
  bool operator==(const setIterator<T>& y) const {return _node == y._node;}
 
  bool operator!=(const setIterator<T>& y) const {return _node != y._node;}
 
  const T& operator[](long i) const {return i>=0 ? *(*this + i) : *(*this - -i);}  
 
  long operator-(setIterator<T> iter) const
  {
   long result=0;
   while (iter++ != *this) {result++;}
   return result;
  }
 
  bool IsHeader() const {return _node->IsHeader();}
};
 
template <class T>
class constSetIterator
{
 public:
 
  const Node* _node; 
 
  constSetIterator() : _node(0) {}
 
  constSetIterator(const Node* in) : _node(in) {}
 
  constSetIterator(const constSetIterator<T>& i) : _node(i._node) {}
 
  constSetIterator(const setIterator<T>& i) : _node(i._node) {}
 
  const T& operator*() const
  {
   return ((setNode<T>*)_node)->Element;
  }
 
  const T* operator->() const
  {
   return &((setNode<T>*)_node)->Element;
  }
 
  const T* operator&() const
  {
   return &((setNode<T>*)_node)->Element;
  }
 
  constSetIterator<T>& operator++()
  {_node = NextItem((Node*)_node); return *this;}
 
  constSetIterator<T> operator++(int)
  {constSetIterator<T> save = *this; ++*this ;return save;}
 
  constSetIterator<T>& operator+=(unsigned long increment)
  {for (unsigned long i=0; i<increment; i++) ++*this; return *this;}
 
  constSetIterator<T> operator+(unsigned long increment) const
  {
   constSetIterator<T> result(*this);
   for (unsigned long i=0; i<increment; i++) ++result;
   return result;
  }
 
  constSetIterator<T>& operator--()
  {_node = PreviousItem((Node*)_node); return *this;}
 
  constSetIterator<T> operator--(int)
  {setIterator save = *this; --*this ;return save;}
 
  constSetIterator<T>& operator-=(unsigned long decrement)
  {for (unsigned long i=0; i<decrement; i++) --*this; return *this;}
 
  constSetIterator<T> operator-(unsigned long decrement) const
  {
   constSetIterator<T> result(*this);
   for (unsigned long i=0; i<decrement; i++) --result;
   return result;
  }
 
  bool operator==(const constSetIterator<T>& y) const {return _node == y._node;}
 
  bool operator!=(const constSetIterator<T>& y) const {return _node != y._node;}
 
  const T& operator[](long i) const {return i>=0 ? *(*this + i) : *(*this - -i);}  
 
  long operator-(constSetIterator<T> iter) const
  {
   long result=0;
   while (iter++ != *this) {result++;}
   return result;
  }
 
  bool IsHeader() const {return _node->IsHeader;}
};

Set Operations

Several set operations will be defined. These are enumerated as follows.

struct setOperation
{
 enum
 {
  Union,
  Intersection,
  SymmetricDifference,
  Difference,
 };
};

Exceptions

The following are exception classes need to be defined.

class treeException
{
  public:
 
   treeException() {}
};
 
 class EntryAlreadyExistsException : public treeException
 {
  public:
    EntryAlreadyExistsException() {}
 };
 
 class EntryNotFoundException : public treeException
 {
  public:
    EntryNotFoundException()  {}
 };
 
 class InvalidSetOperationException : public treeException
 {
  public:
    InvalidSetOperationException() {}
 };
 
 class IsHeaderException : public treeException
 {
  public:
    IsHeaderException() {}
 };

Comparator Function Template

The following function template helps to offload comparison to the less than operator.

template <class U, class V>
inline int compare(const U& u, const V& v)
{if (u < v) return -1; else if (v < u) return 1; else return 0;}

The Set Class

After all the machinery is in place, the class Set can now be defined.

template <class T>
class set
{
 public:
 
  typedef int (*keyCompare)(const T&,const T&);
 
 protected:
 
  Node Header;
  keyCompare Compare;
 
 public:
 
  // *** iterators ***
 
  typedef setIterator<T> iterator;
 
  typedef constSetIterator<T> const_iterator;
 
  // *** constructors, destructor, operators ***
 
  set(keyCompare C=compare) : Compare(C) {}
 
  set(const set<T>& copy) : Compare(copy.Compare)
  {
   Copy((setNode<T>*)copy.Header.Parent);
  }
 
  set(const set& A, const set& B, unsigned long operation)
  {
   Compare = A.Compare;
 
   const_iterator first1 = A.begin();
   const_iterator last1  = A.end();
   const_iterator first2 = B.begin();
   const_iterator last2  = B.end();
 
   switch (operation)
    {
     case setOperation::Union:
      {
       while (first1 != last1 && first2 != last2)
        {
         int order = Compare(*first1,*first2);
 
         if (order < 0)
          {
           insert(*first1);
           ++first1;
          }
 
         else if (order > 0)
          {
           insert(*first2);
           ++first2;
          }
 
         else
          {
           insert(*first1);
           ++first1; ++first2;
          }
        }
 
       while (first1 != last1)
        {
         insert(*first1);
         first1++;
        }
 
       while (first2 != last2)
        {
         insert(*first2);
         first2++;
        }
      }
     break;
 
     case setOperation::Intersection:
      {
       while (first1 != last1 && first2 != last2)
        {
         int order = Compare(*first1,*first2);
 
         if (order < 0)
          ++first1;
 
         else if (order > 0)
          ++first2;
 
         else
          {
           insert(*first1);
           ++first1; ++first2;
          }
        }
      }
     break;
 
     case setOperation::SymmetricDifference:
      {
       while (first1 != last1 && first2 != last2)
        {
         int order = Compare(*first1,*first2);
 
         if (order < 0)
          {
           insert(*first1);
           ++first1;
          }
 
         else if (order > 0)
          {
           insert(*first2);
           ++first2;
          }
 
         else
          {++first1; ++first2;}
        }
 
       while (first1 != last1)
        {
         insert(*first1);
         ++first1;
        }
 
       while (first2 != last2)
        {
         insert(*first2);
         ++first2;
        }
      }
      break;
 
     case setOperation::Difference:
      {
       while (first1 != last1 && first2 != last2)
        {
         int order = Compare(*first1,*first2);
 
         if (order < 0)
          {
           insert(*first1);
           ++first1;
          }
 
         else if (order > 0)
          {
           insert(*first1);
           ++first1; ++first2;
          }
 
         else
          {++first1; ++first2;}
        }
 
       while (first1 != last1)
        {
         insert(*first1);
         ++first1;
        }
      }
      break;
 
     default:
      throw InvalidSetOperationException();
    }
  }
 
  template<class I>
  set(I first,I last,keyCompare C=compare)
  {
   Compare = C;
   while (first != last) insert(*first++);
  }
 
  ~set()
  {
   Destroy((setNode<T>*)Header.Parent);
  }
 
  set<T>& operator=(const set<T>& copy)
  {
   erase();
   Compare = copy.Compare;
   Copy((setNode<T>*)copy.Header.Parent);
   return *this;
  }
 
  unsigned long length() const {return Count(Header.Parent);}
 
  operator keyCompare() const {return Compare;}
 
  set<T>& operator<<(const T& Element) {insert(Element); return *this;}
 
  set<T>& operator>>(const T& Element) {erase(Element); return *this;}
 
  // *** methods ***
 
  iterator begin() {return Header.Left;}
 
  iterator end() {return &Header;}
 
  const_iterator begin() const {return Header.Left;}
 
  const_iterator end() const {return &Header;}
 
  iterator insert(const T& Element)
  {
   Node* RootNode = Header.Parent;
 
   if (RootNode == 0)
    {
     RootNode = new setNode<T>(Element,&Header);
     Header.Left = RootNode;
     Header.Right = RootNode;
     Header.Parent = RootNode;
     return RootNode;
    }
 
   else
    {
     for (; ; )
      {
       int Result = Compare(Element,((setNode<T>*)RootNode)->Element);
 
       if (Result == 0)
        throw EntryAlreadyExistsException();
 
       else if (Result < 0)
        {
         if (RootNode->Left != 0)
          RootNode = RootNode->Left;
         else
          {
           Node* newNode = new setNode<T>(Element,RootNode);
           RootNode->Left = newNode;
           AdjustAdd(newNode);
           return newNode;
          }
        }
 
       else
        {
         if (RootNode->Right != 0)
          RootNode = RootNode->Right;
         else
          {
           Node* newNode = new setNode<T>(Element,RootNode);
           RootNode->Right = newNode;
           AdjustAdd(newNode);
           return newNode;
          }
        }
      }
    }
  } 
 
  void erase(const T& Element)
  {
   Node* RootNode = Header.Parent;
 
   for (; ; )
    {
     if (RootNode == 0) throw EntryNotFoundException();
 
     int Result = Compare(Element,((setNode<T>*)RootNode)->Element);
 
     if (Result < 0)
      RootNode = RootNode->Left;
 
     else if (Result > 0)
      RootNode = RootNode->Right;
 
     else // Item is found
      {
       if (RootNode->Left != 0 && RootNode->Right != 0)
        {
         Node* Replace = RootNode->Left;
         while (Replace->Right != 0) Replace = Replace->Right;
         SwapNodes(RootNode, Replace);
        }
 
       Node* Parent = RootNode->Parent;
 
       unsigned long From = (Parent->Left == RootNode) ? Direction::FromLeft : Direction::FromRight;
 
       if (RootNode->Left == 0)
        {
         if (Parent == &Header)
          Header.Parent = RootNode->Right;
         else if (From == Direction::FromLeft)
          Parent->Left = RootNode->Right;
         else
          Parent->Right = RootNode->Right;
 
         if (RootNode->Right != 0) RootNode->Right->Parent = Parent;
        }
       else
        {
         if (Parent == &Header)
          Header.Parent = RootNode->Left;
         else if (From == Direction::FromLeft)
          Parent->Left = RootNode->Left;
         else
          Parent->Right = RootNode->Left;
 
         if (RootNode->Left != 0) RootNode->Left->Parent = Parent;
        }
 
       AdjustRemove(Parent, From);
       delete (setNode<T>*)RootNode;
       break;
      }
    }
  }
 
  void erase(iterator i)
  {
   Node* RootNode = i._node;
 
   if (RootNode->IsHeader()) throw IsHeaderException();
 
   if (RootNode->Left != 0 && RootNode->Right != 0)
    {
     Node* Replace = RootNode->Left;
     while (Replace->Right != 0) Replace = Replace->Right;
     SwapNodes(RootNode, Replace);
    }
 
   Node* Parent = RootNode->Parent;
 
   unsigned long From = (Parent->Left == RootNode) ? Direction::FromLeft : Direction::FromRight;
 
   if (RootNode->Left == 0)
    {
     if (Parent == &Header)
      Header.Parent = RootNode->Right;
     else if (From == Direction::FromLeft)
      Parent->Left = RootNode->Right;
     else
      Parent->Right = RootNode->Right;
 
     if (RootNode->Right != 0) RootNode->Right->Parent = Parent;
    }
   else
    {
     if (Parent == &Header)
      Header.Parent = RootNode->Left;
     else if (From == Direction::FromLeft)
      Parent->Left = RootNode->Left;
     else
      Parent->Right = RootNode->Left;
 
     if (RootNode->Left != 0) RootNode->Left->Parent = Parent;
    }
 
   AdjustRemove(Parent, From);
   delete (setNode<T>*)RootNode;
  }
 
  bool operator[](const T& Element) const {return exists(Element);}
 
  bool exists(const T& Element) const
  {
   if (!Header.Parent)
    return false;
   else
    {
     const Node* SearchNode = Header.Parent;
 
     do
      {
       int Result = Compare(Element,((setNode<T>*)SearchNode)->Element);
 
       if (Result < 0) SearchNode = SearchNode->Left;
 
       else if (Result > 0) SearchNode = SearchNode->Right;
 
       else break;
 
      } while (SearchNode);
 
     return SearchNode != 0;
    }
  }
 
  iterator find(const T& Element) const
  {
   if (!Header.Parent)
     throw EntryNotFoundException();
   else
    {
     const Node* SearchNode = Header.Parent;
 
     do
      {
       int Result = Compare(Element,((setNode<T>*)SearchNode)->Element);
 
       if (Result < 0) SearchNode = SearchNode->Left;
 
       else if (Result > 0) SearchNode = SearchNode->Right;
 
       else break;
 
      } while (SearchNode);
 
      if (SearchNode == 0) throw EntryNotFoundException();
 
     return (Node*)SearchNode;
    } 
  }      
 
  void erase()
  {
   Destroy((setNode<T>*)Header.Parent);
   Header.Left = &Header;
   Header.Right = &Header;
   Header.Parent = 0;
  }
 
  iterator after(const T& Element) const
  {
   const Node* y = &Header;
   const Node* x = Header.Parent;
 
   while (x != 0) 
    if (Compare(Element,((setNode<T>*)x)->Element)<0)
     {y=x; x=x->Left;}
    else
     x=x->Right;
 
   return (Node*)y;
  }
 
  iterator afterEquals(const T& Element) const
  {
   const Node* y = &Header;
   const Node* x = Header.Parent;
 
   while (x != 0) 
    {
     int c = Compare(Element,((setNode<T>*)x)->Element);
     if (c == 0)
      {y=x; break;}  
     else if (c<0)
      {y=x; x=x->Left;}
     else
      x=x->Right;
    }
 
   return (Node*)y;
  }
 
  iterator before(const T& Element) const
  {
   const Node* y = &Header;
   const Node* x = Header.Parent;
 
   while (x != 0) 
    if (Compare(Element,((setNode<T>*)x)->Element)<=0)
     {x=x->Left;}
    else
     {y=x; x=x->Right;}
 
   return (Node*)y;
  }
 
  iterator beforeEquals(const T& Element) const
  {
   const Node* y = &Header;
   const Node* x = Header.Parent;
 
   while (x != 0) 
    {
     int c = Compare(Element,((setNode<T>*)x)->Element);
     if (c == 0)
      {y = x; break;}
     else if (c<0)
      x=x->Left;
     else
      {y=x; x=x->Right;}
    }
 
   return (Node*)y;
  }
 
  iterator last() {return Header.Right;}
 
  const_iterator last() const {return Header.Right;}
 
  unsigned long depth() const {return Depth(Header.Parent);}
 
 protected:
 
  void Copy(setNode<T>* Clone)
  {
   if (!Header.Parent) erase();
   if (Clone)
    {
     Copy((setNode<T>*&)Header.Parent,Clone,&Header);
     Header.Left = GetFirst();
     Header.Right = GetLast();
    }
  }
 
  void Copy(setNode<T>*& RootNode,
            setNode<T>* n,
            const Node* Parent)
  {
   RootNode = new setNode<T>(n->Element,(Node*)Parent);
   RootNode->Balance = n->Balance;
 
   if (n->Left)
     Copy((setNode<T>*&)RootNode->Left,(setNode<T>*)n->Left,RootNode);
   else RootNode->Left = 0;
 
   if (n->Right)
     Copy((setNode<T>*&)RootNode->Right,(setNode<T>*)n->Right,RootNode);
   else RootNode->Right = 0;
  }
 
  Node* GetFirst()
  {
   if (!Header.Parent)
    return &Header;
 
   else
    {
     Node* SearchNode = Header.Parent;
     while (SearchNode->Left) SearchNode = SearchNode->Left;
     return SearchNode;
    } 
  }      
 
  Node* GetLast()
  {
   if (!Header.Parent)
    return &Header;
 
   else
    {
     Node* SearchNode = Header.Parent;
     while (SearchNode->Right) SearchNode = SearchNode->Right;
     return SearchNode;
    } 
  }      
 
  void Destroy(setNode<T>* RootNode)
  {
    if (RootNode)
    { 
     if (RootNode->Left)
      Destroy((setNode<T>*)RootNode->Left); 
 
     if (RootNode->Right)
      Destroy((setNode<T>*)RootNode->Right);
 
     delete RootNode;
    }
  }
};
 
template<class T>
inline set<T> operator|(const set<T>& a,const set<T>& b)
{set<T> r(a,b,setOperation::Union); return r;}
 
template<class T>
inline set<T> operator&(const set<T>& a,const set<T>& b)
{set<T> r(a,b,setOperation::Intersection); return r;}
 
template<class T>
inline set<T> operator^(const set<T>& a,const set<T>& b)
{set<T> r(a,b,setOperation::SymmetricDifference); return r;}
 
template<class T>
inline set<T> operator-(const set<T>& a,const set<T>& b)
{set<T> r(a,b,setOperation::Difference); return r;}
 
template<class T>
inline bool operator==(const set<T>& a,const set<T>& b)
{
 set<T>::const_iterator first1 = a.begin();
 set<T>::const_iterator last1  = a.end();
 set<T>::const_iterator first2 = b.begin();
 set<T>::const_iterator last2  = b.end();
 
 bool equals=true;
 
 set<T>::keyCompare c = a;
 
 while (first1 != last1 && first2 != last2)
  {
   int order = c(*first1,*first2);
   if (order < 0)
    {equals=false; break;}
   else if (order > 0)
    {equals=false; break;}
   else
    {++first1; ++first2;}
  }
 
 if (equals)
  {
   if (first1 != last1) equals = false;
   if (first2 != last2) equals = false;
  }
 
 return equals;
}
 
template<class T>
inline bool operator!=(const set<T>& a,const set<T>& b) {return !(a == b);}
 
template<class T>
inline bool operator<=(const set<T>& a,const set<T>& b)
{
 set<T>::const_iterator first1 = a.begin();
 set<T>::const_iterator last1  = a.end();
 set<T>::const_iterator first2 = b.begin();
 set<T>::const_iterator last2  = b.end();
 
 set<T>::keyCompare c = a;
 
 bool subset=true;
 
 while (first1 != last1 && first2 != last2)
  {
   int order = c(*first1,*first2);
 
   if (order < 0)
    {subset=false; break;}
 
   else if (order > 0)
    ++first2;
 
   else
    {++first1; ++first2;}
  }
 
 if (subset) if (first1 != last1) subset = false;
 
 return subset;
}
 
template<class T>
inline int compare(const set<T>& a,const set<T>& b)
{
 set<T>::const_iterator first1 = a.begin();
 set<T>::const_iterator last1  = a.end();
 set<T>::const_iterator first2 = b.begin();
 set<T>::const_iterator last2  = b.end();
 
 set<T>::keyCompare c = a;
 
 while (first1 != last1 && first2 != last2)
  {
   int order = c(*first1,*first2);
   if (order < 0)
    return -1;
   else if (order > 0)
    return 1;
   else
    {++first1; ++first2;}
  }
 
 if (first1 != last1) return 1;
 if (first2 != last2) return -1;
 
 return 0;
}
 
template<class T>
std::ostream& operator<<(std::ostream& s,const set<T>& o)
{
 s << "{";
 set<T>::const_iterator e = o.end();
 set<T>::const_iterator l = e-1;
 for (set<T>::const_iterator i = o.begin(); i!=e; ++i)
  {s << *i; if (i!=l) s << ",";}
 s << "}";
 return s;
}

The code for balancing the set upon removal is also in place. There are separate diagrams for the removals available in.

Comparison to other structures

Both AVL trees and red–black trees are self-balancing binary search trees and they are very similar mathematically. The operations to balance the trees are different, but both occur on the average in O(1) with maximum in O(log n). The real difference between the two is the limiting height.

For a tree of size n ≥ 1

• an AVL tree’s height is at most

  ${\begin{array}{ll}h&\leqq \;c\log _{2}(n+d)+b\\&<\;c\log _{2}(n+2)+b\end{array}}$

where $\varphi :={\tfrac {1+{\sqrt {5}}}{2}}\approx 1.618$  the golden ratio, $c:={\tfrac {1}{\log _{2}\varphi }}\approx 1.44,$   $b:={\tfrac {c}{2}}\log _{2}5-2\approx \;-0.328,$ and  $d:=1+{\tfrac {1}{\varphi ^{4}{\sqrt {5}}}}\approx 1.07$.

• a red–black tree’s height is at most

  ${\begin{array}{ll}h&\leqq \;2\log _{2}(n+1)\end{array}}$

AVL trees are more rigidly balanced than red–black trees, leading to faster retrieval. They are similar on insertion and deletion.

See also

• Trees
• Tree rotation
• Red–black tree
• Splay tree
• Scapegoat tree
• B-tree
• T-tree
• List of data structures

External links

• AVL tree demonstration (requires Flash)
• The online reference is at The Standard Library.

References

This article "AVL Trees in C++" is from Wikipedia. The list of its authors can be seen in its historical. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

📰 Article(s) of the same category(ies)

• AVL Trees in Managed C++
• Deep column station
• AVL Tree in CSharp
• Hydro-slotted perforation
• AVL Trees in Java

---