NUNA_FORK/Include/Generic/RedBlackTree.mqh

<EFBFBD><EFBFBD>//+------------------------------------------------------------------+
//|                                                 RedBlackTree.mqh |
//|                             Copyright 2000-2025, MetaQuotes Ltd. |
//|                                             https://www.mql5.com |
//+------------------------------------------------------------------+
#include <Generic\Interfaces\ICollection.mqh>
#include <Generic\Internal\DefaultComparer.mqh>
#include <Generic\Internal\ArrayFunction.mqh>
#include <Generic\Interfaces\IComparer.mqh>
#include "Stack.mqh"
//+------------------------------------------------------------------+
//| Enum ENUM_RED_BLACK_TREE_NODE_TYPE.                              |
//| Usage: Defines possible node colors for red black tree.          |
//+------------------------------------------------------------------+
enum ENUM_RED_BLACK_TREE_NODE_TYPE
  {
   RED_BLACK_TREE_NODE_RED=0,
   RED_BLACK_TREE_NODE_BLACK=1
  };
//+------------------------------------------------------------------+
//| Class CRedBlackTreeNode<T>.                                      |
//| Usage: Represents a node of red black tree.                      |
//+------------------------------------------------------------------+
template<typename T>
class CRedBlackTreeNode
  {
private:
   T                 m_value;
   CRedBlackTreeNode<T>*m_left;
   CRedBlackTreeNode<T>*m_right;
   CRedBlackTreeNode<T>*m_parent;
   ENUM_RED_BLACK_TREE_NODE_TYPE m_clr;

public:
                     CRedBlackTreeNode(void);
                     CRedBlackTreeNode(T value);
                    ~CRedBlackTreeNode(void);

   //--- methods of access to protected data
   T                 Value(void)                         { return(m_value);  }
   void              Value(T value)                      { m_value=value;    }
   CRedBlackTreeNode<T>   *Parent(void)                        { return(m_parent); }
   void              Parent(CRedBlackTreeNode<T>*node)         { m_parent=node;    }
   CRedBlackTreeNode<T>   *Left(void)                          { return(m_left);   }
   void              Left(CRedBlackTreeNode<T>*node)           { m_left=node;      }
   CRedBlackTreeNode<T>   *Right(void)                         { return(m_right);  }
   void              Right(CRedBlackTreeNode<T>*node)          { m_right=node;     }
   ENUM_RED_BLACK_TREE_NODE_TYPE Color(void)                     { return(m_clr);    }
   void              Color(ENUM_RED_BLACK_TREE_NODE_TYPE clr)    { m_clr=clr;        }
   //--- check node is empty 
   bool              IsLeaf(void);
   //--- create new empty node
   static            CRedBlackTreeNode<T>*CreateEmptyNode(void);
  };
//+------------------------------------------------------------------+
//| Initializes a new instance of the CRedBlackTreeNode<T> class that|
//| is empty.                                                        |
//+------------------------------------------------------------------+
template<typename T>
CRedBlackTreeNode::CRedBlackTreeNode(void) : m_clr(RED_BLACK_TREE_NODE_RED)
  {
  }
//+------------------------------------------------------------------+
//| Initializes a new instance of the CRedBlackTreeNode<T> class with|
//| specified value.                                                 |
//+------------------------------------------------------------------+
template<typename T>
CRedBlackTreeNode::CRedBlackTreeNode(T value)
  {
   m_value=value;
   m_clr=RED_BLACK_TREE_NODE_RED;
   m_left=CreateEmptyNode();
   m_right=CreateEmptyNode();
  }
//+------------------------------------------------------------------+
//| Destructor.                                                      |
//+------------------------------------------------------------------+
template<typename T>
CRedBlackTreeNode::~CRedBlackTreeNode(void)
  {
   if(CheckPointer(m_left)==POINTER_DYNAMIC)
      delete m_left;
   if(CheckPointer(m_right)==POINTER_DYNAMIC)
      delete m_right;
  }
//+------------------------------------------------------------------+
//| Check node is empty.                                             |
//+------------------------------------------------------------------+
template<typename T>
bool CRedBlackTreeNode::IsLeaf(void)
  {
   return(m_clr==RED_BLACK_TREE_NODE_BLACK &&
          CheckPointer(m_left)==POINTER_INVALID && 
          CheckPointer(m_right)==POINTER_INVALID);
  }
