AVL tree реализация шаг за шагом

Question

Во-первых, я прочитал так много тем в стеке относительно avl-деревьев, но у меня возникли проблемы с пониманием реализации, представленной другими пользователями.

Я знаком с идеей дерева AVL, как он балансирует сам, и я знаю, как реализовать стандартное дерево BST, что очень полезно, но я не могу найти в Интернете один кусок C++ Реализация AVL с пошаговым введением, что я пытаюсь сделать, это найти материал, который позволит мне самым легким образом понять, что происходит с кодом.

Наверное, в штате есть несколько студентов/выпускников ИТ, которые могут помочь мне со своими академическими сценариями, к сожалению, я не нашел ничего интересного при использовании дяди Google.

Все, что я нашел, некоторые части неполного кода, в то время как я ищу для реализации, которая включает в себя: структуры дерева, все балансирующие функции с некоторым объяснением, как это делается & печать в заказе/удалении/функции узла вставки как скважина

http://kukuruku.co/hub/cpp/avl-trees весьма полезен, но все же ему не хватает какого-то базового объяснения, и я просто не могу обойти эту вещь.

Answer 1

@ Chris M Я думаю, что этот код может помочь you..Its простую программу для реализации словаря с помощью AVL дереву

"#include "iostream " <br> 
#include "string.h" <br> 
using namespace std; <br> 
class node <br> 
{ <br> 
    //int data; <br> 
    char key[10],mean[10]; <br> 
    node *left,*right; <br> 
    int ht; <br> 
}; <br> 

class AVL <br> 
{ 
    public: <br> 
    node *root; <br> 
    node *insert(node *,char[], char[]);//Recursive counterpart of insert <br> 
    node *Delete1(node *,char[]);//Recursive counterpart of delete <br> 
    void preorder1(node *); //Recursive counterpart of preorder <br> 
    void inorder1(node *); //Recursive counterpart of inorder <br> 

    node *rotateright(node *); <br> 
    node *rotateleft(node *); <br> 
    node *RR(node *); <br> 
    node *LL(node *); <br> 
    node *LR(node *); <br> 
    node *RL(node *); 
    int height(node *); <br> 
    int BF(node *); <br> 
     AVL() 
     { 
    root=NULL; 
     } 
    void create(char *x,char *y) <br> 
    { 
    root=insert(root,x,y); <br> 
    } 
    void Delete(char *x) <br> 
    { 
    root=Delete1(root,x); <br> 
    } 

    void levelwise(); 
    void makenull() 
    { 
     root=NULL; 
    } 
}; 
int main() 
{ 
    AVL A; 
    char k[20],m[20]; 
    int n,i,op; 

    do 
     { 
      cout<<"\n1)Create : "; <br> 
      cout<<"\n2)Insert : "; <br> 
      cout<<"\n3)Delete : "; <br> 
      cout<<"\n4)Print : "; <br> 
      cout<<"\n5)Quit : "; <br> 
      cout<<"\nEnter Your Choice : "; <br> 
      cin >> op; <br> 
      switch(op) <br> 
       { 
       case 1:cout<<"\nEnter no.of elements :"; <br> 
         cin>>n; <br> 
         cout<<"\n Enter key and its meaning:"; <br> 
         A.makenull(); <br> 
         for(i=0;i<n;i++) <br> 
         { 
         cin>>k; <br> 
         cin>>m; <br> 
         A.create(k,m); <br> 
         } 
         break; <br> 
       case 2:cout<<"\n Enter key and its meaning:"; 
         cin >>k; 
         cin >>m; 
         A.create(k,m); 
         break; 
       case 3:cout<<"\n Enter key to be deleted:"; <br> 
         cin >>k; 
         A.Delete(k); <br> 
         break; 
       case 4: cout<<"\nPreorder sequence :\n"; <br> 
        A.preorder1(A.root); 
        cout<<"\nInorder sequence :\n"; <br> 
        A.inorder1(A.root); v 
        //A.levelwise(); 
        break; <br> 
       } 

    }while(op!=5); <br> 
return 0; 

} 
node * AVL::insert(node *T,char *k,char *m) <br> 
{ 
int i; 
    if(T==NULL) 
    { 
     T=new node; 
     strcpy(T->key,k); <br> 
     strcpy(T->mean,m); <br> 
     T->left=NULL; <br> 
     T->right=NULL; <br> 
    } <br> 
    else 
     { 
     for(int i=0;i<=strlen(k);i++) 
     { 
     if(k[i] > T->key[i])    // insert in right subtree 
     { 
      T->right=insert(T->right,k,m); <br> 
      if(BF(T)==-2) <br> 
       if(k [i] >T->right->key[i]) <br> 
        T=RR(T); 
       else 
        T=RL(T); 
      break; 
     } 
     else 
      //if(x<T->key) 
     { 
      T->left=insert(T->left,k,m); <br> 
      if(BF(T)==2) 
       if(k[i] < T->left->key[i]) <br> 
        T=LL(T); <br> 
       else 
        T=LR(T); 
      break; 
      } 
      } 
     } 
      T->ht=height(T); 
      return(T); 
} 

