AVL Trees in Managed C++

AVL tree
Type	tree
Invented	1962
Invented by	Georgy Adelson-Velsky and Evgenii Landis
Time complexity in big O notation

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".^[1]

AVL Tree Rotations[edit]

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[edit]

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[edit]

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.

public enum class State
{
 Header,
 LeftHigh,
 Balanced,
 RightHigh
};

Properties[edit]

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.^[2]

The height $h$ of an AVL tree with $n$ nodes lies in the interval:^[3]

log 2 (n +1) \leq h < c log 2 (n +2)+ b

with the golden ratio $φ := (1+$ √ $5$ $) ⁄ 2 \approx 1.618$ , $c := 1 ⁄ log 2 φ \approx 1.44$ , and $b := c ⁄ 2 log 2 5 - 2 \approx -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 = 1$ , $F 2 = 1$ .

NameSpaces[edit]

At the top of your program, you should include the following namespaces. The the code goes into the namespace of your choice ('ISharp' below).

using namespace System;
using namespace System;
using namespace System::Collections;
using namespace System::Collections::Generic;
using namespace System::Threading;
using namespace System::Runtime::Serialization;

namespace ISharp
{
  ... Code Goes Here ...
}

Direction[edit]

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.

public enum class Direction { FromLeft, FromRight };

Node Classes[edit]

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.

public ref struct Node
{
 Node^ Left;
 Node^ Right;
 Node^ Parent;
 State Balance;
 
 Node()
 {
  Left = this;
  Right = this;
  Parent = nullptr;
  Balance = State::Header;
 }
 
 Node(Node^ p)
 {
  Left = nullptr;
  Right = nullptr;
  Parent = p;
  Balance = State::Balanced;
 }
 
 property Boolean IsHeader
 { Boolean get() { return Balance == State::Header; } }
};

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

generic<typename T>
public ref class SetNode : Node
{
 public:

  T Data;

  SetNode(T dataType, Node^ Parent) : Node(Parent) {Data = dataType; }
};

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).

Delegates[edit]

The following delegates are used to support the Added, Removed and Updated events of the set class.

generic <typename T>
public delegate void TypeAdded(Object^ O, T type);

generic <typename T>
public delegate void TypeRemoved(Object^ O, T type);

generic <typename T>
public delegate void TypeUpdated(Object^ O, T before, T after);

Cloning[edit]

The following cloning classes probably should be built in to .Net.

generic<typename T>
 public interface struct ICloneable
 {
  T Clone();
 };

generic<typename T>
public interface class ICloner  {  T Clone(T t); };

generic<typename T>
[Serializable]
 public ref struct Cloner abstract : ICloner<T>
{
 static property Cloner<T>^ Default { Cloner<T>^ get(); }

 static property Cloner<T>^ Invisible { Cloner<T>^ get(); }

 virtual T Clone(T t) = 0;
};

generic<typename T>
[Serializable]
public ref struct DefaultCloner1 : Cloner<T>
{
 virtual T Clone(T t) override
 {
  ICloneable<T>^ copier = (ICloneable<T>^)t;
  return copier->Clone();
 }
};

generic<typename T>
[Serializable]
public ref struct DefaultCloner2 : Cloner<T>
{
 virtual T Clone(T t) override
 {
  ICloneable<T>^ copier = (ICloneable<T>^)t;
  return (T)copier->Clone();
 }
};

generic<typename T>
[Serializable]
public ref struct DefaultNoCloner : Cloner<T>
{
 virtual T Clone(T t) override
 {
  return t;
 }
};

generic<typename T>
Cloner<T>^ Cloner<T>::Default::get()
{
   Type^ TypeT = T::typeid;
   Type^ TypeIC1 = ICloneable<T>::typeid;
   Type^ TypeIC2 = ICloneable::typeid;
   if (TypeIC1->IsAssignableFrom(TypeT))
     return gcnew DefaultCloner1<T>();
   else if (TypeIC2->IsAssignableFrom(TypeT))
     return gcnew DefaultCloner2<T>();
   else
     return gcnew DefaultNoCloner<T>();
}

 generic<typename T>
 Cloner<T>^ Cloner<T>::Invisible::get() { return gcnew DefaultNoCloner<T>(); }

AVL Utilities[edit]

The AVL Utility functions are as follows.

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

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

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

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

void BalanceTree(Node^ Root, Direction From)
{
  bool Taller = true;

  while (Taller)
   {
    Node^ Parent = Root->Parent;
    Direction 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;
       }
     }
   }
 }

