Реализация АВЛ-дерева

Ниже предложены возможная программная реализация АВЛ-дерева.

Код класса на Object Pascal.

unit mAVLTree;
 
interface
 
type
 
  TAVLTree = class;
 
  TAVLTreeNode = class (TObject)
  private
    FKey: Cardinal;
    FData: TObject;
 
    FBalance,
    FLeftBalance,
    FRightBalance: Byte;
 
    FLeft,
    FRight,
    FParent: TAVLTreeNode;
 
    FOwner: TAVLTree;
 
    procedure RefreshBalance;
  public
    constructor Create(AOwner: TAVLTree; AKey: Cardinal; AData: TObject; AParent: TAVLTreeNode);
    destructor Destroy; override;
 
    function GetNext(AKey: Cardinal): TAVLTreeNode;
 
    property Key: Cardinal read FKey write FKey;
    property Data: TObject read FData write FData;
 
    property Parent: TAVLTreeNode read FParent write FParent;
    property Left: TAVLTreeNode read FLeft write FLeft;
    property Right: TAVLTreeNode read FRight write FRight;
 
    property Balance: Byte read FBalance;
    property LeftBalance: Byte read FLeftBalance;
    property RightBalance: Byte read FRightBalance;
  end;
 
  TAVLTree = class (TObject)
  private
    FRoot: TAVLTreeNode;
    FOwnedObjects: Boolean;
    procedure Balance(const ANode: TAVLTreeNode);
  public
    constructor Create(AOwnedObjects: Boolean);
    destructor Destroy; override;
 
    function IsEmpty: Boolean;
    function FindData(AKey: Cardinal): Pointer;
    function FindNode(AKey: Cardinal): TAVLTreeNode;
    function FindOrInsert(AKey: Cardinal; AData: TObject): TAVLTreeNode;
    function Delete(AKey: Cardinal): Boolean;
    procedure Clear;
 
    property Root: TAVLTreeNode read FRoot write FRoot;
  end;
 
implementation
 
uses SysUtils;
 
{ TAVLTreeNode }
 
procedure TAVLTreeNode.RefreshBalance;
begin
  if Assigned(Left) then
    FLeftBalance := Left.Balance
  else
    FLeftBalance := 0;
 
  if Assigned(Right) then
    FRightBalance := Right.Balance
  else
    FRightBalance := 0;
 
  if RightBalance > LeftBalance then
    FBalance := RightBalance + 1
  else
    FBalance := LeftBalance + 1;
end;
 
constructor TAVLTreeNode.Create(AOwner: TAVLTree; AKey: Cardinal; AData: TObject; AParent: TAVLTreeNode);
begin
  inherited Create;
 
  FKey := AKey;
  FData := AData;
  Parent := AParent;
  FBalance := 1;
  FOwner := AOwner;
end;
 
destructor TAVLTreeNode.Destroy;
begin
  if FOwner.FOwnedObjects then
    FreeAndNil(FData);
 
  inherited;  
end;
 
function TAVLTreeNode.GetNext(AKey: Cardinal): TAVLTreeNode;
begin
  if Key > AKey then
    Result := Left
  else
    Result := Right;
end;
 
{ TAVLTree }
 
procedure TAVLTree.Balance(const ANode: TAVLTreeNode);
var
  NodeA,
  NodeB,
  NodeC,
  CurrentNode: TAVLTreeNode;