//+------------------------------------------------------------------+
//| Create new empty black node.                                     |
//+------------------------------------------------------------------+
template<typename T>
CRedBlackTreeNode<T>*CRedBlackTreeNode::CreateEmptyNode(void)
  {
   CRedBlackTreeNode<T>*new_node=new CRedBlackTreeNode<T>();
   new_node.m_clr=RED_BLACK_TREE_NODE_BLACK;
   new_node.m_parent=NULL;
   new_node.m_left=NULL;
   new_node.m_right=NULL;
//--- return new empty node
   return(new_node);
  }
//+------------------------------------------------------------------+
//| Class CRedBlackTree<T>.                                          |
//| Usage: A red black tree is a data structure which is a type of   |
//|        self-balancing binary search tree.                        |
//+------------------------------------------------------------------+
template<typename T>
class CRedBlackTree: public ICollection<T>
  {
protected:
   CRedBlackTreeNode<T>*m_root_node;
   CRedBlackTreeNode<T>*m_last_node;
   IComparer<T>*m_comparer;
   int               m_count;
   bool              m_delete_comparer;

public:
                     CRedBlackTree(void);
                     CRedBlackTree(IComparer<T>*comparer);
                     CRedBlackTree(ICollection<T>*collection);
                     CRedBlackTree(ICollection<T>*collection,IComparer<T>*comparer);
                     CRedBlackTree(T &array[]);
                     CRedBlackTree(T &array[],IComparer<T>*comparer);
                    ~CRedBlackTree(void);
   //--- methods of filling data 
   bool              Add(T value);
   //--- methods of access to protected data
   CRedBlackTreeNode<T>*Root(void)     { return(m_root_node); }
   int               Count(void)       { return(m_count);     }
   bool              Contains(T item);
   IComparer<T>     *Comparer(void) const { return(m_comparer); }
   bool              TryGetMin(T &min);
   bool              TryGetMax(T &max);
   //--- methods of copy data from collection   
   int               CopyTo(T &dst_array[],const int dst_start=0);
   //--- methods of cleaning and removing
   void              Clear(void);
   bool              Remove(T value);
   bool              Remove(CRedBlackTreeNode<T>*node);
   bool              RemoveMin(void);
   bool              RemoveMax(void);
   //--- method for searching
   CRedBlackTreeNode<T>*Find(T value);
   CRedBlackTreeNode<T>*FindMax(void);
   CRedBlackTreeNode<T>*FindMin(void);

private:
   void              RotateRight(CRedBlackTreeNode<T>*rotate_node);
   void              RotateLeft(CRedBlackTreeNode<T>*rotate_node);
   void              BalanceTreeAfterInsert(CRedBlackTreeNode<T>*insert_node);
   void              BalanceTreeAfterDelete(CRedBlackTreeNode<T>*linked_node);
   static void       WalkNextLevel(CRedBlackTreeNode<T>*node,T &array[],int &index);
  };
//+------------------------------------------------------------------+
//| Initializes a new instance of the CRedBlackTree<T> class that is |
//| empty and uses the specified comparer.                           |
//+------------------------------------------------------------------+
template<typename T>
CRedBlackTree::CRedBlackTree(void): m_count(0)
  {
//--- use default comaprer
   m_comparer=new CDefaultComparer<T>();
   m_delete_comparer=true;
  }
//+------------------------------------------------------------------+
//| Initializes a new instance of the CRedBlackTree<T> class that is |
//| empty and uses the specified comparer.                           |
//+------------------------------------------------------------------+
template<typename T>
CRedBlackTree::CRedBlackTree(IComparer<T>*comparer): m_count(0)
  {
//--- check comaprer
   if(CheckPointer(comparer)==POINTER_INVALID)
     {
      //--- use default comaprer
      m_comparer=new CDefaultComparer<T>();
      m_delete_comparer=true;
     }
   else
     {
      //--- use specified equality comaprer
      m_comparer=comparer;
      m_delete_comparer=false;
     }
  }
//+------------------------------------------------------------------+
//| Initializes a new instance of the CRedBlackTree<T> class that    |
//| uses the default equality comparer, contains elements copied from|
//| the specified collection.                                        |
//+------------------------------------------------------------------+
template<typename T>
CRedBlackTree::CRedBlackTree(ICollection<T>*collection): m_count(0)
  {
//--- use default comaprer
   m_comparer=new CDefaultComparer<T>();
   m_delete_comparer=true;
//--- check collection
   if(CheckPointer(collection)==POINTER_INVALID)
      return;
//--- copy all elements from specified collection to array
   T array[];
   int size=collection.CopyTo(array);
//--- fill red black tree by elements from the array
   for(int i=0; i<size; i++)
      Add(array[i]);
  }
