balanceando un árbol AVL (C++)

Question

Me está costando más tiempo tratar de encontrar la forma de equilibrar un árbol AVL para mi clase. Tengo que insertando con esto:

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

Mi plan era que las llamadas a equilibrar() comprobar para ver si las necesidades de los árboles de equilibrado y después equilibrar según sea necesario. El problema es que no puedo imaginar cómo atravesar el árbol para encontrar el nodo desequilibrado correcto. Sé cómo recorrer el árbol recursivamente, pero parece que no puedo traducir ese algoritmo para encontrar el nodo desequilibrado más bajo. También estoy teniendo problemas para escribir un algoritmo iterativo. Cualquier ayuda sería apreciada. :)

Answer 1

se puede medir el height de una rama en un punto dado para calcular el desequilibrio

(recordar una diferencia de altura (niveles)> = 2 significa que el árbol no está equilibrado)

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

Dependiendo de la irregularidad, entonces se puede girar como sea necesario

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

Ahora que sabemos cómo girar, digamos que usted quiere inserción un valor en el árbol ... En primer lugar, comprobamos si el árbol está vacía 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" 
} 

Cuando el árbol no es vacío utilizamos recursividad para atravesar el árbol y llegar a donde se necesita

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

siempre se debe comprobar si hay equilibrio (y hacer rotaciones si es necesario) al modificar el árbol, no hay punto de espera hasta el final cuando el árbol es un desastre para equilibrarlo. Eso sólo complica las cosas ...

---

ACTUALIZACIÓN

Hay un error en su aplicación, en el siguiente código no está mirando correctamente si el árbol está desequilibrada. Debe verificar si la altura es igual a 2 (por lo tanto, desequilibrio). Como resultado, el código de abajo ...

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

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

de ser éste ...

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

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

---

Algunos Recursos

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

Answer 2

Espera, espera, espera. Realmente no va a verificar la "altura" de cada rama cada vez que inserta algo, ¿verdad?

Medir la altura significa atravesar toda la subrama. Medios: cada inserción en un árbol de este tipo costará O (N). Si es así, ¿qué necesita un árbol así? También puede usar una matriz ordenada: da O (N) inserción/eliminación y O (registro N) de búsqueda.

Un algoritmo de manejo de AVL correcto debe almacenar la diferencia de altura izquierda/derecha en cada nodo. Luego, después de cada operación (insertar/eliminar), debe asegurarse de que ninguno de los nodos afectados esté demasiado desequilibrado. Para hacer esto, haz lo que se llama "rotaciones". Durante ellos, no realmente vuelven a medir las alturas. Simplemente no es necesario: cada rotación cambia el equilibrio de los nodos afectados por un valor predecible.

Answer 3

Goto http://code.google.com/p/self-balancing-avl-tree/, todas las operaciones habituales, como añadir, borrar se implementan, además concat y dividir

Answer 4

comentada es el código de la derecha arriba y gire Girar a la izquierda, a continuación es mi trabajo y mi derecha girar trabajando de izquierda rotación. Creo que la lógica en la rotación anterior se invierte:

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