équilibrer un arbre AVL (C ++)

Question

Je vais avoir le plus de temps à essayer de comprendre comment équilibrer un arbre AVL pour ma classe. Je l'ai d'insérer avec ceci:

Node* Tree::insert(int d)
{
    cout << "base insert\t" << d << endl;
    if (head == NULL)
        return (head = new Node(d));
    else
        return insert(head, d);
}

Node* Tree::insert(Node*& current, int d)
{
    cout << "insert\t" << d << endl;
    if (current == NULL)
        current = new Node(d);
    else if (d < current->data) {
        insert(current->lchild, d);
        if (height(current->lchild) - height(current->rchild)) {
            if (d < current->lchild->getData())
                rotateLeftOnce(current);
            else
                rotateLeftTwice(current);
        }
    }
    else if (d > current->getData()) {
        insert(current->rchild, d);
        if (height(current->rchild) - height(current->lchild)) {
            if (d > current->rchild->getData())
                rotateRightOnce(current);
            else
                rotateRightTwice(current);
        }
    }

    return current;
}

Mon plan était d'avoir les appels à l'équilibre () vérifier si l'équilibre entre les besoins d'arbres et l'équilibre au besoin. Le problème est, je ne peux même pas comprendre comment traverser l'arbre pour trouver le nœud asymétrique correct. Je sais comment traverser l'arbre récursive, mais je ne peux pas sembler traduire cet algorithme en vue de trouver le plus bas nœud déséquilibré. Je suis aussi de la difficulté à écrire un algorithme itératif. Toute aide serait appréciée. :)

Answer 1

Vous pouvez mesurer la height d'une branche à un moment donné pour calculer le déséquilibre

(rappelez-vous une différence de hauteur (niveaux)> = 2 signifie que votre arbre est pas équilibré)

int Tree::Height(TreeNode *node){
     int left, right;

     if(node==NULL)
         return 0;
     left = Height(node->left);
     right = Height(node->right);
  if(left > right)
            return left+1;
         else
            return right+1;
} 

En fonction de l'inégalité, alors vous pouvez rotate si nécessaire

void Tree::rotateLeftOnce(TreeNode*& node){
     TreeNode *otherNode;

     otherNode = node->left;
     node->left = otherNode->right;
     otherNode->right = node;
     node = otherNode;
}


void Tree::rotateLeftTwice(TreeNode*& node){
     rotateRightOnce(node->left);
     rotateLeftOnce(node);
}


void Tree::rotateRightOnce(TreeNode*& node){
     TreeNode *otherNode;

     otherNode = node->right;
     node->right = otherNode->left;
     otherNode->left = node;
     node = otherNode;
}


void Tree::rotateRightTwice(TreeNode*& node){
     rotateLeftOnce(node->right);
     rotateRightOnce(node);
}

Maintenant que nous savons comment faire pivoter, permet de dire que vous voulez insérer une valeur dans l'arbre ... Tout d'abord nous vérifier si l'arbre est vide ou non

TreeNode* Tree::insert(int d){
     if(isEmpty()){
         return (root = new TreeNode(d));  //Is empty when root = null
     }
     else
         return insert(root, d);           //step-into the tree and place "d"
}

Lorsque l'arbre est pas vide, nous utilisons récursivité pour parcourir l'arbre et arriver là où est nécessaire

TreeNode* Tree::insert(TreeNode*& node, int d_IN){
     if(node == NULL)  // (1) If we are at the end of the tree place the value
         node = new TreeNode(d_IN);
     else if(d_IN < node->d_stored){  //(2) otherwise go left if smaller
         insert(node->left, d_IN);    
         if(Height(node->left) - Height(node->right) == 2){
            if(d_IN < node->left->d_stored)
                rotateLeftOnce(node);
            else
                rotateLeftTwice(node);
         }
     }
     else if(d_IN > node->d_stored){ // (3) otherwise go right if bigger
        insert(node->right, d_IN);
        if(Height(node->right) - Height(node->left) == 2){
            if(d_IN > node->right->d_stored)
                rotateRightOnce(node);
            else
                rotateRightTwice(node);
        }
     }
     return node;
}

Vous devriez toujours vérifier l'équilibre (et faire des rotations si nécessaire) lors de la modification de l'arbre, pas de point d'attendre la fin lorsque l'arbre est un gâchis pour l'équilibrer. Cela complique les choses simplement ...

---

UPDATE

Il y a une erreur dans votre mise en œuvre, dans le code ci-dessous vous ne vérifiez pas correctement si l'arbre est déséquilibré. Vous devez vérifier si la hauteur est égal à 2 (donc déséquilibre). En conséquence le code ci-dessous ...

if (height(current->lchild) - height(current->rchild)) { ...

if (height(current->rchild) - height(current->lchild)) {...

doit devenir ...

if (height(current->lchild) - height(current->rchild) == 2) { ...

if (height(current->rchild) - height(current->lchild) == 2) {...

---

Certaines ressources

• AVL Arbre ~ Imprementation en C ++
• AVL Arbre ~ Applet

Answer 2

Attendez, attendez, attendez. Tu ne vas pas vraiment vérifier la « hauteur » de chaque branche à chaque fois que vous insérez quelque chose, êtes-vous?

Mesurer les moyens de hauteur transversing tous les sous-branche. Moyens - chaque insertion dans l'arbre d'un tel coûtera O (N). Si oui - qu'est-ce que vous avez besoin d'un tel arbre? Vous pouvez utiliser un tableau trié ainsi: il donne O (N) insertion / suppression et O (log N) recherche

.

Un algorithme correct manipulation AVL must Magasin la différence de hauteur gauche / droite à chaque noeud. Puis, après chaque opération (insérer / enlever) - vous devez vous assurer qu'aucun des nœuds concernés sera trop déséquilibrée. Pour ce faire, vous faites les soi-disant « rotations ». Au cours de leur vous ne pas en fait remesurer les hauteurs. Vous n'avez tout simplement pas:. Chaque rotation modifie l'équilibre des nœuds concernés par une valeur prévisible

Answer 3

http://code.google.com/p/self- équilibre-AVL-arbre / , toutes les opérations habituelles comme ajouter, de supprimer sont mises en œuvre, plus concat et divisé

Answer 4

ont commenté sur le code ci-dessus et à droite rotate tourner à gauche, ci-dessous est mon droit et mon travail rotate Faire pivoter à gauche de travail. Je pense que la logique dans la rotation est inversée ci-dessus:

 void rotateRight(Node *& n){
    //Node* temp = n->right;
    //n->right = temp->left;
    //temp->left = n;
    //n = temp;
    cout << "}}}}}}}}}}}}}}}}}}}}}ROTATE RIGHT}}}}}}}}}}}}}}}}}}}}}" << endl;
    Node *temp = n->left;
    n->left = temp->right;
    temp->right = n;
    n = temp;
}

void rotateLeft(Node *& n){
    //Node *temp = n->left;
    //n->left = temp->right;
    //temp->right = n;
    //n = temp;
    cout << "}}}}}}}}}}}}}}}}}}}}}ROTATE LEFT}}}}}}}}}}}}}}}}}}}}}" << endl;
    Node* temp = n->right;
    n->right = temp->left;
    temp->left = n;
    n = temp;
}