void BalanceTreeRemove(Node^ Root, Direction From)
{
  if (Root->IsHeader) return;
  bool Shorter = true;

  while (Shorter)
   {
    Node^ Parent = Root->Parent;
    Direction 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^ Minimum(Node^ node)
{
 while (node->Left) node=node->Left;
 return node;
}

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, Direction Direction)
{
 BalanceTreeRemove(Parent,Direction);
 
 Node^ Header = Parent;
 while (!Header->IsHeader) Header=Header->Parent;

 if (Header->Parent == nullptr)
 {
  Header->Left = Header;
  Header->Right = Header;
 }
 else
 {
  Header->Left = Minimum(Header->Parent);
  Header->Right = Maximum(Header->Parent);
 }
}

Node^ PreviousItem(Node^ node)
{
 if (node->IsHeader) {return node->Right;}

 else if (node->Left != nullptr)
  {
   Node^ y = node->Left;
   while (y->Right != nullptr) 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 != nullptr)
  {
   node = node->Right;
   while (node->Left != nullptr) 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;
}

void SwapNodeReference(Node^% first, Node^% second)
{Node^ temporary = first; first = second; second = temporary;}

void LeftNodeSwap(Node^ Root, Node^ Replace)
{
 if (Replace->Left) Replace->Left->Parent = Root;
 if (Replace->Right) Replace->Right->Parent = Root;

 if (Root->Right) Root->Right->Parent = Replace;

 if (Replace == Root->Left)
  {
   Replace->Parent = Root->Parent;
   Root->Parent = Replace;

   Root->Left = Replace->Left;
   Replace->Left = Root;
  }
 else
  {
   Root->Left->Parent = Replace;

   if (Replace->Parent->Left == Replace)
    Replace->Parent->Left = Root;
   else
    Replace->Parent->Right = Root;

   SwapNodeReference(Root->Left,Replace->Left);
   SwapNodeReference(Root->Parent,Replace->Parent);
  }

 SwapNodeReference(Root->Right,Replace->Right);

 State Balance = Root->Balance;
 Root->Balance = Replace->Balance;
 Replace->Balance=Balance;
}

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

 State Balance = A->Balance;
 A->Balance = B->Balance;
 B->Balance=Balance;
}

unsigned long long Depth(Node^ Root)
{
 if (Root)
  {
   unsigned long long Left  = Root->Left  ? Depth(Root->Left)  : 0;
   unsigned long long Right = Root->Right ? Depth(Root->Right) : 0;
   return Left < Right ? Right+1 : Left+1;
  }
 else
  return 0;
}

unsigned long long Count(Node^ Root)
{
 if (Root)
  {
   unsigned long long left  = Root->Left  ? Count(Root->Left)  : 0;
   unsigned long long right = Root->Right ? Count(Root->Right) : 0;
   return left + right + 1;
  }
 else
  return 0;
}

Explanation of Balancing[edit]

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[edit]

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[edit]

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[edit]

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 Enumerators[edit]

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

generic<typename T>
public value struct SetEntry : System::Collections::Generic::IEnumerator<T>
{
 public:

  SetEntry(Node^ n) { _Node = n; }

  property T Value
  {
   T get()
    {
     if (_Node->Balance == State::Header) throw gcnew IsEndItemException();
     return ((SetNode<T>^)_Node)->Data;
    }
   void set(T Value)
    {
     if (_Node->Balance == State::Header) throw gcnew IsEndItemException();
     ((SetNode<T>^)_Node)->Data = Value;
    }
  }

 property Boolean IsHeader { Boolean get() { return _Node->IsHeader; } }

 virtual Boolean MoveNext()
 {
  _Node = NextItem(_Node);
  return _Node->IsHeader ? false : true;
 }

 Boolean MovePrevious()
 {
  _Node = PreviousItem(_Node);
  return _Node->IsHeader ? false : true;
 }

 static SetEntry<T> operator ++(SetEntry<T> entry)
 {
  entry._Node = NextItem(entry._Node);
  return entry;
 }

 static SetEntry<T> operator --(SetEntry<T> entry)
 {
  entry._Node = PreviousItem(entry._Node);
  return entry;
 }

 static SetEntry<T> operator +(SetEntry<T> C, unsigned long long Increment)
 {
  SetEntry<T> Result =  SetEntry<T>(C._Node);
  for (unsigned long long i = 0; i < Increment; i++) ++Result;
  return Result;
 }

 static SetEntry<T> operator +(unsigned long long Increment, SetEntry<T> C)
 {
  SetEntry<T> Result = SetEntry<T>(C._Node);
  for (unsigned long long i = 0; i < Increment; i++) ++Result;
  return Result;
 }

 static SetEntry<T> operator -(SetEntry<T> C, unsigned long long Decrement)
 {
  SetEntry<T> Result = SetEntry<T>(C._Node);
  for (unsigned long long i = 0; i < Decrement; i++) --Result;
  return Result;
 }

 virtual void Reset()
 { while (!_Node->IsHeader) _Node = NextItem(_Node); }

 virtual property Object^ InterfaceCurrentA
  {
   Object^ get()  = System::Collections::IEnumerator::Current::get
      {
          if (_Node->Balance == State::Header) throw gcnew IsEndItemException();
          return ((SetNode<T>^)_Node)->Data;
      }
  }

 virtual property T InterfaceCurrentB
  {
   T get()  = System::Collections::Generic::IEnumerator<T>::Current::get
      {
          if (_Node->Balance == State::Header) throw gcnew IsEndItemException();
          return ((SetNode<T>^)_Node)->Data;
      }
  }

 static Boolean operator ==(SetEntry<T> x, SetEntry<T> y) { return x._Node == y._Node; }
 static Boolean operator !=(SetEntry<T> x, SetEntry<T> y) { return x._Node != y._Node; }

 static long long operator -(SetEntry<T> This, SetEntry<T> iter)
 {
  long long Result = 0;
  while (This._Node != iter._Node) { iter.MoveNext(); Result++; }
  return Result;
 }

 virtual String^ ToString() override
 {
  if (_Node->Balance == State::Header) throw gcnew IsEndItemException();
  return Value->ToString();
 }

 Node^ _Node;
};

Set Operations[edit]

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

 public enum class SetOperation
 {
            Union,
            Intersection,
            SymmetricDifference,
            Difference,
            Equality,
            Inequality,
            Subset,
            Superset
 };

Exceptions[edit]

The following exception classes need to be defined.

    public ref struct OutOfKeyOrderException : public Exception
    {
        static String^ message = gcnew String("A tree was found to be out of key order.");

        OutOfKeyOrderException() : Exception(message)
        {
            Source = gcnew String("StandardGenericLibrary Collections Subsystem");
        }
    };

    public ref struct TreeInvalidParentException : public Exception
    {
        static String^ message = gcnew String("The parent structure of a tree is invalid.");

        TreeInvalidParentException() : Exception(message)
        {
            Source = gcnew String("StandardGenericLibrary Collections Subsystem");
        }
    };

    public ref struct TreeOutOfBalanceException : public Exception
    {
        static String^ message = gcnew String("The tree is out of balance.");

        TreeOutOfBalanceException() : Exception(message)
        {
            Source = gcnew String("StandardGenericLibrary Collections Subsystem");
        }
    };

    public ref struct InvalidEmptyTreeException : public Exception
    {
        static String^ message = gcnew String("An empty tree is invalid.");

        InvalidEmptyTreeException() : Exception(message)
        {
            Source = gcnew String("StandardGenericLibrary Collections Subsystem");
        }
    };


    public ref struct InvalidEndItemException : public Exception
    {
        static String^ message = gcnew String("The end item of a tree is invalid.");

        InvalidEndItemException() : Exception(message)
        {
            Source = gcnew String("StandardGenericLibrary Collections Subsystem");
        }
    };

     public ref struct EntryAlreadyExistsException : public Exception
    {
        static String^ message = gcnew String("An entry already exists in the collection.");

        EntryAlreadyExistsException() : Exception(message)
        {
            Source = gcnew String("StandardGenericLibrary Collections Subsystem");
        }
    };

    public ref struct DifferentKeysException : public Exception
    {
        static String^ message = gcnew String("The specified items have different keys.");

        DifferentKeysException() : Exception(message)
        {
            Source = gcnew String("StandardGenericLibrary Collections Subsystem");
        }
    };

    public ref struct AddSubTreeFailedException : public Exception
    {
        static String^ message = gcnew String("Subtree creation failed.");

        AddSubTreeFailedException() : Exception(message)
        {
            Source = gcnew String("StandardGenericLibrary Collections Subsystem");
        }
    };

    public ref struct IsEndItemException : public Exception
    {
        static String^ message = gcnew String("The requested action cannot be performed on an end item.");

        IsEndItemException() : Exception(message)
        {
            Source = gcnew String("ISharp Collections Subsystem");
        }
    };

    public ref struct EntryNotFoundException : public Exception
    {
        static String^ message = gcnew String("The requested entry could not be located in the specified collection.");

        EntryNotFoundException() : Exception(message)
        {
            Source = gcnew String("StandardGenericLibrary Collections Subsystem");
        }
    };

    public ref struct InvalidSetOperationException : public Exception
    {
        static String^ message = gcnew String("An invalid set operation was specified.");

        InvalidSetOperationException() : Exception(message)
        {
            Source = gcnew String("StandardGenericLibrary Collections Subsystem");
        }
    };

The Set Class[edit]

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

generic<typename T>
[Serializable]
public ref class Set : public System::Collections::Generic::ICollection<T>,
                       public System::ICloneable,
                       public ISerializable,
                       public IComparable<Set<T>^>,
                       public IEquatable<Set<T>^>
{
 public:
  event TypeAdded<T>^ Added;
  event TypeRemoved<T>^ Removed;
  event TypeUpdated<T>^ Updated;

 protected:
  Node^ Header;
  System::Collections::Generic::IComparer<T>^ TComparer;
  ICloner<T>^ TCloner;
  unsigned long long Nodes;

  property Node^ Root
  {
   Node^ get() { return Header->Parent; }
   void set(Node^ Value) { Header->Parent = Value; }
  }

        //*** Constructors ***

 public:

  Set()
   {
    Nodes=0;
    Header = gcnew Node();
    TComparer = System::Collections::Generic::Comparer<T>::Default;
    TCloner = ISharp::Cloner<T>::Default;
   }

  Set(System::Collections::Generic::IComparer<T>^ TCompare)
  {
   Nodes=0;
   Header = gcnew Node();
   TComparer = TCompare;
   TCloner = ISharp::Cloner<T>::Default;
  }

  Set(Set<T>^ SetToCopy)
  {
   Nodes=0;
   Header = gcnew Node();
   TComparer = SetToCopy->TComparer;
   TCloner = SetToCopy->TCloner;
   Copy((SetNode<T>^)SetToCopy->Root);
  }

  Set(System::Collections::Generic::IEnumerable<T>^ Collection)
  {
   Nodes=0;
   Header = gcnew Node();
   TComparer = System::Collections::Generic::Comparer<T>::Default;
   TCloner = ISharp::Cloner<T>::Default;

   for each (T t in Collection) Add(TCloner->Clone(t));
  }

  Set(... array<T>^ Collection)
  {
   Nodes=0;
   Header = gcnew Node();
   TComparer = System::Collections::Generic::Comparer<T>::Default;
   TCloner = ISharp::Cloner<T>::Default;

   for each (T t in Collection) Add(TCloner->Clone(t));
  }

  Set(System::Collections::Generic::IEnumerable<T>^ Collection,
      System::Collections::Generic::IComparer<T>^ TCompare)
  {
   Nodes=0;
   Header = gcnew Node();
   TComparer = TCompare;
   TCloner = ISharp::Cloner<T>::Default;
 
   for each (T t in Collection) Add(TCloner->Clone(t));
  }

  Set(Set<T>^ A,
      Set<T>^ B,
      SetOperation operation)
  {
   Nodes=0;
   Header = gcnew Node();
   TComparer = A->TComparer;
   TCloner = A->TCloner;
   CombineSets(A, B, this, operation);
  }

  Set(SerializationInfo^ si, StreamingContext sc)
  {
   Nodes=0;
   System::Collections::Generic::IComparer<T>^ TCompare = (System::Collections::Generic::IComparer<T>^)si->GetValue("TComparer", System::Collections::Generic::IComparer<T>::typeid);
   ISharp::ICloner<T>^ TClone = (ISharp::ICloner<T>^)si->GetValue("TCloner", ICloner<T>::typeid);

   Header = gcnew Node();
   TComparer = TCompare;
   TCloner = TClone;

   Type^ type = T::typeid;

   unsigned long long LoadCount = si->GetUInt64("Count");

   for (unsigned long long i = 0; i < LoadCount; i++)
   {
    Object^ obj = si->GetValue(i.ToString(), type);
    Add((T)obj, false);
   }
  }

        //*** Operators ***

  static Set<T>^ operator |(Set<T>^ A, Set<T>^ B)
  {
   Set<T>^ U = gcnew Set<T>(A->TComparer);
   U->TCloner = A->TCloner;
   CombineSets(A, B, U, SetOperation::Union);
   return U;
  }

  static Set<T>^ operator &(Set<T>^ A, Set<T>^ B)
  {
   Set<T>^ I = gcnew Set<T>(A->TComparer);
   I->TCloner = A->TCloner;
   CombineSets(A, B, I, SetOperation::Intersection);
   return I;
  }

  static Set<T>^ operator ^(Set<T>^ A, Set<T>^ B)
  {
   Set<T>^ S = gcnew Set<T>(A->TComparer);
   S->TCloner = A->TCloner;
   CombineSets(A, B, S, SetOperation::SymmetricDifference);
   return S;
  }

  static Set<T>^ operator -(Set<T>^ A, Set<T>^ B)
  {
   Set<T>^ S = gcnew Set<T>(A->TComparer);
   S->TCloner = A->TCloner;
   CombineSets(A, B, S, SetOperation::Difference);
   return S;
  }

  static Boolean operator ==(Set<T>^ A, Set<T>^ B)
  {
   return CheckSets(A, B, SetOperation::Equality);
  }

  static Boolean operator !=(Set<T>^ A, Set<T>^ B)
  {
   return CheckSets(A, B, SetOperation::Inequality);
  }

  static Boolean operator <(Set<T>^ A, Set<T>^ B)
  {
   return CheckSets(A, B, SetOperation::Subset);
  }

  static Boolean operator >(Set<T>^ A, Set<T>^ B)
  {
   return CheckSets(A, B, SetOperation::Superset);
  }

  property Boolean default [T]
  {
   Boolean get(T key)
   {
    if (Root == nullptr)
     return false;
    else
     {
      Node^ search = Root;

      do
       {
        int Result = TComparer->Compare(key, static_cast<SetNode<T>^>(search)->Data);

        if (Result < 0) search = search->Left;

        else if (Result > 0) search = search->Right;

        else break;

       } while (search != nullptr);

       return search != nullptr;
      }
    }
  }

 static Set<T>^ operator +(Set<T>^ set, T t)
 {
  set->Add(t, false);
  return set;
 }

 static Set<T>^ operator -(Set<T>^ set, T t)
 {
  set->Remove(t);
  return set;
 }

 //*** Properties ***

 property SetEntry<T> Begin
 { SetEntry<T> get() { return SetEntry<T>(Header->Left); } }

 property ICloner<T>^ TypeCloner
 {
  ICloner<T>^ get() { return TCloner; }
  void set(ICloner<T>^ Value) { TCloner = Value; }
 }
 property System::Collections::Generic::IComparer<T>^ Comparer
 {System::Collections::Generic::IComparer<T>^ get() { return TComparer; } }

 virtual property int Count { int get() { return (int)Length; } }

 property SetEntry<T> End
 { SetEntry<T> get() { return SetEntry<T>(Header); } }

 property T First
 { T get() { return ((SetNode<T>^)LeftMost)->Data; } }

 virtual property Boolean IsReadOnly { Boolean get() { return false; } }

 virtual property Boolean IsSynchronized { Boolean get() { return true; } }

 property T Last
 { T get() { return ((SetNode<T>^)RightMost)->Data; } }

 property Node^ LeftMost
 {
  Node^ get() { return Header->Left; }
  void set(Node^ Value) { Header->Left = Value; }
 }

 property unsigned long long Length {  unsigned long long get() { return Count;} }

 property Node^ RightMost
 {
  Node^ get() { return Header->Right; }
  void set(Node^ Value) { Header->Right = Value; }
 }
 
 property Object^ SyncRoot { Object^ get() { return this; } }

        //*** Public Methods ***

 SetEntry<T> After(T Value, Boolean equals)
 {
  return SetEntry<T>(equals ? AfterEquals(Value) : After(Value));
 }

 virtual void Add(T t)
 {
  Add(t, false);
 }

 void Add(SetEntry<T> cse)
 {
  Add(TCloner->Clone(cse.Value), false);
 }

 unsigned long long Add(System::Collections::Generic::IEnumerable<T>^ copy)
 {
  unsigned long long count = 0;

  for each(T t in copy)
  {
   Add(TCloner->Clone(t), false);
   count++;
  }

  return count;
 }

 SetEntry<T> Before(T value, bool equals)
 {
  return SetEntry<T>(equals ? BeforeEquals(value) : Before(value));
 }

 virtual void Clear() { Remove(); }

 void CallRemoved(T data) { Removed(this, data); }

 virtual Object^ Clone()
 {
  Set<T>^ setOut = gcnew Set<T>(TComparer);
  setOut->TCloner = TCloner;
  setOut->Copy((SetNode<T>^)Root);
  return setOut;
 }

 virtual int CompareTo(Set<T>^ B)
 {
  return CompareSets(this, B);
 }

 virtual bool Contains(T t)
 {
  Node^ found = Search(t);
  return found != nullptr ? true : false;
 }

 virtual Boolean Contains(Set<T>^ ss)
 {
  for each (T t in ss)
   if (Search(t) == nullptr) return false;

  return true;
 }

 virtual void CopyTo(array<T>^ arr, int i)
 {
  SetEntry<T> begin = SetEntry<T>((SetNode<T>^)Header->Left);
  SetEntry<T> end = SetEntry<T>(Header);

  while (begin != end)
  {
   arr->SetValue(TCloner->Clone(((SetNode<T>^)begin._Node)->Data), i);
   i++; begin.MoveNext();
  }
 }

  virtual void CopyTo(System::Array^ arr, int i)
  {
   SetEntry<T> begin = SetEntry<T>((SetNode<T>^)Header->Left);
   SetEntry<T> end = SetEntry<T>(Header);

   while (begin != end)
   {
     arr->SetValue(TCloner->Clone(((SetNode<T>^)begin._Node)->Data), i);
     i++; begin.MoveNext();
   }
  }

  virtual Boolean Equals(Set<T>^ compare)
  {
   SetEntry<T> first1 = Begin;
   SetEntry<T> last1 = End;
   SetEntry<T> first2 = compare->Begin;
   SetEntry<T> last2 = compare->End;

   Boolean equals = true;

   while (first1 != last1 && first2 != last2)
    {
     if (TComparer->Compare(first1.Value, first2.Value) == 0)
      { first1.MoveNext(); first2.MoveNext(); }
     else
      { equals = false; break; }
    }

   if (equals)
    {
     if (first1 != last1) equals = false;
     if (first2 != last2) equals = false;
    }

   return equals;
  }

  T Find(T value)
  {
   Node^ _Node = Search(value);
   if (_Node == nullptr)
     throw gcnew EntryNotFoundException();
   return ((SetNode<T>^)_Node)->Data;
  }

 virtual System::Collections::IEnumerator^ InterfaceGetEnumeratorSimple() sealed = System::Collections::IEnumerable::GetEnumerator
 { return gcnew SetEntry<T>(Header); }

 virtual System::Collections::Generic::IEnumerator<T>^ InterfaceGetEnumerator() sealed = System::Collections::Generic::IEnumerable<T>::GetEnumerator
 { return gcnew SetEntry<T>(Header); }

  virtual void GetObjectData(SerializationInfo^ si, StreamingContext sc)
  {
   si->SetType(ISharp::Set<T>::typeid);

   Type^ type = T::typeid;

   unsigned long long index = 0;
   for each (T e in *this)
   {
     si->AddValue(index.ToString(), e, type);
     index++;
   }

   si->AddValue("Count", index);
   si->AddValue("TComparer", TComparer, TComparer->GetType());
   si->AddValue("TCloner", TCloner, TCloner->GetType());
  }

  SetEntry<T> Insert(T t) { return SetEntry<T>(Add(t, false)); }

  SetEntry<T> Locate(T value)
  {
   Node^ _Node = Search(value);
   if (_Node == nullptr)
     throw gcnew EntryNotFoundException();
   return SetEntry<T>(_Node);
  }

  void Notify()
  {
   Notify((SetNode<T>^)Root);
  }

  unsigned long long Remove()
  {
   for each (T t in this) Removed(this, t);
   unsigned long long count = Nodes;
   Root = nullptr;
   LeftMost = Header;
   RightMost = Header;
   Nodes = 0;
   return count;
  }

  virtual bool Remove(T data)
  {
   Node^ root = Root;

   for (; ; )
   {
    if (root == nullptr) throw gcnew EntryNotFoundException();

    int compare = TComparer->Compare(data, ((SetNode<T>^)root)->Data);

    if (compare < 0)
     root = root->Left;

    else if (compare > 0)
     root = root->Right;

    else // Item is found
    {
     if (root->Left != nullptr && root->Right != nullptr)
     {
      Node^ replace = root->Left;
      while (replace->Right != nullptr) replace = replace->Right;
      SwapNodes(root, replace);
     }

     Node^ Parent = root->Parent;

     Direction From = (Parent->Left == root) ? Direction::FromLeft : Direction::FromRight;

     if (LeftMost == root)
      {
       Node^ n = NextItem(root);

       if (n->IsHeader)
        { LeftMost = Header; RightMost = Header; }
       else
         LeftMost = n;
      }
      else if (RightMost == root)
       {
        Node^ p = PreviousItem(root);

        if (p->IsHeader)
         { LeftMost = Header; RightMost = Header; }
        else
          RightMost = p;
       }

     if (root->Left == nullptr)
     {
      if (Parent == Header)
        Header->Parent = root->Right;
      else if (Parent->Left == root)
        Parent->Left = root->Right;
      else
        Parent->Right = root->Right;

      if (root->Right != nullptr) root->Right->Parent = Parent;
     }
     else
      {
       if (Parent == Header)
        Header->Parent = root->Left;
       else if (Parent->Left == root)
        Parent->Left = root->Left;
       else
        Parent->Right = root->Left;

       if (root->Left != nullptr) root->Left->Parent = Parent;
      }

      AdjustRemove(Parent, From);
      Nodes--;
      Removed(this, ((SetNode<T>^)root)->Data);
      break;
     }
   }
   return true;
  }

  void Remove(SetEntry<T> i) { Remove(i._Node); }

  Node^ Search(T data)
  {
   if (Root == nullptr)
     return nullptr;
   else
    {
     Node^ search = Root;

     do
      {
       int Result = TComparer->Compare(data, ((SetNode<T>^)search)->Data);

       if (Result < 0) search = search->Left;

       else if (Result > 0) search = search->Right;

       else break;

      } while (search != nullptr);

      return search;
    }
  }

  virtual String^ ToString() override
  {
   String^ StringOut = gcnew String("{");

   SetEntry<T> start = Begin;
   SetEntry<T> end = End;
   SetEntry<T> last = End - 1;

   while (start != end)
   {
    String^ NewStringOut = start.Value->ToString();
    if (start != last) NewStringOut = NewStringOut + gcnew String(",");
    StringOut = StringOut + NewStringOut;
    ++start;
   }

   StringOut = StringOut + gcnew String("}");
   return StringOut;
  }

 void Update(T value)
 {
  if (Root == nullptr)
   throw gcnew EntryNotFoundException();
  else
   {
    Node^ search = Root;

    do
    {
     int Result = TComparer->Compare(value, ((SetNode<T>^)search)->Data);

     if (Result < 0) search = search->Left;

     else if (Result > 0) search = search->Right;

     else break;

    } while (search != nullptr);

    if (search == nullptr) throw gcnew EntryNotFoundException();

    T saved = ((SetNode<T>^)search)->Data;
    ((SetNode<T>^)search)->Data = value;
    Updated(this, saved, value);
  }
 }

 void Update(SetEntry<T>^ entry, T after) {  Update((SetNode<T>^)entry->_Node, after); }

 void Validate()
 {
  if (Nodes == 0 || Root == nullptr)
  {
   if (Nodes != 0) { throw gcnew InvalidEmptyTreeException(); }
   if (Root != nullptr) { throw gcnew InvalidEmptyTreeException(); }
   if (LeftMost != Header) { throw gcnew InvalidEndItemException(); }
   if (RightMost != Header) { throw gcnew InvalidEndItemException(); }
  }

  Validate((SetNode<T>^)Root);

  if (Root != nullptr)
  {
   Node^ x = Root;
   while (x->Left != nullptr) x = x->Left;

   if (LeftMost != x) throw gcnew InvalidEndItemException();

   Node^ y = Root;
   while (y->Right != nullptr) y = y->Right;

   if (RightMost != y) throw gcnew InvalidEndItemException();
  }
 }

        //*** Private Methods ***

 protected:

 Node^ After(T data)
 {
  Node^ y = Header;
  Node^ x = Root;

  while (x != nullptr)
   if (TComparer->Compare(data, ((SetNode<T>^)x)->Data) < 0)
    { y = x; x = x->Left; }
   else
     x = x->Right;

  return y;
 }

 Node^ AfterEquals(T data)
 {
  Node^ y = Header;
  Node^ x = Root;

  while (x != nullptr)
  {
   int c = TComparer->Compare(data, ((SetNode<T>^)x)->Data);
   if (c == 0)
    { y = x; break; }
   else if (c < 0)
    { y = x; x = x->Left; }
   else
    x = x->Right;
  }

  return y;
 }

 SetNode<T>^ Add(T data, bool exist)
 {
  Node^ root = Root;

  if (root == nullptr)
   {
    Root = gcnew SetNode<T>(data, Header);
    Nodes++;
    LeftMost = Root;
    RightMost = Root;
    Added(this, ((SetNode<T>^)Root)->Data);
    return (SetNode<T>^)Root;
   }
  else
   {
    for (; ; )
     {
      int compare = TComparer->Compare(data, static_cast<SetNode<T>^>(root)->Data);

      if (compare == 0) // Item Exists
       {
        if (exist)
         {
          T saved = ((SetNode<T>^)root)->Data;
          ((SetNode<T>^)root)->Data = data;
          Updated(this, saved, data);
          return (SetNode<T>^)root;
         }
        else
         throw gcnew EntryAlreadyExistsException();
       }

      else if (compare < 0)
       {
        if (root->Left != nullptr)
         root = root->Left;
        else
         {
          SetNode<T>^ NewNode = gcnew SetNode<T>(data, root);
          Nodes++;
          root->Left = NewNode;
          AdjustAdd(NewNode);
          Added(this, NewNode->Data);
          return NewNode;
         }
      }

    else
     {
      if (root->Right != nullptr)
       root = root->Right;
      else
       {
        SetNode<T>^ NewNode = gcnew SetNode<T>(data, root);
        Nodes++;
        root->Right = NewNode;
        AdjustAdd(NewNode);
        Added(this, NewNode->Data);
        return NewNode;
       }
     }
    }
   }
 }

 unsigned long long Add(Node^ begin, Node^ end)
 {
  bool success = true;
  unsigned long long count = 0;

  SetEntry<T> i(begin);

  while (success && i._Node != end)
  {
   if (!i._Node->IsHeader)
    {
     try
      {
       Add(TCloner->Clone(i.Value), false);
       count++;
       i.MoveNext();
      }
     catch (Exception^) { success = false; }
    }
   else i.MoveNext();
  }
  if (!success)
   {
    if (count != 0)
     {
      i.MovePrevious();
      SetEntry<T> start(begin); start.MovePrevious();

      while (i != start)
       {
        SetEntry<T> j(i._Node); j.MovePrevious();
        if (!i._Node->IsHeader) Remove(i.Value);
        i = j;
       }
     }
    throw gcnew AddSubTreeFailedException();
   }
  return Count;
 }

 Node^ Before(T data)
 {
  Node^ y = Header;
  Node^ x = Root;

  while (x != nullptr)
   if (TComparer->Compare(data, ((SetNode<T>^)x)->Data) <= 0)
    x = x->Left;
   else
    { y = x; x = x->Right; }

  return y;
 }

 Node^ BeforeEquals(T data)
 {
  Node^ y = Header;
  Node^ x = Root;

  while (x != nullptr)
  {
   int c = TComparer->Compare(data, ((SetNode<T>^)x)->Data);
   if (c == 0)
    { y = x; break; }
   else if (c < 0)
    x = x->Left;
   else
    { y = x; x = x->Right; }
  }

  return y;
 }

 void Bounds()
 {
  LeftMost = GetFirst();
  RightMost = GetLast();
 }

 void Copy(SetNode<T>^ CopyRoot)
 {
  if (Root != nullptr) Remove();
  if (CopyRoot != nullptr)
   {
     Copy(Header->Parent, CopyRoot, Header);
     LeftMost = GetFirst();
     RightMost = GetLast();
    }
 }

 void Copy(Node^% root, SetNode<T>^ CopyRoot, Node^ Parent)
 {
  root = gcnew SetNode<T>(TCloner->Clone(CopyRoot->Data), Parent);
  Nodes++;

  root->Balance = CopyRoot->Balance;

  if (CopyRoot->Left != nullptr)
   Copy(root->Left, (SetNode<T>^)CopyRoot->Left, (SetNode<T>^)root);

  if (CopyRoot->Right != nullptr)
   Copy(root->Right, (SetNode<T>^)CopyRoot->Right, (SetNode<T>^)root);

  Added(this, ((SetNode<T>^)root)->Data);
 }

 Node^ GetFirst()
 {
  if (Root == nullptr)
   return Header;

  else
   {
    Node^ search = Root;
    while (search->Left != nullptr) search = search->Left;
    return search;
   }
 }

 Node^ GetLast()
 {
  if (Root == nullptr)
   return Header;

  else
   {
    Node^ search = Root;
    while (search->Right != nullptr) search = search->Right;
    return search;
   }
 }

 void Import(SetNode<T>^ n)
 {
  if (n != nullptr) ImportTree(n);
 }

 void ImportTree(SetNode<T>^ n)
 {
  if (n->Left != nullptr) ImportTree((SetNode<T>^)n->Left);
  Add(n->Data, false);
  if (n->Right != nullptr) ImportTree((SetNode<T>^)n->Right);
 }

 void Notify(SetNode<T>^ root)
 {
  if (root != nullptr)
  {
   if (root->Left != nullptr)
    Notify((SetNode<T>^)root->Left);

   Added(this, root->Data);

   if (root->Right != nullptr)
    Notify((SetNode<T>^)root->Right);
  }
 }

 void Remove(Node^ root)
 {
  if (root->Left != nullptr && root->Right != nullptr)
  {
   Node^ replace = root->Left;
   while (replace->Right != nullptr) replace = replace->Right;
   SwapNodes(root, replace);
  }

  Node^ Parent = root->Parent;

  Direction From = (Parent->Left == root) ? Direction::FromLeft : Direction::FromRight;

  if (LeftMost == root)
  {
   Node^ n = NextItem(root);

   if (n->IsHeader)
    { LeftMost = Header; RightMost = Header; }
   else
    LeftMost = n;
  }
  else if (RightMost == root)
  {
    Node^ p = PreviousItem(root);

    if (p->IsHeader)
     { LeftMost = Header; RightMost = Header; }
    else
     RightMost = p;
  }

  if (root->Left == nullptr)
  {
   if (Parent == Header)
    Header->Parent = root->Right;
   else if (Parent->Left == root)
    Parent->Left = root->Right;
   else
    Parent->Right = root->Right;

   if (root->Right != nullptr) root->Right->Parent = Parent;
  }
  else
  {
   if (Parent == Header)
    Header->Parent = root->Left;
   else if (Parent->Left == root)
    Parent->Left = root->Left;
   else
    Parent->Right = root->Left;

   if (root->Left != nullptr) root->Left->Parent = Parent;
  }

  AdjustRemove(Parent, From);
  Nodes--;
  Removed(this, ((SetNode<T>^)root)->Data);
 }

 unsigned long long Remove(Node^ i, Node^ j)
 {
  if (i == LeftMost && j == Header)
   return Remove();
  else
   {
    unsigned long long count = 0;
    while (i != j)
    {
     SetEntry<T> iter(i); iter.MoveNext();
     if (i != Header) { Remove(i); count++; }
     i = iter._Node;
    }

    return count;
   }
 }

 void Update(SetNode<T>^ Node, T value)
 {
  if (TComparer->Compare(Node->Data, value) != 0) throw gcnew DifferentKeysException();
  T saved = Node->Data;
  Node->Data = value;
  Updated(this, saved, value);
 }

 void Validate(SetNode<T>^ root)
 {
  if (root == nullptr) return;

  if (root->Left != nullptr)
   {
    SetNode<T>^ Left = (SetNode<T>^)root->Left;

    if (TComparer->Compare(Left->Data, root->Data) >= 0)
     throw gcnew OutOfKeyOrderException();

    if (Left->Parent != root)
     throw gcnew TreeInvalidParentException();

    Validate((SetNode<T>^)root->Left);
   }

  if (root->Right != nullptr)
   {
    SetNode<T>^ Right = (SetNode<T>^)root->Right;

    if (TComparer->Compare(Right->Data, root->Data) <= 0)
     throw gcnew OutOfKeyOrderException();

    if (Right->Parent != root)
     throw gcnew TreeInvalidParentException();

    Validate((SetNode<T>^)root->Right);
   }

  unsigned long long DepthLeft = root->Left != nullptr ? Depth(root->Left) : 0;
  unsigned long long DepthRight = root->Right != nullptr ? Depth(root->Right) : 0;

  if (DepthLeft > DepthRight && DepthLeft - DepthRight > 2)
   throw gcnew TreeOutOfBalanceException();

  if (DepthLeft < DepthRight && DepthRight - DepthLeft > 2)
   throw gcnew TreeOutOfBalanceException();
 }

        //*** Static Methods

 static void CombineSets(Set<T>^ A,
                         Set<T>^ B,
                         Set<T>^ R,
                         SetOperation operation)
{
 System::Collections::Generic::IComparer<T>^ TComparer = R->TComparer;
 ISharp::ICloner<T>^ TCloner = R->TCloner;

 SetEntry<T> first1 = A->Begin;
 SetEntry<T> last1 = A->End;
 SetEntry<T> first2 = B->Begin;
 SetEntry<T> last2 = B->End;

            switch (operation)
            {
                case SetOperation::Union:
                    while (first1 != last1 && first2 != last2)
                    {
                        int order = TComparer->Compare(first1.Value, first2.Value);

                        if (order < 0)
                        {
                            R->Add(TCloner->Clone(first1.Value));
                            first1.MoveNext();
                        }

                        else if (order > 0)
                        {
                            R->Add(TCloner->Clone(first2.Value));
                            first2.MoveNext();
                        }

                        else
                        {
                            R->Add(TCloner->Clone(first1.Value));
                            first1.MoveNext();
                            first2.MoveNext();
                        }
                    }
                    while (first1 != last1)
                    {
                        R->Add(TCloner->Clone(first1.Value));
                        first1.MoveNext();
                    }
                    while (first2 != last2)
                    {
                        R->Add(TCloner->Clone(first2.Value));
                        first2.MoveNext();
                    }
                    return;

                case SetOperation::Intersection:
                    while (first1 != last1 && first2 != last2)
                    {
                        int order = TComparer->Compare(first1.Value, first2.Value);

                        if (order < 0)
                            first1.MoveNext();

                        else if (order > 0)
                            first2.MoveNext();

                        else
                        {
                            R->Add(TCloner->Clone(first1.Value));
                            first1.MoveNext();
                            first2.MoveNext();
                        }
                    }
                    return;

                case SetOperation::SymmetricDifference:
                    while (first1 != last1 && first2 != last2)
                    {
                        int order = TComparer->Compare(first1.Value, first2.Value);

                        if (order < 0)
                        {
                            R->Add(TCloner->Clone(first1.Value));
                            first1.MoveNext();
                        }

                        else if (order > 0)
                        {
                            R->Add(TCloner->Clone(first2.Value));
                            first2.MoveNext();
                        }

                        else
                        { first1.MoveNext(); first2.MoveNext(); }
                    }

                    while (first1 != last1)
                    {
                        R->Add(TCloner->Clone(first1.Value));
                        first1.MoveNext();
                    }

                    while (first2 != last2)
                    {
                        R->Add(TCloner->Clone(first2.Value));
                        first2.MoveNext();
                    }
                    return;

                case SetOperation::Difference:
                    while (first1 != last1 && first2 != last2)
                    {
                        int order = TComparer->Compare(first1.Value, first2.Value);

                        if (order < 0)
                        {
                            R->Add(TCloner->Clone(first1.Value));
                            first1.MoveNext();
                        }

                        else if (order > 0)
                        {
                            R->Add(TCloner->Clone(first1.Value));
                            first1.MoveNext();
                            first2.MoveNext();
                        }

                        else
                        { first1.MoveNext(); first2.MoveNext(); }
                    }

                    while (first1 != last1)
                    {
                        R->Add(TCloner->Clone(first1.Value));
                        first1.MoveNext();
                    }
                    return;
            }

            throw gcnew InvalidSetOperationException();
        }

        static Boolean CheckSets(Set<T>^ A,
                                 Set<T>^ B,
                                 SetOperation operation)
        {
            System::Collections::Generic::IComparer<T>^ TComparer = A->TComparer;

            SetEntry<T> first1 = A->Begin;
            SetEntry<T> last1 = A->End;
            SetEntry<T> first2 = B->Begin;
            SetEntry<T> last2 = B->End;

            switch (operation)
            {
                case SetOperation::Equality:
                case SetOperation::Inequality:
                    {
                        bool equals = true;

                        while (first1 != last1 && first2 != last2)
                        {
                            if (TComparer->Compare(first1.Value, first2.Value) == 0)
                            { first1.MoveNext(); first2.MoveNext(); }
                            else
                            { equals = false; break; }
                        }

                        if (equals)
                        {
                            if (first1 != last1) equals = false;
                            if (first2 != last2) equals = false;
                        }

                        if (operation == SetOperation::Equality)
                            return equals;
                        else
                            return !equals;
                    }

                case SetOperation::Subset:
                case SetOperation::Superset:
                    {
                        bool subset = true;

                        while (first1 != last1 && first2 != last2)
                        {
                            int order = TComparer->Compare(first1.Value, first2.Value);

                            if (order < 0)
                            { subset = false; break; }

                            else if (order > 0)
                                first2.MoveNext();

                            else
                            { first1.MoveNext(); first2.MoveNext(); }
                        }

                        if (subset)
                            if (first1 != last1) subset = false;

                        if (operation == SetOperation::Subset)
                            return subset;
                        else
                            return !subset;
                    }
            }

            throw gcnew InvalidSetOperationException();
        }

        static int CompareSets(Set<T>^ A,
                               Set<T>^ B)
        {
            System::Collections::Generic::IComparer<T>^ TComparer = A->TComparer;

            SetEntry<T> first1 = A->Begin;
            SetEntry<T> last1 = A->End;
            SetEntry<T> first2 = B->Begin;
            SetEntry<T> last2 = B->End;

            int Result = 0;

            while (first1 != last1 && first2 != last2)
            {
                Result = TComparer->Compare(first1.Value, first2.Value);
                if (Result == 0)
                { first1.MoveNext(); first2.MoveNext(); }
                else
                    return Result;
            }

            if (first1 != last1) return 1;
            if (first2 != last2) return -1;

            return 0;
        }
    };

}

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

