AVL дерево

////////////////////////// Объявление
 
struct TNodeData {
* AnsiString Name;
};

struct TNode{
* TNodeData ndData;
* int iBalance;
* TNode *LeftPtr;
* TNode *RightPtr;
};

class TAVLTree {
private:
public:
* TNode *RootPtr;
* void Done(TNode *Ptr);
* TAVLTree();
* ~TAVLTree();
* void LLRotate(TNode *&Ptr);
* void LRRotate(TNode *&Ptr);
* void RRRotate(TNode *&Ptr);
* void RLRotate(TNode *&Ptr);
* TNode *NewNode(TNodeData Data);*
* void apendNode(TNodeData Data, TNode *&Ptr, bool &UpGrowth);
* void OutTree(TImage* Image, TNode *Ptr, int x, int y, int d);
};

//////////////////////////// Определение

TAVLTree::TAVLTree(){
* RootPtr=NULL;
}

void TAVLTree::Done(TNode *Ptr){
* if(Ptr == NULL) return;
* TNode* Pl; TNode* Pr;
* Pl=Ptr->LeftPtr;
* Pr=Ptr->RightPtr;
* delete(Ptr);
* Ptr=NULL;
* if(Pl != NULL) Done(Pl);
* if(Pr != NULL) Done(Pr);
}

TAVLTree::~TAVLTree(){
* Done(RootPtr);
}

void TAVLTree::OutTree(TImage* Image, TNode *Ptr, int x, int y, int d){
* if(Ptr == NULL) return;
* if(Ptr->LeftPtr != NULL) OutTree(Image,Ptr->LeftPtr,x-d,y+20,d%2);
* Image->Canvas->TextOut(x,y+20,Ptr->ndData.Name);
* if(Ptr->RightPtr != NULL) OutTree(Image,Ptr->RightPtr,x-d,y+20,d%2);
}

void TAVLTree::LLRotate(TNode *&Ptr){*
* TNode *Q=NULL;
* Q=Ptr->LeftPtr;
* Q->iBalance=0;
* Ptr->iBalance=0;
* Ptr->LeftPtr=Q->RightPtr;
* Q->RightPtr=Ptr;
* Ptr=Q;
}

void TAVLTree::LRRotate(TNode *&Ptr){
* TNode *Q=NULL; TNode *R=NULL;
* Q=Ptr->LeftPtr;
* R=Q->RightPtr;
* if(R->iBalance < 0) Ptr->iBalance=1; else Ptr->iBalance=0;
* if(R->iBalance > 0) Q->iBalance=-1; else Q->iBalance=0;
* R->iBalance=0;
* Ptr->LeftPtr=R->RightPtr;
* Q->RightPtr=R->LeftPtr;
* R->LeftPtr=Q;
* R->RightPtr=Ptr;
* Ptr=R;
}

void TAVLTree::RRRotate(TNode *&Ptr){
* TNode *Q=NULL;
* Q=Ptr->RightPtr;
* Q->iBalance=0;
* Ptr->iBalance=0;
* Ptr->RightPtr=Q->LeftPtr;
* Q->LeftPtr=Ptr;
* Ptr=Q;
}

void TAVLTree::RLRotate(TNode *&Ptr){
* TNode *Q=NULL; TNode *R=NULL;
* Q=Ptr->RightPtr;
* R=Q->LeftPtr;
* if(R->iBalance > 0) Ptr->iBalance=-1; else Ptr->iBalance=0;
* if(R->iBalance < 0) Q->iBalance=1; else Q->iBalance=0;
* R->iBalance=0;
* Ptr->RightPtr=R->LeftPtr;
* Q->LeftPtr=R->RightPtr;
* R->LeftPtr=Ptr;
* R->RightPtr=Q;
* Ptr=R;
}

TNode* TAVLTree::NewNode(TNodeData Data){
* TNode* Ptr;
* Ptr=new TNode;
* Ptr->ndData=Data;
* Ptr->LeftPtr=NULL;
* Ptr->RightPtr=NULL;
* return Ptr;
}

void TAVLTree::apendNode(TNodeData Data, TNode *&Ptr, bool &UpGrowth){
* if(Ptr == NULL){
* * Ptr=NewNode(Data);
* * Ptr->iBalance=0;
* * UpGrowth=true;
* }else{
* * if(Ptr->ndData.Name > Data.Name){
* * * apendNode(Data,Ptr->LeftPtr,UpGrowth);
* * * if(UpGrowth)
* * * * if(Ptr->iBalance > 0){
* * * * * Ptr->iBalance=0;
* * * * * UpGrowth=false;
* * * * }else if(Ptr->iBalance == 0){
* * * * * Ptr->iBalance=-1;
* * * * }else if(Ptr->iBalance < 0){
* * * * * if(Ptr->LeftPtr->iBalance < 0){
* * * * * * LLRotate(Ptr);
* * * * * }else{
* * * * * * LRRotate(Ptr);
* * * * * }
* * * * * Ptr->iBalance=0;
* * * * * UpGrowth=false;
* * * * }
* * }else if(Ptr->ndData.Name < Data.Name){
* * * this->apendNode(Data,Ptr->RightPtr,UpGrowth);
* * * if(UpGrowth)
* * * * if(Ptr->iBalance < 0){
* * * * * Ptr->iBalance=0;
* * * * * UpGrowth=false;
* * * * }else if(Ptr->iBalance == 0){
* * * * * Ptr->iBalance=1;
* * * * }else if(Ptr->iBalance > 0){
* * * * * if(Ptr->RightPtr->iBalance > 0){
* * * * * * RRRotate(Ptr);
* * * * * }else{
* * * * * * RLRotate(Ptr);
* * * * * }
* * * * * Ptr->iBalance=0;
* * * * * UpGrowth=false;
* * * * }
* * }else if(Ptr->ndData.Name == Data.Name){
* * //заглушка
* * }
* }
}

/////////////////////////Построение АВЛ дерева

* TAVLTree AVLTree;
* TNodeData Data;
* bool UpGrowth = false;
* Data.Name="A";
* AVLTree.apendNode(Data,AVLTree.RootPtr,UpGrowth);
* Data.Name="B"; UpGrowth = false;
* AVLTree.apendNode(Data,AVLTree.RootPtr,UpGrowth);
* Data.Name="C"; UpGrowth = false;
* AVLTree.apendNode(Data,AVLTree.RootPtr,UpGrowth);
* Data.Name="D"; UpGrowth = false;
* AVLTree.apendNode(Data,AVLTree.RootPtr,UpGrowth);
* Data.Name="E"; UpGrowth = false;
* AVLTree.apendNode(Data,AVLTree.RootPtr,UpGrowth);
* Data.Name="F"; UpGrowth = false;
* AVLTree.apendNode(Data,AVLTree.RootPtr,UpGrowth);
* Data.Name="G"; UpGrowth = false;
* AVLTree.apendNode(Data,AVLTree.RootPtr,UpGrowth);
* Data.Name="K"; UpGrowth = false;
* AVLTree.apendNode(Data,AVLTree.RootPtr,UpGrowth);
* AVLTree.OutTree(Image1,AVLTree.RootPtr,200,80,90);