//+------------------------------------------------------------------+
//| Initializes a new instance of the CRedBlackTree<T> class that    |
//| uses the specified comparer and contains elements  copied from   |
//| the specified collection.                                        |
//+------------------------------------------------------------------+
template<typename T>
CRedBlackTree::CRedBlackTree(ICollection<T>*collection,IComparer<T>*comparer): m_count(0)
  {
//--- check comaprer
   if(CheckPointer(comparer)==POINTER_INVALID)
     {
      //--- use default comaprer
      m_comparer=new CDefaultComparer<T>();
      m_delete_comparer=true;
     }
   else
     {
      //--- use specified equality comaprer
      m_comparer=comparer;
      m_delete_comparer=false;
     }
//--- check collection
   if(CheckPointer(collection)==POINTER_INVALID)
      return;
//--- copy all elements from specified collection to array
   T array[];
   int size=collection.CopyTo(array);
//--- fill red black tree by elements from the array
   for(int i=0; i<size; i++)
      Add(array[i]);
  }
//+------------------------------------------------------------------+
//| Initializes a new instance of the CRedBlackTree<T> class that    |
//| uses the default equality comparer and contains elements copied  |
//| from the specified array.                                        |
//+------------------------------------------------------------------+
template<typename T>
CRedBlackTree::CRedBlackTree(T &array[]): m_count(0)
  {
//--- use default comaprer
   m_comparer=new CDefaultComparer<T>();
   m_delete_comparer=true;
//--- fill red black tree by elements from the specified array
   for(int i=0; i<ArraySize(array); i++)
      Add(array[i]);
  }
//+------------------------------------------------------------------+
//| Initializes a new instance of the CRedBlackTree<T> class that    |
//| uses the specified comparer and contains elements  copied from   |
//| the specified array.                                             |
//+------------------------------------------------------------------+
template<typename T>
CRedBlackTree::CRedBlackTree(T &array[],IComparer<T>*comparer): m_count(0)
  {
//--- check comaprer
   if(CheckPointer(comparer)==POINTER_INVALID)
     {
      //--- use default comaprer
      m_comparer=new CDefaultComparer<T>();
      m_delete_comparer=true;
     }
   else
     {
      //--- use specified equality comaprer
      m_comparer=comparer;
      m_delete_comparer=false;
     }
//--- fill red black tree by elements from the specified array
   for(int i=0; i<ArraySize(array); i++)
      Add(array[i]);
  }
//+------------------------------------------------------------------+
//| Destructor.                                                      |
//+------------------------------------------------------------------+
template<typename T>
CRedBlackTree::~CRedBlackTree(void)
  {
//--- delete comparer
   if(m_delete_comparer)
      delete m_comparer;
//--- clear tree
   Clear();
  }
//+------------------------------------------------------------------+
//| Adds a new item to the tree. If the element already belongs to   |
//| this tree, no new element will be added.                         |
//+------------------------------------------------------------------+
template<typename T>
bool CRedBlackTree::Add(T value)
  {
//--- traverse tree - find node below
   if(CheckPointer(Find(value))!=POINTER_INVALID)
      return(false);
//--- create new node
   CRedBlackTreeNode<T>*new_node=new CRedBlackTreeNode<T>(value);
   CRedBlackTreeNode<T>*work_node=m_root_node;
   while(CheckPointer(work_node)!=POINTER_INVALID && !work_node.IsLeaf())
     {
      //--- find parent
      new_node.Parent(work_node);
      int result= m_comparer.Compare(value, work_node.Value());
      if(result == 0)
        {
         //--- node with same value already exists
         return(false);
        }
      work_node=(result>0 ? work_node.Right() : work_node.Left());
     }
//--- insert node into tree starting at parent's location
   if(CheckPointer(new_node.Parent())!=POINTER_INVALID)
     {
      if(m_comparer.Compare(new_node.Value(),new_node.Parent().Value())>0)
        {
         if(CheckPointer(new_node.Parent().Right())==POINTER_DYNAMIC && new_node.Parent().Right().IsLeaf())
            delete new_node.Parent().Right();
         new_node.Parent().Right(new_node);
        }
      else
        {
         if(CheckPointer(new_node.Parent().Left())==POINTER_DYNAMIC && new_node.Parent().Left().IsLeaf())
            delete new_node.Parent().Left();
         new_node.Parent().Left(new_node);
        }
     }
   else
     {
      //--- first node added
      m_root_node=new_node;
     }
//--- restore red-black properties
   BalanceTreeAfterInsert(new_node);
   m_last_node=new_node;
//--- increment count 
   m_count++;
   return(true);
  }