Comparison to other structures[edit]

Both AVL trees and red–black trees are self-balancing binary search trees and they are very similar mathematically.^[5] 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 \geq 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}}$ ^[6]

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

External links[edit]

AVL tree demonstration (requires Flash).

References[edit]

↑ Georgy Adelson-Velsky, G.; Evgenii Landis (1962). "An algorithm for the organization of information". Proceedings of the USSR Academy of Sciences (in русский). 146: 263–266. English translation by Myron J. Ricci in Soviet Math. Doklady, 3:1259–1263, 1962.
↑ More precisely: if the AVL balance information is kept in the child nodes – with meaning "when going upward there is an additional increment in height", this can be done with one bit. Nevertheless, the modifying operations can be programmed more efficiently if the balance information can be checked with one test.
↑ Knuth, Donald E. (2000). Sorting and searching (2. ed., 6. printing, newly updated and rev. ed.). Boston [u.a.]: Addison-Wesley. p. 460. ISBN 0-201-89685-0. Search this book on
↑ Robert L. Kruse, Data Structures and Program Design, Prentice-Hally, 1987, ISBN 0-13-197146-8, page 353, chapter 9: Binary Trees.
↑ In fact, every AVL tree can be colored red–black.
↑ Red–black tree#Proof of asymptotic bounds

