Balancieren eines AVL-Baumes (C++)

Question

Ich habe die schwierigste Zeit herauszufinden, wie man einen AVL-Baum für meine Klasse ausbalanciert. Ich habe das Einfügen es mit diesem:

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; 
} 

Mein Plan, die Anrufe zu haben war zu balancieren() überprüfen, um zu sehen, ob der Baum Bedürfnisse Ausgleich und dann je nach Bedarf ausgleichen. Das Problem ist, ich kann nicht einmal herausfinden, wie man den Baum durchquert, um den richtigen unausgeglichenen Knoten zu finden. Ich weiß, wie man den Baum rekursiv durchläuft, aber ich kann diesen Algorithmus nicht so übersetzen, dass er den niedrigsten unsymmetrischen Knoten findet. Ich habe auch Probleme beim Schreiben eines iterativen Algorithmus. Jede Hilfe wäre willkommen. :)

Answer 1

Sie können die height einer Verzweigung an einer bestimmten Stelle messen die Unwucht

zu berechnen (denken Sie daran, einen Unterschied in der Höhe (Level)> = 2 bedeutet, dass Ihr Baum ist nicht ausgewogen)

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; 
} 

auf die Unebenheit Je dann können Sie drehen wie nötig

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); 
} 

Jetzt, da wir wissen, wie zu drehen, können Sie sagen ein Wert im Baum einfügen wollen ... Zuerst prüfen wir, ob der Baum leer oder nicht

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" 
} 

Wenn der Baum nicht ist leer wir verwenden Rekursion den Baum zu durchqueren und gelangen an, wo

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; 
} 

Sie immer für die Balance (und tun Umdrehungen falls erforderlich) benötigt wird, überprüfen sollten, Wenn man den Baum ändert, wartet kein Punkt mehr bis zum Ende, wenn der Baum ein Durcheinander ist, um ihn auszugleichen. Das verkompliziert die Dinge nur ...

---

UPDATE

Es ist ein Fehler in der Implementierung, in dem folgenden Code nicht korrekt überprüft, ob der Baum unausgeglichen ist. Sie müssen prüfen, ob die Höhe gleich 2 ist (daher Unwucht). Als Ergebnis der Code unten ...

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

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

werden sollen ...

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

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

---

Einige Ressourcen

• AVL Tree ~ Imprementation in C++
• AVL Tree ~ Applet

Answer 2

Warte, warte, warte. Sie werden nicht wirklich jedes Mal, wenn Sie etwas einfügen, die "Höhe" jedes Zweiges überprüfen, oder?

Die Messung der Höhe bedeutet, dass der gesamte Unterzweig transversiert wird. Mittel - jede Einfügung in einen solchen Baum kostet O (N). Wenn ja - wofür brauchen Sie einen solchen Baum? Sie können auch ein sortiertes Array verwenden: es gibt O (N) -Einfügung/Löschung und O (Protokoll N) -Suche.

Ein korrekter AVL-Verarbeitungsalgorithmus muss den linken/rechten Höhenunterschied an jedem Knoten speichern. Dann, nach jeder Operation (einfügen/entfernen) - müssen Sie sicherstellen, dass keiner der betroffenen Knoten zu sehr unausgeglichen ist. Dazu machen Sie die sogenannten "Rotationen". Während sie nicht tatsächlich die Höhen messen. Sie müssen es einfach nicht: Jede Rotation verändert das Gleichgewicht der betroffenen Knoten um einen vorhersehbaren Wert.

Answer 3

goto http://code.google.com/p/self-balancing-avl-tree/ alle üblichen Operationen wie Hinzufügen, Löschen umgesetzt werden, sowie Concat und spaltete

Answer 4

kommentiert out ist der Code rechts drehen oben und links drehen, unter meiner Arbeit nach rechts drehen und meine links drehen arbeiten. Ich denke, die Logik in der oben drehen inversed ist:

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; 
}