//+------------------------------------------------------------------+
//| Determines whether this tree contains the specified item.        |
//+------------------------------------------------------------------+
template<typename T>
bool CRedBlackTree::Contains(T item)
  {
   CRedBlackTreeNode<T>*tree_node=Find(item);
   return(CheckPointer(tree_node)!=POINTER_INVALID);
  }
//+------------------------------------------------------------------+
//| Finds the minimum element stored in the tree.                    |
//+------------------------------------------------------------------+
template<typename T>
bool CRedBlackTree::TryGetMin(T &min)
  {
   CRedBlackTreeNode<T>*work_node=m_root_node;
//--- check tree is empty
   if(CheckPointer(work_node)==POINTER_INVALID || work_node.IsLeaf())
      return(false);
//--- traverse to the extreme left to find the smallest key
   while(!work_node.Left().IsLeaf())
      work_node=work_node.Left();
//--- store min value
   m_last_node=work_node;
   min=work_node.Value();
   return(true);
  }
//+------------------------------------------------------------------+
//| Finds the maximum element stored in the tree.                    |
//+------------------------------------------------------------------+
template<typename T>
bool CRedBlackTree::TryGetMax(T &max)
  {
   CRedBlackTreeNode<T>*work_node=m_root_node;
//--- check tree is empty
   if(CheckPointer(work_node)==POINTER_INVALID || work_node.IsLeaf())
      return(false);
//--- traverse to the extreme right to find the largest key
   while(!work_node.Right().IsLeaf())
      work_node=work_node.Right();
//--- store max value
   m_last_node=work_node;
   max=work_node.Value();
   return(true);
  }
//+------------------------------------------------------------------+
//| Copies a range of elements from the tree to a compatible         |
//| one-dimensional array.                                           |
//+------------------------------------------------------------------+
template<typename T>
int CRedBlackTree::CopyTo(T &dst_array[],const int dst_start=0)
  {
//--- check root node
   if(CheckPointer(m_root_node)==POINTER_INVALID)
      return(0);
//--- resize array
   if(dst_start+m_count>ArraySize(dst_array))
      ArrayResize(dst_array,dst_start+m_count);
//--- start copy
   int index=dst_start;
   if(!m_root_node.IsLeaf())
     {
      //--- store all values in the stack
      WalkNextLevel(m_root_node,dst_array,index);
      //--- copy values from stack to array
      return(index-dst_start);
     }
   else
     {
      //--- tree is empty
      return(0);
     }
  }
//+------------------------------------------------------------------+
//| Removes all nodes from the tree.                                 |
//+------------------------------------------------------------------+
template<typename T>
void CRedBlackTree::Clear(void)
  {
//--- check count
   if(m_count>0)
     {
      //--- delete root node
      if(CheckPointer(m_root_node)==POINTER_DYNAMIC)
         delete m_root_node;
      //--- delete last node
      if(CheckPointer(m_last_node)==POINTER_DYNAMIC)
         delete m_last_node;
      m_count=0;
     }
  }
//+------------------------------------------------------------------+
//| Removes a node with specified value from the tree.               |
//+------------------------------------------------------------------+
template<typename T>
bool CRedBlackTree::Remove(T value)
  {
//--- try to find node with specified value
   CRedBlackTreeNode<T>*delete_node=Find(value);
   if(CheckPointer(delete_node)!=POINTER_INVALID)
      return Remove(delete_node);
   return(false);
  }
//+------------------------------------------------------------------+
//| Removes a node from the tree.                                    |
//| A node to be deleted will be:                                    |
//| 1. a leaf with no children                                       |
//| 2. have one child                                                |
//| 3. have two children                                             |
//| If the deleted node is red, the red black properties still hold. |
//| If the deleted node is black, the tree needs rebalancing.        |
//+------------------------------------------------------------------+
template<typename T>
bool CRedBlackTree::Remove(CRedBlackTreeNode<T>*delete_node)
  {
//--- check node
   if(CheckPointer(delete_node)==POINTER_INVALID)
      return(false);
//--- check delete node conatins in tree
   bool contains=false;
//--- walk of a tree and try to find the delete node
   CRedBlackTreeNode<T>*tree_node=m_root_node;
   while(CheckPointer(tree_node)!=POINTER_INVALID && !tree_node.IsLeaf())
     {
      //--- check specified node is delete node
      if(tree_node==delete_node)
        {
         contains=true;
         break;
        }
      else
        {
         //--- determine qual between specified node and delete node
         int result=m_comparer.Compare(delete_node.Value(),tree_node.Value());
         if(result>0)
            tree_node=tree_node.Right();  // walk of a right tree
         else
         if(result<0)
            tree_node=tree_node.Left();   // walk of a left tree
         else
            break;                        // values of nodes are equal, but delete node does not belong to this tree
        }
     }
//--- check delete node not belong to this tree
   if(!contains)
      return(false);
//--- work node
   CRedBlackTreeNode<T>*work_node;
//--- find the replacement node - the node one with at *most* one child. 
   if(delete_node.Left().IsLeaf() || delete_node.Right().IsLeaf())
     {
      work_node=delete_node;
     }
   else
     {
      //--- traverse right subtree
      work_node=delete_node.Right();
      //--- to find next node in sequence
      while(!work_node.Left().IsLeaf())
         work_node=work_node.Left();
     }
//--- at this point, work_node contains the replacement node. it's content will be copied to the valules in the node to be deleted
//--- linked_node is the node that will be linked to work_node's old parent. 
   CRedBlackTreeNode<T>*linked_node=(work_node.Left().IsLeaf() ? work_node.Right() : work_node.Left());
//--- replace linked_node's parent with work_node's parent and 
//--- link linked_node to proper subtree in parent
//--- this removes work_node from the chain
   linked_node.Parent(work_node.Parent());
   if(CheckPointer(work_node.Parent())!=POINTER_INVALID)
     {
      if(work_node==work_node.Parent().Left())
         work_node.Parent().Left(linked_node);
      else
         work_node.Parent().Right(linked_node);
     }
   else
     {
      //--- make linked_node the root node
      m_root_node=linked_node;
     }
//--- copy the values from work_node (the replacement node) to the node being deleted.
   if(work_node!=delete_node)
      delete_node.Value(work_node.Value());
//--- restore red-black properties
   if(work_node.Color()==RED_BLACK_TREE_NODE_BLACK)
      BalanceTreeAfterDelete(linked_node);
//--- delete node
   if(m_count>1)
     {
      if(linked_node==work_node.Left())
         work_node.Left(NULL);
      else
         work_node.Right(NULL);
     }
   delete work_node;
//--- decrement count
   m_count--;
   return(true);
  }
//+------------------------------------------------------------------+
//| Removes a node with minimum value from the tree.                 |
//+------------------------------------------------------------------+
template<typename T>
bool CRedBlackTree::RemoveMin(void)
  {
//--- check root node
   if(CheckPointer(m_root_node)==POINTER_INVALID)
      return(false);
//--- find and remove node with minimum value
   return Remove(FindMin());
  }
//+------------------------------------------------------------------+
//| Removes a node with maximum value from the tree.                 |
//+------------------------------------------------------------------+
template<typename T>
bool CRedBlackTree::RemoveMax(void)
  {
//--- check root node
   if(CheckPointer(m_root_node)==POINTER_INVALID)
      return(false);
//--- find and remove node with maximum value
   return Remove(FindMax());
  }
//+------------------------------------------------------------------+
//| Attempts to find a node that contains the specified value.       |
//+------------------------------------------------------------------+
template<typename T>
CRedBlackTreeNode<T>*CRedBlackTree::Find(T value)
  {
   int result;
//--- check last node 
   if(CheckPointer(m_last_node)!=POINTER_INVALID && !m_last_node.IsLeaf())
     {
      result=m_comparer.Compare(value,m_last_node.Value());
      if(result==0)
         return(m_last_node);
     }
//--- begin at root
   CRedBlackTreeNode<T>*tree_node=m_root_node;
//--- traverse tree until node is found
   while(CheckPointer(tree_node)!=POINTER_INVALID && !tree_node.IsLeaf())
     {
      result=m_comparer.Compare(value,tree_node.Value());
      if(result==0)
        {
         m_last_node=tree_node;
         return(tree_node);
        }
      tree_node=(result<0 ? tree_node.Left() : tree_node.Right());
     }
   return(NULL);
  }
//+------------------------------------------------------------------+
//| Attempts to find a node that contains the minimum value.         |
//+------------------------------------------------------------------+
template<typename T>
CRedBlackTreeNode<T>*CRedBlackTree::FindMin(void)
  {
   CRedBlackTreeNode<T>*work_node=m_root_node;
//--- check tree is empty
   if(CheckPointer(work_node)==POINTER_INVALID || work_node.IsLeaf())
      return(NULL);
//--- traverse to the extreme left to find the smallest key
   while(!work_node.Left().IsLeaf())
      work_node=work_node.Left();
//--- store min value
   m_last_node=work_node;
   return(work_node);
  }
//+------------------------------------------------------------------+
//| Attempts to find a node that contains the maximum value.         |
//+------------------------------------------------------------------+
template<typename T>
CRedBlackTreeNode<T>*CRedBlackTree::FindMax(void)
  {
   CRedBlackTreeNode<T>*work_node=m_root_node;
//--- check tree is empty
   if(CheckPointer(work_node)==POINTER_INVALID || work_node.IsLeaf())
      return(NULL);
//--- traverse to the extreme right to find the largest key
   while(!work_node.Right().IsLeaf())
      work_node=work_node.Right();
//--- store max value
   m_last_node=work_node;
   return(work_node);
  }
//+------------------------------------------------------------------+
//| Pushing node rotate_node down and to the right to balance the    |
//| tree. rotate_node's Left child (work_node) replaces rotate_node  |
//| (since rotate_node < work_node), and work_node's Right child     |
//| becomes rotate_node's Left child (since it's < rotate_node but > |
//| work_node).                                                      |
//+------------------------------------------------------------------+
template<typename T>
void CRedBlackTree::RotateRight(CRedBlackTreeNode<T>*rotate_node)
  {
//--- get rotate_node's Left node, this becomes work_node
   CRedBlackTreeNode<T>*work_node=rotate_node.Left();
//--- set rotate_node's Right link
//--- work_node's Right child becomes rotate_node's Left child
   rotate_node.Left(work_node.Right());
//--- modify parents
   if(!work_node.Right().IsLeaf())
     {
      //--- sets work_node's Right Parent to rotate_node
      work_node.Right().Parent(rotate_node);
     }
   if(!work_node.IsLeaf())
     {
      //--- set work_node's Parent to rotate_node's Parent
      work_node.Parent(rotate_node.Parent());
     }
   if(CheckPointer(rotate_node.Parent())!=POINTER_INVALID)
     {
      //--- determine which side of it's Parent rotate_node was on
      if(rotate_node==rotate_node.Parent().Right())
        {
         //--- set Right Parent to work_node
         rotate_node.Parent().Right(work_node);
        }
      else
        {
         //--- set Left Parent to work_node
         rotate_node.Parent().Left(work_node);
        }
     }
   else
     {
      m_root_node=work_node;
     }
//--- link rotate_node and work_node 
//--- put rotate_node on work_node's Right
   work_node.Right(rotate_node);
//--- set work_node as rotate_node's Parent
   if(!rotate_node.IsLeaf())
      rotate_node.Parent(work_node);
  }
//+------------------------------------------------------------------+
//| Pushing node rotate_node down and to the Left to balance the     |
//| tree. rotate_node's Right child (work_node) replaces rotate_node |
//| (since work_node > rotate_node), and work_node's Left child      |
//| becomes rotate_node's Right child (since it's < work_node but >  |
//| rotate_node).                                                    |
//+------------------------------------------------------------------+
template<typename T>
void CRedBlackTree::RotateLeft(CRedBlackTreeNode<T>*rotate_node)
  {
//--- get rotate_node's Right node, this becomes work_node
   CRedBlackTreeNode<T>*work_node=rotate_node.Right();
//--- set rotate_node's Right link
//--- work_node's Left child's becomes rotate_node's Right child
   rotate_node.Right(work_node.Left());
//--- modify parents
   if(!work_node.Left().IsLeaf())
     {
      //--- sets work_node's Left Parent to rotate_node
      work_node.Left().Parent(rotate_node);
     }
   if(!work_node.IsLeaf())
     {
      //--- set work_node's Parent to rotate_node's Parent
      work_node.Parent(rotate_node.Parent());
     }
   if(CheckPointer(rotate_node.Parent())!=POINTER_INVALID)
     {
      //--- determine which side of it's Parent rotate_node was on
      if(rotate_node==rotate_node.Parent().Left())
        {
         //--- set Left Parent to work_node
         rotate_node.Parent().Left(work_node);
        }
      else
        {
         //--- set Right Parent to work_node
         rotate_node.Parent().Right(work_node);
        }
     }
   else
     {
      m_root_node=work_node;
     }

//--- link rotate_node and work_node
//--- put rotate_node on work_node's Left
   work_node.Left(rotate_node);
//--- set work_node as rotate_node's Parent
   if(!rotate_node.IsLeaf())
      rotate_node.Parent(work_node);
  }
//+------------------------------------------------------------------+
//| Additions to red-black trees usually destroy the red-black       |
//| properties. Examine the tree and restore. Rotations are normally |
//| required to restore it.                                          |
//+------------------------------------------------------------------+
template<typename T>
void CRedBlackTree::BalanceTreeAfterInsert(CRedBlackTreeNode<T>*insert_node)
  {
//--- maintain red-black tree properties after adding new node
   while(insert_node!=m_root_node && insert_node.Parent().Color()==RED_BLACK_TREE_NODE_RED)
     {
      //--- parent node is colored red
      CRedBlackTreeNode<T>*work_node;
      //--- determine traversal path			
      if(insert_node.Parent()==insert_node.Parent().Parent().Left())
        {
         //--- get rigth uncle
         work_node=insert_node.Parent().Parent().Right();
         if(CheckPointer(work_node)!=POINTER_INVALID && work_node.Color()==RED_BLACK_TREE_NODE_RED)
           {
            //--- uncle is red
            //--- change parent and uncle to black
            insert_node.Parent().Color(RED_BLACK_TREE_NODE_BLACK);
            work_node.Color(RED_BLACK_TREE_NODE_BLACK);
            //--- grandparent must be red
            insert_node.Parent().Parent().Color(RED_BLACK_TREE_NODE_RED);
            //--- continue loop with grandparent
            insert_node=insert_node.Parent().Parent();
           }
         else
           {
            //--- uncle is black
            //--- determine if new node is greater than parent
            if(insert_node==insert_node.Parent().Right())
              {
               //--- new node is greater than parent
               insert_node=insert_node.Parent();
               RotateLeft(insert_node);
              }
            //--- new node is less than parent
            insert_node.Parent().Color(RED_BLACK_TREE_NODE_BLACK);
            insert_node.Parent().Parent().Color(RED_BLACK_TREE_NODE_RED);
            RotateRight(insert_node.Parent().Parent());
           }
        }
      else
        {
         //--- get left uncle
         work_node=insert_node.Parent().Parent().Left();
         if(CheckPointer(work_node)!=POINTER_INVALID && work_node.Color()==RED_BLACK_TREE_NODE_RED)
           {
            //--- uncle is red
            //--- change parent and uncle to black
            insert_node.Parent().Color(RED_BLACK_TREE_NODE_BLACK);
            work_node.Color(RED_BLACK_TREE_NODE_BLACK);
            //--- grandparent must be red
            insert_node.Parent().Parent().Color(RED_BLACK_TREE_NODE_RED);
            //--- continue loop with grandparent
            insert_node=insert_node.Parent().Parent();
           }
         else
           {
            //--- uncle is black
            //--- determine if new node is greater than parent
            if(insert_node==insert_node.Parent().Left())
              {
               //--- new node is greater than parent
               insert_node=insert_node.Parent();
               RotateRight(insert_node);
              }
            //--- new node is less than parent
            insert_node.Parent().Color(RED_BLACK_TREE_NODE_BLACK);
            insert_node.Parent().Parent().Color(RED_BLACK_TREE_NODE_RED);
            RotateLeft(insert_node.Parent().Parent());
           }
        }
     }
//--- root should always be black
   m_root_node.Color(RED_BLACK_TREE_NODE_BLACK);
  }
//+------------------------------------------------------------------+
//| Deletions from red-black trees may destroy the red-black         |
//| properties. Examine the tree and restore. Rotations are normally |
//| required to restore it.                                          |
//+------------------------------------------------------------------+
template<typename T>
void CRedBlackTree::BalanceTreeAfterDelete(CRedBlackTreeNode<T>*linked_node)
  {
//--- maintain Red-Black tree balance after deleting node
   while(linked_node!=m_root_node && linked_node.Color()==RED_BLACK_TREE_NODE_BLACK)
     {
      CRedBlackTreeNode<T>*work_node;
      //--- determine traversal path
      if(linked_node==linked_node.Parent().Left())
        {
         //--- work node is delete node sibling
         work_node=linked_node.Parent().Right();
         if(work_node.Color()==RED_BLACK_TREE_NODE_RED)
           {
            //--- delete node is black, work node is red - make both black and rotate
            linked_node.Parent().Color(RED_BLACK_TREE_NODE_RED);
            work_node.Color(RED_BLACK_TREE_NODE_BLACK);
            RotateLeft(linked_node.Parent());
            work_node=linked_node.Parent().Right();
           }
         //--- check work node is not leaf
         if(work_node.IsLeaf())
            return;
         if(work_node.Left().Color()==RED_BLACK_TREE_NODE_BLACK && 
            work_node.Right().Color()==RED_BLACK_TREE_NODE_BLACK)
           {
            //--- children are both black
            //--- change parent to red
            work_node.Color(RED_BLACK_TREE_NODE_RED);
            //--- move up the tree
            linked_node=linked_node.Parent();
           }
         else
           {
            if(work_node.Right().Color()==RED_BLACK_TREE_NODE_BLACK)
              {
               work_node.Left().Color(RED_BLACK_TREE_NODE_BLACK);
               work_node.Color(RED_BLACK_TREE_NODE_RED);
               RotateRight(work_node);
               work_node=linked_node.Parent().Right();
              }
            work_node.Color(linked_node.Parent().Color());
            linked_node.Parent().Color(RED_BLACK_TREE_NODE_BLACK);
            work_node.Right().Color(RED_BLACK_TREE_NODE_BLACK);
            RotateLeft(linked_node.Parent());
            linked_node=m_root_node;
           }
        }
      else
        {
         //--- work node is delete node sibling
         work_node=linked_node.Parent().Left();
         if(work_node.Color()==RED_BLACK_TREE_NODE_RED)
           {
            //--- delete node is black, work node is red - make both black and rotate
            linked_node.Parent().Color(RED_BLACK_TREE_NODE_RED);
            work_node.Color(RED_BLACK_TREE_NODE_BLACK);
            RotateRight(linked_node.Parent());
            work_node=linked_node.Parent().Left();
           }
         //--- check work node is not leaf
         if(work_node.IsLeaf())
            return;
         if(work_node.Right().Color()==RED_BLACK_TREE_NODE_BLACK && 
            work_node.Left().Color()==RED_BLACK_TREE_NODE_BLACK)
           {
            //--- children are both black
            //--- change parent to red
            work_node.Color(RED_BLACK_TREE_NODE_RED);
            //--- move up the tree
            linked_node=linked_node.Parent();
           }
         else
           {
            if(work_node.Left().Color()==RED_BLACK_TREE_NODE_BLACK)
              {
               work_node.Right().Color(RED_BLACK_TREE_NODE_BLACK);
               work_node.Color(RED_BLACK_TREE_NODE_RED);
               RotateLeft(work_node);
               work_node=linked_node.Parent().Left();
              }
            work_node.Color(linked_node.Parent().Color());
            linked_node.Parent().Color(RED_BLACK_TREE_NODE_BLACK);
            work_node.Left().Color(RED_BLACK_TREE_NODE_BLACK);
            RotateRight(linked_node.Parent());
            linked_node=m_root_node;
           }
        }
     }
   linked_node.Color(RED_BLACK_TREE_NODE_BLACK);
  }
//+------------------------------------------------------------------+
//| Recursive walk of a tree.                                        |
//+------------------------------------------------------------------+
template<typename T>
void CRedBlackTree::WalkNextLevel(CRedBlackTreeNode<T>*node,T &array[],int &index)
  {
//--- walk of a left subtree
   if(!node.Left().IsLeaf())
      WalkNextLevel(node.Left(),array,index);
//--- chech index
   if(index>=ArraySize(array))
      return;
//--- store value in the array
   array[index++]=node.Value();
//--- walk of a right subtree
   if(!node.Right().IsLeaf())
      WalkNextLevel(node.Right(),array,index);
  }
//+------------------------------------------------------------------+