begin
  CurrentNode := ANode;
 
  while Assigned(CurrentNode) do
  begin
    CurrentNode.RefreshBalance;
 
    if Abs(CurrentNode.LeftBalance - CurrentNode.RightBalance) <= 1 then
      CurrentNode := CurrentNode.Parent
    else
      if CurrentNode.RightBalance > CurrentNode.LeftBalance then
      begin
        if CurrentNode.Right.LeftBalance > CurrentNode.Right.RightBalance then
        begin
          NodeA := CurrentNode;
          NodeB := NodeA.Right;
          NodeC := NodeB.Left;
          NodeC.Parent := NodeA.Parent;
 
          if Assigned(NodeC.Parent) then
            if NodeC.Parent.Right = NodeA then
              NodeC.Parent.Right := NodeC
            else
              NodeC.Parent.Left := NodeC;
 
          NodeA.Parent := NodeC;
          NodeB.Parent := NodeC;
          NodeA.Right := NodeC.Left;
          if Assigned(NodeA.Right) then
            NodeA.Right.Parent := NodeA;
 
          NodeC.Left := NodeA;
          NodeB.Left := NodeC.Right;
          if Assigned(NodeB.Left) then
            NodeB.Left.Parent := NodeB;
 
          NodeC.Right := NodeB;
 
          NodeA.RefreshBalance;
          NodeB.RefreshBalance;
          NodeC.RefreshBalance;
 
          if Root = NodeA then
            Root := NodeC;
 
          CurrentNode := NodeC.Parent;
        end
        else
        begin
          NodeA := CurrentNode;
          NodeB := NodeA.Right;
          NodeB.Parent := NodeA.Parent;
 
          if Assigned(NodeB.Parent) then
            if NodeB.Parent.Right = NodeA then
              NodeB.Parent.Right := NodeB
            else
              NodeB.Parent.Left := NodeB;
 
          NodeA.Parent := NodeB;
          NodeA.Right := NodeB.Left;
 
          if Assigned(NodeA.Right) then
            NodeA.Right.Parent := NodeA;
 
          NodeB.Left := NodeA;
 
          NodeA.RefreshBalance;
          NodeB.RefreshBalance;
 
          if Root = NodeA then
            Root := NodeB;
 
          CurrentNode := NodeB.Parent;
        end
      end
      else
      begin
        if CurrentNode.Left.RightBalance>CurrentNode.Left.LeftBalance then
        begin
          NodeA := CurrentNode;
          NodeB := NodeA.Left;
          NodeC := NodeB.Right;
          NodeC.Parent := NodeA.Parent;
          if Assigned(NodeC.Parent) then
            if NodeC.Parent.Right = NodeA then
              NodeC.Parent.Right := NodeC
            else
              NodeC.Parent.Left := NodeC;
 
          NodeA.Parent := NodeC;
          NodeB.Parent := NodeC;
          NodeA.Left := NodeC.Right;
          if Assigned(NodeA.Left) then
              NodeA.Left.Parent := NodeA;
 
          NodeC.Right := NodeA;
          NodeB.Right := NodeC.Left;
          if Assigned(NodeB.Right) then
            NodeB.Right.Parent := NodeB;
          NodeC.Left:=NodeB;
 
          NodeA.RefreshBalance;
          NodeB.RefreshBalance;
          NodeC.RefreshBalance;
 
          if Root = NodeA then
            Root := NodeC;
 
          CurrentNode := NodeC.Parent;
        end
        else
        begin
          NodeA := CurrentNode;
          NodeB := NodeA.Left;
          NodeB.Parent := NodeA.Parent;
          if Assigned(NodeB.Parent) then
            if NodeB.Parent.Right = NodeA then
            NodeB.Parent.Right := NodeB
          else
            NodeB.Parent.Left := NodeB;
 
          NodeA.Parent := NodeB;
          NodeA.Left := NodeB.Right;
 
          if Assigned(NodeA.Left) then
            NodeA.Left.Parent := NodeA;
 
          NodeB.Right := NodeA;
 
          NodeA.RefreshBalance;
          NodeB.RefreshBalance;
 
         if Root = NodeA then
           Root := NodeB;
          CurrentNode:=NodeB.Parent;
        end
      end;
  end;
end;
 
constructor TAVLTree.Create(AOwnedObjects: Boolean);
begin
  inherited Create;
 
  FOwnedObjects := AOwnedObjects;
end;
 
destructor TAVLTree.Destroy;
begin
  Clear;
 
  inherited;
end;
 
function TAVLTree.IsEmpty: Boolean;
begin
  Result := not Assigned(Root);
end;
 
function TAVLTree.FindData(AKey: Cardinal): Pointer;
var
  Node: TAVLTreeNode;
begin
  Node := FindNode(AKey);
 
  if Assigned(Node) then
    Result := Node.Data
  else
    Result := nil;
end;
 
function TAVLTree.FindNode(AKey: Cardinal): TAVLTreeNode;
begin
  Result := Root;
 
  while Assigned(Result) and (Result.Key <> AKey) do
    Result := Result.GetNext(AKey);
end;
 
function TAVLTree.FindOrInsert(AKey: Cardinal; AData: TObject): TAVLTreeNode;
var
  ParentNode,
  NewNode: TAVLTreeNode;
