415 lines
14 KiB
MQL5
415 lines
14 KiB
MQL5
 | //+------------------------------------------------------------------+
| ||
//| Tree.mqh |
| |||
//| Copyright 2000-2025, MetaQuotes Ltd. |
| |||
//| https://www.mql5.com |
| |||
//+------------------------------------------------------------------+
| |||
#include "TreeNode.mqh"
| |||
//+------------------------------------------------------------------+
| |||
//| Class CTree. |
| |||
//| Purpose: Building a binary tree of instances of CTreeNode class |
| |||
//| and its derviatives. |
| |||
//| Derives from class CTreeNode. |
| |||
//+------------------------------------------------------------------+
| |||
class CTree : public CTreeNode
| |||
{
| |||
protected:
| |||
CTreeNode *m_root_node; // root node of the tree
| |||
| |||
public:
| |||
CTree(void);
| |||
~CTree(void);
| |||
//--- methods of access to protected data
| |||
CTreeNode *Root(void) const { return(m_root_node); }
| |||
//--- method of identifying the object
| |||
virtual int Type() const { return(0x9999); }
| |||
//--- method of filling the tree
| |||
CTreeNode *Insert(CTreeNode *new_node);
| |||
//--- methods of removing tree nodes
| |||
bool Detach(CTreeNode *node);
| |||
bool Delete(CTreeNode *node);
| |||
void Clear(void);
| |||
//--- method of searching data in the tree
| |||
CTreeNode *Find(const CTreeNode *node);
| |||
//--- method to create elements in the tree
| |||
virtual CTreeNode *CreateElement() { return(NULL); }
| |||
//--- methods for working with files
| |||
virtual bool Save(const int file_handle);
| |||
virtual bool Load(const int file_handle);
| |||
| |||
protected:
| |||
void Balance(CTreeNode *node);
| |||
};
| |||
//+------------------------------------------------------------------+
| |||
//| Constructor |
| |||
//+------------------------------------------------------------------+
| |||
CTree::CTree(void) : m_root_node(NULL)
| |||
{
| |||
}
| |||
//+------------------------------------------------------------------+
| |||
//| Destructor |
| |||
//+------------------------------------------------------------------+
| |||
CTree::~CTree(void)
| |||
{
| |||
Clear();
| |||
}
| |||
//+------------------------------------------------------------------+
| |||
//| Method of adding a node to the tree |
| |||
//+------------------------------------------------------------------+
| |||
CTreeNode *CTree::Insert(CTreeNode *new_node)
| |||
{
| |||
CTreeNode *p_node;
| |||
CTreeNode *result=m_root_node;
| |||
//--- check
| |||
if(!CheckPointer(new_node))
| |||
return(NULL);
| |||
//--- add
| |||
if(result!=NULL)
| |||
{
| |||
p_node=NULL;
| |||
result=m_root_node;
| |||
while(result!=NULL && result.Compare(new_node)!=0)
| |||
{
| |||
p_node=result;
| |||
result=result.GetNext(new_node);
| |||
}
| |||
if(result!=NULL)
| |||
return(result);
| |||
if(p_node.Compare(new_node)>0)
| |||
p_node.Left(new_node);
| |||
else
| |||
p_node.Right(new_node);
| |||
new_node.Parent(p_node);
| |||
Balance(p_node);
| |||
}
| |||
else
| |||
m_root_node=new_node;
| |||
//--- result
| |||
return(result);
| |||
}
| |||
//+------------------------------------------------------------------+
| |||
//| Method of removing a node from the tree |
| |||
//+------------------------------------------------------------------+
| |||
bool CTree::Delete(CTreeNode *node)
| |||
{
| |||
//--- check
| |||
if(!CheckPointer(node))
| |||
return(false);
| |||
//--- delete
| |||
if(Detach(node) && CheckPointer(node)==POINTER_DYNAMIC)
| |||
delete node;
| |||
//--- successful
| |||
return(true);
| |||
}
| |||
//+------------------------------------------------------------------+
| |||
//| Method of detaching node from the tree |
| |||
//+------------------------------------------------------------------+
| |||
bool CTree::Detach(CTreeNode *node)
| |||
{
| |||
CTreeNode *curr_node,*tmp_node;
| |||
CTreeNode *nodeA,*nodeB;
| |||
//--- check
| |||
curr_node=node;
| |||
if(!CheckPointer(curr_node))
| |||
return(false);
| |||
//--- detach
| |||
if(curr_node.BalanceL()>curr_node.BalanceR())
| |||
{
| |||
nodeA=curr_node.Left();
| |||
while(nodeA.Right()!=NULL)
| |||
nodeA=nodeA.Right();
| |||
nodeB=nodeA.Parent();
| |||
if(nodeB!=curr_node)
| |||
{
| |||
nodeB.Right(nodeA.Left());
| |||
tmp_node=nodeB.Right();
| |||
if(tmp_node!=NULL)
| |||
tmp_node.Parent(nodeB);
| |||
tmp_node=curr_node.Left();
| |||
nodeA.Left(tmp_node);
| |||
tmp_node.Parent(nodeA);
| |||
}
| |||
//--- left link of curr_node is already installed as it should be
| |||
curr_node.Left(NULL);
| |||
//--- transferring the right link of curr_node to nodeA
| |||
nodeA.Right(curr_node.Right());
| |||
tmp_node=curr_node.Right();
| |||
if(tmp_node!=NULL)
| |||
tmp_node.Parent(nodeA);
| |||
curr_node.Right(NULL);
| |||
//--- transferring the root link of curr_node to nodeA
| |||
tmp_node=curr_node.Parent();
| |||
nodeA.Parent(tmp_node);
| |||
if(tmp_node!=NULL)
| |||
{
| |||
if(tmp_node.Left()==curr_node)
| |||
tmp_node.Left(nodeA);
| |||
else
| |||
tmp_node.Right(nodeA);
| |||
}
| |||
else
| |||
{
| |||
curr_node.Parent(NULL);
| |||
m_root_node=nodeA;
| |||
tmp_node=nodeA;
| |||
}
| |||
Balance(tmp_node);
| |||
}
| |||
else
| |||
{
| |||
if(curr_node.BalanceR()>0)
| |||
{
| |||
nodeA=curr_node.Right();
| |||
while(nodeA.Left()!=NULL)
| |||
nodeA=nodeA.Left();
| |||
nodeB=nodeA.Parent();
| |||
if(nodeB!=curr_node)
| |||
{
| |||
nodeB.Left(nodeA.Right());
| |||
tmp_node=nodeB.Left();
| |||
if(tmp_node!=NULL)
| |||
tmp_node.Parent(nodeB);
| |||
tmp_node=curr_node.Right();
| |||
nodeA.Right(tmp_node);
| |||
tmp_node.Parent(nodeA);
| |||
}
| |||
//--- right link of curr_node is already installed as it should be
| |||
curr_node.Right(NULL);
| |||
//--- transferring the left link of curr_node to nodeA
| |||
nodeA.Left(curr_node.Left());
| |||
tmp_node=curr_node.Left();
| |||
if(tmp_node!=NULL)
| |||
tmp_node.Parent(nodeA);
| |||
curr_node.Left(NULL);
| |||
//--- transferring the root link of curr_node to nodeA
| |||
tmp_node=curr_node.Parent();
| |||
nodeA.Parent(tmp_node);
| |||
if(tmp_node!=NULL)
| |||
{
| |||
if(tmp_node.Left()==curr_node)
| |||
tmp_node.Left(nodeA);
| |||
else
| |||
tmp_node.Right(nodeA);
| |||
}
| |||
else
| |||
{
| |||
curr_node.Parent(NULL);
| |||
m_root_node=nodeA;
| |||
tmp_node=nodeA;
| |||
}
| |||
Balance(tmp_node);
| |||
}
| |||
else
| |||
{
| |||
//--- node list
| |||
if(curr_node.Parent()==NULL)
| |||
m_root_node=NULL;
| |||
else
| |||
{
| |||
tmp_node=curr_node.Parent();
| |||
if(tmp_node.Left()==curr_node)
| |||
tmp_node.Left(NULL);
| |||
else
| |||
tmp_node.Right(NULL);
| |||
curr_node.Parent(NULL);
| |||
}
| |||
Balance(curr_node.Parent());
| |||
}
| |||
}
| |||
//--- successful
| |||
return(true);
| |||
}
| |||
//+------------------------------------------------------------------+
| |||
//| Method of cleaning the tree |
| |||
//+------------------------------------------------------------------+
| |||
void CTree::Clear(void)
| |||
{
| |||
if(CheckPointer(m_root_node)==POINTER_DYNAMIC)
| |||
delete m_root_node;
| |||
m_root_node=NULL;
| |||
}
| |||
//+------------------------------------------------------------------+
| |||
//| Method of searching for a node in the tree |
| |||
//+------------------------------------------------------------------+
| |||
CTreeNode *CTree::Find(const CTreeNode *node)
| |||
{
| |||
CTreeNode *result=m_root_node;
| |||
//--- find
| |||
while(result!=NULL && result.Compare(node)!=0)
| |||
result=result.GetNext(node);
| |||
//--- result
| |||
return(result);
| |||
}
| |||
//+------------------------------------------------------------------+
| |||
//| Method of balancing the tree |
| |||
//+------------------------------------------------------------------+
| |||
void CTree::Balance(CTreeNode *node)
| |||
{
| |||
CTreeNode *nodeA,*nodeB,*nodeC,*curr_node,*tmp_node;
| |||
//---
| |||
curr_node=node;
| |||
while(curr_node!=NULL)
| |||
{
| |||
curr_node.RefreshBalance();
| |||
if(MathAbs(curr_node.BalanceL()-curr_node.BalanceR())<=1)
| |||
curr_node=curr_node.Parent();
| |||
else
| |||
{
| |||
if(curr_node.BalanceR()>curr_node.BalanceL())
| |||
{
| |||
//--- rotation to the right
| |||
tmp_node=curr_node.Right();
| |||
if(tmp_node.BalanceL()>tmp_node.BalanceR())
| |||
{
| |||
//--- great rotation to the right
| |||
nodeA=curr_node;
| |||
nodeB=nodeA.Right();
| |||
nodeC=nodeB.Left();
| |||
nodeC.Parent(nodeA.Parent());
| |||
tmp_node=nodeC.Parent();
| |||
if(tmp_node!=NULL)
| |||
{
| |||
if(tmp_node.Right()==nodeA)
| |||
tmp_node.Right(nodeC);
| |||
else
| |||
tmp_node.Left(nodeC);
| |||
}
| |||
else
| |||
m_root_node=nodeC;
| |||
nodeA.Parent(nodeC);
| |||
nodeB.Parent(nodeC);
| |||
nodeA.Right(nodeC.Left());
| |||
tmp_node=nodeA.Right();
| |||
if(tmp_node!=NULL)
| |||
tmp_node.Parent(nodeA);
| |||
nodeC.Left(nodeA);
| |||
nodeB.Left(nodeC.Right());
| |||
tmp_node=nodeB.Left();
| |||
if(tmp_node!=NULL)
| |||
tmp_node.Parent(nodeB);
| |||
nodeC.Right(nodeB);
| |||
if(m_root_node==nodeA)
| |||
m_root_node=nodeC;
| |||
curr_node=nodeC.Parent();
| |||
}
| |||
else
| |||
{
| |||
//--- slight rotation to the right
| |||
nodeA=curr_node;
| |||
nodeB=nodeA.Right();
| |||
nodeB.Parent(nodeA.Parent());
| |||
tmp_node=nodeB.Parent();
| |||
if(tmp_node!=NULL)
| |||
{
| |||
if(tmp_node.Right()==nodeA)
| |||
tmp_node.Right(nodeB);
| |||
else
| |||
tmp_node.Left(nodeB);
| |||
}
| |||
else
| |||
m_root_node=nodeB;
| |||
nodeA.Parent(nodeB);
| |||
nodeA.Right(nodeB.Left());
| |||
tmp_node=nodeA.Right();
| |||
if(tmp_node!=NULL)
| |||
tmp_node.Parent(nodeA);
| |||
nodeB.Left(nodeA);
| |||
if(m_root_node==nodeA)
| |||
m_root_node=nodeB;
| |||
curr_node=nodeB.Parent();
| |||
}
| |||
}
| |||
else
| |||
{
| |||
//--- rotation to the left
| |||
tmp_node=curr_node.Left();
| |||
if(tmp_node.BalanceR()>tmp_node.BalanceL())
| |||
{
| |||
//--- great rotation to the left
| |||
nodeA=curr_node;
| |||
nodeB=nodeA.Left();
| |||
nodeC=nodeB.Right();
| |||
nodeC.Parent(nodeA.Parent());
| |||
tmp_node=nodeC.Parent();
| |||
if(tmp_node!=NULL)
| |||
{
| |||
if(tmp_node.Right()==nodeA)
| |||
tmp_node.Right(nodeC);
| |||
else
| |||
tmp_node.Left(nodeC);
| |||
}
| |||
else
| |||
m_root_node=nodeC;
| |||
nodeA.Parent(nodeC);
| |||
nodeB.Parent(nodeC);
| |||
nodeA.Left(nodeC.Right());
| |||
tmp_node=nodeA.Left();
| |||
if(tmp_node!=NULL)
| |||
tmp_node.Parent(nodeA);
| |||
nodeC.Right(nodeA);
| |||
nodeB.Right(nodeC.Left());
| |||
tmp_node=nodeB.Right();
| |||
if(tmp_node!=NULL)
| |||
tmp_node.Parent(nodeB);
| |||
nodeC.Left(nodeB);
| |||
if(m_root_node==nodeA)
| |||
m_root_node=nodeC;
| |||
curr_node=nodeC.Parent();
| |||
}
| |||
else
| |||
{
| |||
//--- small rotation to the left
| |||
nodeA=curr_node;
| |||
nodeB=nodeA.Left();
| |||
nodeB.Parent(nodeA.Parent());
| |||
tmp_node=nodeB.Parent();
| |||
if(tmp_node!=NULL)
| |||
{
| |||
if(tmp_node.Right()==nodeA)
| |||
tmp_node.Right(nodeB);
| |||
else
| |||
tmp_node.Left(nodeB);
| |||
}
| |||
else
| |||
m_root_node=nodeB;
| |||
nodeA.Parent(nodeB);
| |||
nodeA.Left(nodeB.Right());
| |||
tmp_node=nodeA.Left();
| |||
if(tmp_node!=NULL)
| |||
tmp_node.Parent(nodeA);
| |||
nodeB.Right(nodeA);
| |||
if(m_root_node==nodeA)
| |||
m_root_node=nodeB;
| |||
curr_node=nodeB.Parent();
| |||
}
| |||
}
| |||
}
| |||
}
| |||
}
| |||
//+------------------------------------------------------------------+
| |||
//| Writing tree to file |
| |||
//+------------------------------------------------------------------+
| |||
bool CTree::Save(const int file_handle)
| |||
{
| |||
//--- check
| |||
if(file_handle==INVALID_HANDLE)
| |||
return(false);
| |||
if(m_root_node==NULL)
| |||
return(true);
| |||
//--- result
| |||
return(m_root_node.SaveNode(file_handle));
| |||
}
| |||
//+------------------------------------------------------------------+
| |||
//| Reading tree from file |
| |||
//+------------------------------------------------------------------+
| |||
bool CTree::Load(const int file_handle)
| |||
{
| |||
//--- check
| |||
if(file_handle==INVALID_HANDLE)
| |||
return(false);
| |||
//--- create root node only
| |||
Clear();
| |||
Insert(CreateElement());
| |||
//--- result
| |||
return(m_root_node.LoadNode(file_handle,m_root_node));
| |||
}
| |||
//+------------------------------------------------------------------+
|