#include using namespace std; void p(int i) { if(i) p(i-1); printf(" "); } class BST { public : void add(int value) { add(root,value); } void del(int value) { del(root,value); } void draw() { draw(root,0,3); } void print(){ show(root); } protected: struct Node { Node *left=nullptr; int value,h=0; Node *right=nullptr; Node(int value):value(value) {} void setH(){ this->h=std::max(getLeftH(),getRightH())+1; } int getLeftH(){ if(left==nullptr) return -1; return left->h; } int getRightH(){ if(right==nullptr) return -1; return right->h; } int getBalance(){ return getLeftH()-getRightH(); } } *root=nullptr; int size=0; stackst; void add(Node*&root,int value) { if(root==nullptr) { root=new Node(value); size++; return; } st.push(root); if(root->value > value) add(root->left,value); else if(root->value < value) add(root->right,value); else { clear(st); return ; } root->setH(); balance(root); } Node *getMax(Node * t) { while (t != NULL && t->right != NULL) t = t->right; return t; } void del(Node*&root,int value) { if(root==nullptr) return ; st.push(root); if(root->value>value) del(root->left,value); else if(root->value < value) del(root->right,value); else { Node*deleted=root; if(root->left==nullptr) root=root->right; else if(/*root->left!=nullptr &&*/root->right==nullptr) root=root->left; else { Node*max=getMax(root); root->value=max->value; del(root->right,max->value); root->setH(); balance(root); return; } delete deleted;//when we have 1 son in the left OR the right if(root==nullptr) return ; } root->setH(); balance(root); } int search(Node*t,int value) { if(t==NULL) return 0; else if(t->value==value) return 1; else if(t->value>value) return search(t->left,value); else return search(t->right,value); } void show(Node * r) { if (r == NULL) return; show(r->left); printf("%d ", r->value); show(r->right); } void draw(Node*r,int space,int s) { if(r==NULL) return; draw(r->right,space+3,1); p(space); if(s==1) { printf("%d|%d\n",r->value,r->h); p(space); printf("/\n"); } else if(s==2) { printf("\\\n"); p(space); printf("%d|%d\n",r->value,r->h); } else printf("%d|%d\n",r->value,r->h); draw(r->left,space+3,2); } void clear(stack&st) { while(!st.empty()) st.pop(); } void RR(Node*&root){ Node*t=root; root=t->left; t->left=root->right; root->right=t; if(root->left!=nullptr) root->left->setH(); if(root->right!=nullptr) root->right->setH(); root->setH(); } void LR(Node*&root){ Node*t=root; root=t->right; t->right=root->left; root->left=t; if(root->left!=nullptr) root->left->setH(); if(root->right!=nullptr) root->right->setH(); root->setH(); } void RLR(Node*&root){ RR(root->right); LR(root); } void LRR(Node*&root){ LR(root->left); RR(root); } void balance(Node*&root){ if(root->getBalance()>=-1 && root->getBalance()<=1) return; Node*son=nullptr; if(root->getBalance()<0) son=root->right; else son=root->left; if(root->getBalance()*son->getBalance()>0) if(root->getBalance()<0) LR(root); else RR(root); else if(root->getBalance()<0) RLR(root); else LRR(root); } }; int main() { BST t; int a[] = { 15, 12, 13, 17, 16, 10, 9, 30, 9 }; sort(a,a+sizeof(a)/sizeof(int)); for (int i = 0; i < sizeof(a)/sizeof(int); i++) t.add(a[i]),t.draw(),printf("\n\n\n"); t.draw(); }

AVL