int AVL::height(node *T) v 
{ 
    int lh,rh; 
    if(T==NULL) <br> 
     return(0); 
    if(T->left==NULL) v 
     lh=0; 
    else 
     lh=1+T->left->ht; <br> 
    if(T->right==NULL) 
     rh=0; 
    else 
     rh=1+T->right->ht; <br> 
    if(lh>rh) 
     return(lh); 
    return(rh); 
} 
node * AVL::rotateright(node *x) <br> 
{ 
    node *y; 
    y=x->left; 
    x->left=y->right; 
    y->right=x; 
    x->ht=height(x); 
    y->ht=height(y); 
    return(y); 
} 
node * AVL::rotateleft(node *x) <br> 
{ 
    node *y; 
    y=x->right; 
    x->right=y->left; 
    y->left=x; 
    x->ht=height(x); 
    y->ht=height(y); 
    return(y); 
} 
node * AVL::RR(node *T) <br> 
{ 
    T=rotateleft(T); 
    return(T); 
} 
node * AVL::LL(node *T) <br> 
{ 
    T=rotateright(T); 
    return(T); 
} 
node * AVL::LR(node *T) <br> 
{ 
    T->left=rotateleft(T->left); 
    T=rotateright(T); 
    return(T); 
} 
node * AVL::RL(node *T) <br> 
{ 
    T->right=rotateright(T->right); 
    T=rotateleft(T); 
    return(T); 
} 
int AVL::BF(node *T) <br> 
{ 
    int lh,rh; 
    if(T==NULL) 
    return(0); 
    if(T->left==NULL) 
     lh=0; 
    else 
     lh=1+T->left->ht; 
    if(T->right==NULL) 
     rh=0; 
    else 
     rh=1+T->right->ht; 
    return(lh-rh); 
} 

void AVL::preorder1(node *T) <br> 
{ 
    if(T!=NULL) 
    { 
     cout<<" "<<T->key<<"(Bf="<<BF(T)<<")"; 
     preorder1(T->left); 
     preorder1(T->right); 
    } 
} 

void AVL::inorder1(node *T) <br> 
{ 
    if(T!=NULL) 
    { 
     inorder1(T->left); 
     cout<<" "<<T->key<<"(Bf="<<BF(T)<<")"; 
     inorder1(T->right); 
    } 
} 

node * AVL::Delete1(node *T,char *x) <br> 
{  node *p; 
    if(T==NULL) 
    { 
     return NULL; 
    } 
    else 
     { 
     for(int i=0;i<strlen(x);i++) <br> 
     if(x[i] > T->key[i])    // insert in right subtree 
     { 
      T->right=Delete1(T->right,x); 
      if(BF(T)==2) 
       if(BF(T->left)>=0) 
        T=LL(T); 
       else 
        T=LR(T); 
      break; 
     } 
     else 
      if(x[i]<T->key[i]) 
       { 
        T->left=Delete1(T->left,x); 
        if(BF(T)==-2)//Rebalance during windup 
         if(BF(T->right)<=0) 
          T=RR(T); 
         else 


    T=RL(T); 
       break; 
       } 

      else <br> 
       { 
       //key to be deleted is found 
        if(T->right !=NULL) 
        { //delete its inorder succesor 
         p=T->right; 
         while(p->left != NULL) 
         p=p->left; 

         strcpy(T->key,p->key); 
         T->right=Delete1(T->right,p->key); 
         if(BF(T)==2)//Rebalance during windup 
         if(BF(T->left)>=0) 
          T=LL(T); 
         else 
          T=LR(T); 
        } 
        else <br> 
        return(T->left); 
        break; 

       } 
     } 
    T->ht=height(T); 
    return(T); 
}