This article "AVL Trees in Managed 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.

[1] Georgy Adelson-Velsky, G.; Evgenii Landis (1962). "An algorithm for the organization of information". Proceedings of the USSR Academy of Sciences (in русский). 146: 263–266. English translation by Myron J. Ricci in Soviet Math. Doklady, 3:1259–1263, 1962.

[2] More precisely: if the AVL balance information is kept in the child nodes – with meaning "when going upward there is an additional increment in height", this can be done with one bit. Nevertheless, the modifying operations can be programmed more efficiently if the balance information can be checked with one test.

[3] Knuth, Donald E. (2000). Sorting and searching (2. ed., 6. printing, newly updated and rev. ed.). Boston [u.a.]: Addison-Wesley. p. 460. ISBN 0-201-89685-0. Search this book on

[4] Robert L. Kruse, Data Structures and Program Design, Prentice-Hally, 1987, ISBN 0-13-197146-8, page 353, chapter 9: Binary Trees.

[5] In fact, every AVL tree can be colored red–black.

[6] Red–black tree#Proof of asymptotic bounds

[1]

[2]

[3]

[4]

[5]

[6]

v t e Tree data structures
Search trees (dynamic sets/associative arrays)	2–3 2–3–4 AA (a,b) AVL B B+ B* B^x (Optimal) Binary search Dancing HTree Interval Order statistic (Left-leaning) Red–black Scapegoat Splay T Treap UB Weight-balanced
Heaps	Binary Binomial Brodal Fibonacci Leftist Pairing Skew van Emde Boas Weak
Tries	Ctrie C-trie (compressed ADT) Hash Radix Suffix Ternary search X-fast Y-fast
Spatial data partitioning trees	Ball BK BSP Cartesian Hilbert R k-d (implicit k-d) M Metric MVP Octree Priority R Quad R R+ R* Segment VP X
Other trees	Cover Exponential Fenwick Finger Fractal tree index Fusion Hash calendar iDistance K-ary Left-child right-sibling Link/cut Log-structured merge Merkle PQ Range SPQR Top

v t e Data structures
Types	Collection Container
Abstract	Associative array Multimap List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set
Arrays	Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix
Linked	Association list Linked list Skip list Unrolled linked list XOR linked list
Trees	B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree
Graphs	Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures