934 lines
73 KiB
MQL5
934 lines
73 KiB
MQL5
//+------------------------------------------------------------------+
|
|
//| 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);
|
|
}
|
|
//+------------------------------------------------------------------+
|