begin
  Result := Root;
 
  if Assigned(Result) then
  begin
    ParentNode := nil;
    Result := Root;
 
    while Assigned(Result) and (Result.Key <> Akey) do
    begin
      ParentNode := Result;
      Result := Result.GetNext(AKey);
    end;
 
    if Assigned(Result) then Exit;
 
    NewNode := TAVLTreeNode.Create(Self, AKey, AData, ParentNode);
 
    if ParentNode.Key > NewNode.Key then
      ParentNode.Left := NewNode
    else
      ParentNode.Right := NewNode;
 
    Balance(ParentNode);
  end
  else
  begin
    Root := TAVLTreeNode.Create(Self, AKey, AData, nil);
  end;
end;
 
function TAVLTree.Delete(AKey: Cardinal): Boolean;
var
  CurrentNode,
  NodeA,
  NodeB: TAVLTreeNode;
begin
  CurrentNode := FindNode(AKey);
 
  Result := Assigned(CurrentNode);
 
  if Result then
  begin
    if CurrentNode.LeftBalance > CurrentNode.RightBalance then
    begin
      NodeA := CurrentNode.Left;
 
      while Assigned(NodeA.Right) do
        NodeA := NodeA.Right;
 
      NodeB := NodeA.Parent;
 
      if NodeB = CurrentNode then
      begin
        CurrentNode.Left := NodeA.Left;
        if Assigned(CurrentNode.Left) then
          CurrentNode.Left.Parent := CurrentNode;
      end
      else
      begin
        NodeB.Right := NodeA.Left;
        if Assigned(NodeB.Right) then
          NodeB.Right.Parent := NodeB;
      end;
 
      CurrentNode.Key := NodeA.Key;
      CurrentNode.Data := NodeA.Data;
      FreeAndNil(NodeA);
 
      Balance(NodeB);
    end
    else if CurrentNode.RightBalance > 0 then
    begin
      NodeA := CurrentNode.Right;
 
      while Assigned(NodeA.Left) do
        NodeA := NodeA.Left;
 
      NodeB := NodeA.Parent;
 
      if NodeB = CurrentNode then
      begin
        CurrentNode.Right := NodeA.Right;
        if Assigned(CurrentNode.Right) then
          CurrentNode.Right.Parent := CurrentNode;
      end
      else
      begin
        NodeB.Left:=NodeA.Right;
        if Assigned(NodeB.Left) then
          NodeB.Left.Parent := NodeB;
      end;
 
      CurrentNode.Key := NodeA.Key;
      CurrentNode.Data := NodeA.Data;
 
      FreeAndNil(NodeA);
 
      Balance(NodeB);
    end
    else
    begin
      if not Assigned(CurrentNode.Parent) then
        Root := nil
      else
        if (CurrentNode.Parent.Left = CurrentNode) then
          CurrentNode.Parent.Left := nil
        else
          CurrentNode.Parent.Right := nil ;
 
      {Parent of Current Node is Not Balanced ,so}
      Balance(CurrentNode.Parent);
 
      FreeAndNil(CurrentNode);
    end;
  end;
end;
 
procedure TAVLTree.Clear;
 
  procedure _Clear_R(ANode: TAVLTreeNode);
  begin
    if not Assigned(ANode) then Exit;
 
    if Assigned(ANode.Left) then begin
      _Clear_R(ANode.Left);
    end;
 
    if Assigned(ANode.Right) then begin
      _Clear_R(ANode.Right);
    end;
 
    FreeAndNil(ANode);
  end;
 
begin
  _Clear_R(FRoot);
end;
 
 
end.

Код класса на C++.

using std::swap;
using std::max;
 
template <typename KEY_T, typename DATA_T>
class TreeMap{
	struct Node{
		KEY_T Key;
		DATA_T Data;
		Node* LeftChild;
		Node* RightChild;
		int Balance;
		Node(const KEY_T InKey, DATA_T InData);
		~Node();
		Node* GetNodeByKey(const KEY_T& InKey);
		void DeleteBranch();
		int Add(const KEY_T& InKey, const DATA_T& InData);
		int Delete(const KEY_T& InKey, Node* Parent=NULL);
		void DeleteLeaf(Node* Parent);
		size_t Count();
		Node* Leftest();
		Node* Rightest();
		void Swap(Node* Another);
		void Rebalance();
		void RotateLeft();
		void RotateRight();
		void DoubleRotateLeft();
		void DoubleRotateRight();
		int Height();
		void Check();
	};
	Node* Root;
public:
	class Iterator{
		Node* CurrentNode;
		TreeMap* CurrentTree;
		List<Node*> Stack;
		void SetBad();
		void GoLeft();
		void GoRight();
	public:
		friend class TreeMap<KEY_T, DATA_T>;
		Iterator(const Iterator& InIterator);
		Iterator(TreeMap& InTreeMap, bool IsBegin=true);
		operator bool();
		Iterator& operator++();
		Iterator& operator--();
		Iterator operator++(int);
		Iterator operator--(int);
		Iterator& operator+=(size_t n);
		Iterator& operator-=(size_t n);
		Iterator& operator=(const Iterator& InIterator);
		Iterator& operator=(const KEY_T& InKey);
		DATA_T& operator*();
		void Delete();
		void Add(const KEY_T& InKey, const DATA_T& InData);
	};
	TreeMap();
	~TreeMap();
	Iterator GetBegin();
	Iterator GetEnd();
	void Add(const KEY_T& InKey, const DATA_T& InData);
	void Delete(const KEY_T& InKey);
	DATA_T& operator[](const KEY_T& InKey);
	size_t Count();
	void Clear();
	Iterator Find(const DATA_T& Unknown);
	void CheckIntegrity();
};
 
template <typename KEY_T, typename DATA_T>
TreeMap<KEY_T, DATA_T>::Node::Node(const KEY_T InKey, DATA_T InData):Key(InKey), Data(InData), LeftChild(NULL), RightChild(NULL), Balance(0){
}
 
template <typename KEY_T, typename DATA_T>
TreeMap<KEY_T, DATA_T>::Node::~Node(){
}
 
template <typename KEY_T, typename DATA_T>
void TreeMap<KEY_T, DATA_T>::Node::DeleteLeaf(TreeMap<KEY_T, DATA_T>::Node* Parent){
	if(Parent->LeftChild==this)
		Parent->LeftChild=NULL;
	else
		Parent->RightChild=NULL;
	delete this;
}
 
 
template <typename KEY_T, typename DATA_T>
typename TreeMap<KEY_T, DATA_T>::Node* TreeMap<KEY_T, DATA_T>::Node::GetNodeByKey(const KEY_T& InKey){
	if(InKey==Key)
		return this;
	else if(InKey>Key && RightChild)
		return RightChild->GetNodeByKey(InKey);
	else if(LeftChild)
		return LeftChild->GetNodeByKey(InKey);
	throw String("No node for this key!");
}
 
template <typename KEY_T, typename DATA_T>
size_t TreeMap<KEY_T, DATA_T>::Node::Count(){
	size_t Counter=1;
	if(RightChild)
		Counter+=RightChild->Count();
	if(LeftChild)
		Counter+=LeftChild->Count();
	return Counter;
}
 
template <typename KEY_T, typename DATA_T>
int TreeMap<KEY_T, DATA_T>::Node::Add(const KEY_T& InKey, const DATA_T& InData){
	if(InKey==Key)
		throw String("Not unique key!");
	int OldBalance=Balance;
	if(InKey>Key)
		if(RightChild){
			Balance+=RightChild->Add(InKey, InData);
			Rebalance();
		}else{
			RightChild=new Node(InKey, InData);
			Balance++;
		}
	else
		if(LeftChild){
			Balance-=LeftChild->Add(InKey, InData);
			Rebalance();
		}else{
			LeftChild=new Node(InKey, InData);
			Balance--;
		}
	if(Balance!=OldBalance)
		return (Balance!=0);
	return 0;
}
 
template <typename KEY_T, typename DATA_T>
void TreeMap<KEY_T, DATA_T>::Node::Swap(TreeMap<KEY_T, DATA_T>::Node* Another){
	swap(Key, Another->Key);
	swap(Data, Another->Data);
}
 
template <typename KEY_T, typename DATA_T>
typename TreeMap<KEY_T, DATA_T>::Node* TreeMap<KEY_T, DATA_T>::Node::Leftest(){
	Node* CurrentNode=this;
	while(CurrentNode->LeftChild)
		CurrentNode=CurrentNode->LeftChild;
	return CurrentNode;
}
 
template <typename KEY_T, typename DATA_T>
typename TreeMap<KEY_T, DATA_T>::Node* TreeMap<KEY_T, DATA_T>::Node::Rightest(){
	Node* CurrentNode=this;
	while(CurrentNode->RightChild)
		CurrentNode=CurrentNode->RightChild;
	return CurrentNode;
}
 
template <typename KEY_T, typename DATA_T>
int TreeMap<KEY_T, DATA_T>::Node::Delete(const KEY_T& InKey, TreeMap<KEY_T, DATA_T>::Node* Parent){
	int OldBalance=Balance;
	if(InKey==Key){
		if(!RightChild && !LeftChild){
			DeleteLeaf(Parent);
			return 1;
		}else 
			if(Balance>=0){
				Swap(RightChild->Leftest());
				Balance-=RightChild->Delete(InKey, this);
			}else{
				Swap(LeftChild->Rightest());
				Balance+=LeftChild->Delete(InKey, this);
			}
	}else if(InKey>Key)
		if(RightChild){
			Balance-=RightChild->Delete(InKey, this);
			Rebalance();
		}else
			throw String("There is no node for this key!");
	else
		if(LeftChild){
			Balance+=LeftChild->Delete(InKey, this);
			Rebalance();
		}else
			throw String("There is no node for this key!");
	if(Balance!=OldBalance)
		return (Balance==0);
	return 0;
}
 
template <typename KEY_T, typename DATA_T>
void TreeMap<KEY_T, DATA_T>::Node::Rebalance(){
	if(Balance==2)
		if(RightChild->Balance>=0)
			RotateRight();
		else
			DoubleRotateRight();
	else if(Balance==-2)
		if(LeftChild->Balance<=0)
			RotateLeft();
		else
			DoubleRotateLeft();
}
 
template <typename KEY_T, typename DATA_T>
void TreeMap<KEY_T, DATA_T>::Node::RotateRight(){
	Swap(RightChild);
	Node* R=RightChild->RightChild;
	RightChild->RightChild=RightChild->LeftChild;
	RightChild->LeftChild=LeftChild;
	LeftChild=RightChild;
	RightChild=R;
	Balance=LeftChild->Balance-1;
	LeftChild->Balance=1-LeftChild->Balance;
}
 
template <typename KEY_T, typename DATA_T>
void TreeMap<KEY_T, DATA_T>::Node::DoubleRotateRight(){
	Swap(RightChild->LeftChild);
	Node* N=RightChild->LeftChild->RightChild;
	RightChild->LeftChild->RightChild=RightChild->LeftChild->LeftChild;
	RightChild->LeftChild->LeftChild=LeftChild;
	LeftChild=RightChild->LeftChild;
	RightChild->LeftChild=N;
	Balance=0;
	RightChild->Balance=(LeftChild->Balance==-1);
	LeftChild->Balance=-(LeftChild->Balance==1);
}
 
template <typename KEY_T, typename DATA_T>
void TreeMap<KEY_T, DATA_T>::Node::RotateLeft(){
	Swap(LeftChild);
	Node* L=LeftChild->LeftChild;
	LeftChild->LeftChild=LeftChild->RightChild;
	LeftChild->RightChild=RightChild;
	RightChild=LeftChild;
	LeftChild=L;
	Balance=1+RightChild->Balance;
	RightChild->Balance=-1-RightChild->Balance;
}
 
template <typename KEY_T, typename DATA_T>
void TreeMap<KEY_T, DATA_T>::Node::DoubleRotateLeft(){
	Swap(LeftChild->RightChild);
	Node* M=LeftChild->RightChild->LeftChild;
	LeftChild->RightChild->LeftChild=LeftChild->RightChild->RightChild;
	LeftChild->RightChild->RightChild=RightChild;
	RightChild=LeftChild->RightChild;
	LeftChild->RightChild=M;
	Balance=0;
	LeftChild->Balance=-(RightChild->Balance==1);
	RightChild->Balance=(RightChild->Balance==-1);
}
 
template <typename KEY_T, typename DATA_T>
TreeMap<KEY_T, DATA_T>::TreeMap(): Root(NULL){}
 
template <typename KEY_T, typename DATA_T>
TreeMap<KEY_T, DATA_T>::~TreeMap(){
	Clear();
}
 
template <typename KEY_T, typename DATA_T>
typename TreeMap<KEY_T, DATA_T>::Iterator TreeMap<KEY_T, DATA_T>::GetBegin(){
	return Iterator(*this);
}
 
template <typename KEY_T, typename DATA_T>
typename TreeMap<KEY_T, DATA_T>::Iterator TreeMap<KEY_T, DATA_T>::GetEnd(){
	return Iterator(*this, false);
}
 
