AVL tree/C++

From Rosetta Code
< AVL tree
Revision as of 11:09, 19 May 2018 by Thundergnat (talk | contribs) (Reverted edits by Goee (talk) to last revision by NNcNannara)

Code

<lang cpp> // The set template is the primary class of AVL Trees. // The system is set up to add templates including tree and map.

  1. include<iostream>

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

struct State 

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

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

};

struct Direction { 

enum {FromLeft, FromRight};

};

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;

}

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;

}

struct setOperation { 

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

};

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

template<class T> struct setNode : public Node { 

T Element;

setNode(const T& ElementSet,
        Node* Parent) : Node(Parent), Element(ElementSet) {}

operator T&() {return Element;}

};

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

};

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;

}

void main() { 

try
 {
  set<double> s;

  //*** Build the Set

  for (int i=0; i<10; i++) s << i+.5;

  //*** Print the set using iterators

  std::cout << "{";

  set<double>::iterator last = s.last();

  for (set<double>::iterator x = s.begin(); x != s.end(); ++x)
   {
       std::cout << *x;
       if (x != last) std::cout << ",";
   }

  std::cout << "}\n";

  //*** Print the set using stream output operator

  std::cout << s << "\n";

  //*** Print the set using for each

  std::cout << "{";

  for each (double d in s)
   {
       std::cout << d;
       if (d != *last) std::cout << ",";
   }

  std::cout << "}\n";
 }
catch (treeException) {std::cout << "A Tree Exception Occurred.\n";}

} </lang>

Retrieved from "https://rosettacode.org/wiki/AVL_tree/C%2B%2B?oldid=268997"