mobinzkr/MobinMQL
1
0
Fork 0
Code Issues Pull requests Projects Releases Packages Wiki Activity Actions
MobinMQL/Include/Arrays/Tree.mqh
Mobin Zarekar 4746a7645a error handling course
2025-07-22 14:47:41 +03:00

415 lines
14 KiB
MQL5
Raw Permalink Blame History

//+------------------------------------------------------------------+
//| 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));
}
//+------------------------------------------------------------------+
Reference in a new issue View git blame Copy permalink