template <typename KEY_T, typename DATA_T>
size_t TreeMap<KEY_T, DATA_T>::Count(){
	if(!Root)
		return 0;
	return Root->Count();
}
 
template <typename KEY_T, typename DATA_T>
void TreeMap<KEY_T, DATA_T>::Clear(){
	if(!Root)
		return;
	Root->DeleteBranch();
	Root=NULL;
}
 
template <typename KEY_T, typename DATA_T>
void TreeMap<KEY_T, DATA_T>::Node::DeleteBranch(){
	if(LeftChild)
		LeftChild->DeleteBranch();
	if(RightChild)
		RightChild->DeleteBranch();
	delete this;
}
 
template <typename KEY_T, typename DATA_T>
void TreeMap<KEY_T, DATA_T>::Iterator::SetBad(){
	CurrentNode=NULL;
	Stack.Clear();
}
 
template <typename KEY_T, typename DATA_T>
void TreeMap<KEY_T, DATA_T>::Iterator::GoLeft(){
	while(CurrentNode && CurrentNode->LeftChild){
		Stack.AddLast(CurrentNode);
		CurrentNode=CurrentNode->LeftChild;
	}
}
 
template <typename KEY_T, typename DATA_T>
void TreeMap<KEY_T, DATA_T>::Iterator::GoRight(){
	while(CurrentNode && CurrentNode->RightChild){
		Stack.AddLast(CurrentNode);
		CurrentNode=CurrentNode->RightChild;
	}
}
 
template <typename KEY_T, typename DATA_T>
typename TreeMap<KEY_T, DATA_T>::Iterator TreeMap<KEY_T, DATA_T>::Find(const DATA_T& Unknown){
	Iterator r(*this);
	for(; r; ++r)
		if(*r==Unknown)
			return r;
	r.SetBad();
	return r;
}
 
template <typename KEY_T, typename DATA_T>
TreeMap<KEY_T, DATA_T>::Iterator::Iterator(const TreeMap<KEY_T, DATA_T>::Iterator& InIterator){
	operator=(InIterator);
}
 
template <typename KEY_T, typename DATA_T>
TreeMap<KEY_T, DATA_T>::Iterator::Iterator(TreeMap<KEY_T, DATA_T>& InTreeMap, bool IsBegin):CurrentNode(InTreeMap.Root), CurrentTree(&InTreeMap){
	if(IsBegin)
		GoLeft();
	else
		GoRight();
}
 
template <typename KEY_T, typename DATA_T>
TreeMap<KEY_T, DATA_T>::Iterator::operator bool(){
	return CurrentNode!=NULL;
}
 
template <typename KEY_T, typename DATA_T>
typename TreeMap<KEY_T, DATA_T>::Iterator& TreeMap<KEY_T, DATA_T>::Iterator::operator++(){
	if(!CurrentNode)
		return *this;
	if(CurrentNode->RightChild){
		Stack.AddLast(CurrentNode);
		CurrentNode=CurrentNode->RightChild;
		GoLeft();
		return *this;
	}
	if(Stack.Count()==0){
		SetBad();
		return *this;
	}
	typename List<Node*>::Iterator i=Stack.GetEnd();
	if((*i)->LeftChild==CurrentNode){
		CurrentNode=*i;
		Stack.DeleteLast();
		return *this;
	}
	while(CurrentNode==(*i)->RightChild){
		CurrentNode=*i--;
		Stack.DeleteLast();
		if(Stack.Count()==0){
			SetBad();
			return *this;
		}
	}
	CurrentNode=*i;
	Stack.DeleteLast();
	return *this;
}
 
template <typename KEY_T, typename DATA_T>
typename TreeMap<KEY_T, DATA_T>::Iterator& TreeMap<KEY_T, DATA_T>::Iterator::operator--(){
	if(!CurrentNode)
		return *this;
	if(CurrentNode->LeftChild){
		Stack.AddLast(CurrentNode);
		CurrentNode=CurrentNode->LeftChild;
		GoRight();
		return *this;
	}
	if(Stack.Count()==0){
		SetBad();
		return *this;
	}
	typename List<Node*>::Iterator i=Stack.GetEnd();
	if((*i)->RightChild==CurrentNode){
		CurrentNode=*i;
		Stack.DeleteLast();
		return *this;
	}
	while(CurrentNode==(*i)->LeftChild){
		CurrentNode=*i--;
		Stack.DeleteLast();
		if(Stack.Count()==0){
			SetBad();
			return *this;
		}
	}
	CurrentNode=*i;
	Stack.DeleteLast();
	return *this;
}
 
