bilanciamento di un albero AVL (C++)

Question

Sto provando il momento più difficile cercando di capire come bilanciare un albero AVL per la mia classe. Ce l'ho Caricamento con questo:

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

Il mio piano era quello di avere le chiamate per bilanciare() controllare per vedere se le esigenze degli alberi di bilanciamento e quindi l'equilibrio, se necessario. Il problema è che non riesco nemmeno a capire come attraversare l'albero per trovare il nodo sbilanciato corretto. So come attraversare l'albero in modo ricorsivo, ma non riesco a tradurre quell'algoritmo nel trovare il nodo meno equilibrato. Sto anche avendo problemi a scrivere un algoritmo iterativo. Qualsiasi aiuto sarebbe apprezzato. :)

Answer 1

È possibile misurare la height di un ramo in un dato punto per calcolare lo squilibrio

(ricordate un dislivello (livelli)> = 2 significa che il vostro albero non è bilanciato)

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

a seconda del dislivello allora si può ruotare se necessario

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

Ora che sappiamo come ruotare, diciamo che si desidera inserto un valore nella struttura ... Prima controlliamo se l'albero è vuoto o no

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

Quando l'albero non è vuoto usiamo ricorsione per attraversare l'albero e arriviamo al punto in cui è necessario

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

si dovrebbe sempre verificare la presenza di equilibrio (e fare le rotazioni, se necessario) quando si modifica l'albero, nessun punto attende fino alla fine quando l'albero è un disastro per bilanciarlo. Che proprio complica le cose ...

---

UPDATE

C'è un errore nell'implementazione, nel seguente codice non si sta verificando in modo corretto se l'albero è sbilanciato. È necessario verificare se l'altezza è uguale a 2 (quindi squilibrio). Di conseguenza, il codice di muggito ...

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

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

dovrebbe diventare ...

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

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

---

alcune risorse

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

Answer 2

Attendere, attendere, attendere. Non hai intenzione di controllare l'altezza di ogni ramo ogni volta che inserisci qualcosa, vero?

Misurare l'altezza significa attraversare tutto il ramo secondario. Mezzi: ogni inserto in tale albero avrà un costo di O (N). Se è così - cosa ti serve un albero del genere? Si può anche usare un array ordinato: dà O (N) inserimento/cancellazione e O (log N) search.

Un algoritmo di gestione AVL corretto deve memorizzare la differenza di altezza sinistra/destra su ciascun nodo. Quindi, dopo ogni operazione (inserimento/rimozione) - è necessario accertarsi che nessuno dei nodi interessati sia troppo sbilanciato. Per fare questo fai le cosiddette "rotazioni". Durante di essi, non è possibile effettuare il controllo delle altezze dello . Semplicemente non devi: ogni rotazione cambia il bilancio dei nodi interessati di un certo valore prevedibile.

Answer 3

goto http://code.google.com/p/self-balancing-avl-tree/, tutte le operazioni, come al solito aggiungere, eliminare sono implementate, oltre concat e dividere

Answer 4

commentato out è il codice giusto ruotare sopra e rotazione a sinistra, al di sotto è il mio lavoro e la mia destra ruotare working sinistra Ruota. Credo che la logica della rotazione di cui sopra è invertita:

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