template <typename KEY_T, typename DATA_T>
typename TreeMap<KEY_T, DATA_T>::Iterator TreeMap<KEY_T, DATA_T>::Iterator::operator++(int){
	Iterator Old(*this);
	++*this;
	return Old;
}
 
template <typename KEY_T, typename DATA_T>
typename TreeMap<KEY_T, DATA_T>::Iterator TreeMap<KEY_T, DATA_T>::Iterator::operator--(int){
	Iterator Old(*this);
	--*this;
	return Old;
}
 
template <typename KEY_T, typename DATA_T>
typename TreeMap<KEY_T, DATA_T>::Iterator& TreeMap<KEY_T, DATA_T>::Iterator::operator+=(size_t n){
	for(; n; n--)
		(*this)++;
	return *this;
}
 
template <typename KEY_T, typename DATA_T>
typename TreeMap<KEY_T, DATA_T>::Iterator& TreeMap<KEY_T, DATA_T>::Iterator::operator-=(size_t n){
	for(; n; n--)
		(*this)--;
	return *this;
}
 
template <typename KEY_T, typename DATA_T>
typename TreeMap<KEY_T, DATA_T>::Iterator& TreeMap<KEY_T, DATA_T>::Iterator::operator=(const TreeMap<KEY_T, DATA_T>::Iterator& InIterator){
	CurrentNode=InIterator.CurrentNode;
	CurrentTree=InIterator.CurrentTree;
	for(typename List<Node*>::Iterator i((List<Node*>&)InIterator.Stack); i; ++i)
		Stack.AddLast(*i);
	return *this;
}
 
template <typename KEY_T, typename DATA_T>
typename TreeMap<KEY_T, DATA_T>::Iterator& TreeMap<KEY_T, DATA_T>::Iterator::operator=(const KEY_T& InKey){
	CurrentNode=CurrentTree->Root->GetNodeByKey(InKey);
	return *this;
}
 
template <typename KEY_T, typename DATA_T>
DATA_T& TreeMap<KEY_T, DATA_T>::Iterator::operator*(){
	if(!(*this))
		throw String("Reading from bad iterator!");
	return CurrentNode->Data;
}
 
template <typename KEY_T, typename DATA_T>
void TreeMap<KEY_T, DATA_T>::Iterator::Delete(){
	if(!(*this))
		throw String("Delete from bad iterator. Nothing to delete!");
	CurrentTree->Delete(CurrentNode->Key);
}
 
template <typename KEY_T, typename DATA_T>
void TreeMap<KEY_T, DATA_T>::Add(const KEY_T& InKey, const DATA_T& InData){
	if(!Root)
		Root=new Node(InKey, InData);
	else
		Root->Add(InKey, InData);
}
 
template <typename KEY_T, typename DATA_T>
void TreeMap<KEY_T, DATA_T>::Delete(const KEY_T& InKey){
	if(Root->Key==InKey && !Root->LeftChild && !Root->RightChild){
		delete Root;
		Root=NULL;
	}else
		Root->Delete(InKey);
}
 
template <typename KEY_T, typename DATA_T>
DATA_T& TreeMap<KEY_T, DATA_T>::operator[](const KEY_T& InKey){
	if(!Root)
		throw String("Tree is empty!");
	Node* ReturnValue=Root->GetNodeByKey(InKey);
	return ReturnValue->Data;
}
 
// необязательный код для тестирования целостности дерева
template <typename KEY_T, typename DATA_T>
void TreeMap<KEY_T, DATA_T>::CheckIntegrity(){
	Root->Check();
}
 
template <typename KEY_T, typename DATA_T>
void TreeMap<KEY_T, DATA_T>::Node::Check(){
	if(!this)
		return; 
	if(Balance!=RightChild->Height()-LeftChild->Height())
		throw String("Mistake in balance integrity!");
	if(Balance<-1 || Balance>1)
		throw String("Tree is unbalanced!");
}
 
template <typename KEY_T, typename DATA_T>
int TreeMap<KEY_T, DATA_T>::Node::Height(){
	if (this==NULL)
		return 0;
	return max(RightChild->Height(), LeftChild->Height())+1;
}