simple - equilibrando un árbol AVL(C++)

rotacion simple a la izquierda

Question

Estoy teniendo dificultades para descubrir cómo equilibrar un árbol AVL para mi clase. Lo tengo 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 hacer que las llamadas a balance () se verifiquen para ver si el árbol necesita equilibrio y luego se equilibra según sea necesario. El problema es que ni siquiera puedo averiguar cómo atravesar el árbol para encontrar el nodo desequilibrado correcto. Sé cómo atravesar el árbol de forma recursiva, 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

Comentando es el código a la derecha, girar arriba y abajo a la izquierda, a continuación está mi trabajo a la derecha girar y mi trabajo a la izquierda girar. Creo que la lógica en la rotación anterior está invertida:

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

Answer 2

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

Medir la altura significa atravesar toda la sub-rama. Medios: cada inserción en dicho árbol costará O (N). Si es así, ¿qué necesitas de tal árbol? También puede usar una matriz ordenada: proporciona O (N) inserción / eliminación y O (registro N) 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 / quitar), debe asegurarse de que ninguno de los nodos afectados esté demasiado desequilibrado. Para ello se realizan las denominadas "rotaciones". Durante ellos no vuelves a medir las alturas. Simplemente no tiene que hacerlo: cada rotación cambia el balance de los nodos afectados por algún valor predecible.

Answer 3

Puede medir la height de una rama en un punto determinado para calcular el desequilibrio

(recuerde una diferencia en altura (niveles)> = 2 significa que su á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, puede rotar según 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 rotar, digamos que desea insertar un valor en el árbol ... Primero verificamos si el árbol está vacío 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 está vacío, utilizamos la recursión 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 debe verificar el equilibrio (y hacer rotaciones si es necesario) al modificar el árbol, no tiene que esperar hasta el final cuando el árbol está desordenado para equilibrarlo. Eso solo complica las cosas ...

ACTUALIZAR

Hay un error en su implementación, en el código a continuación no está comprobando correctamente si el árbol está desequilibrado. Debe comprobar 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)) {...

Debe convertirse...

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

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

Algunos recursos

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

Answer 4

Vaya a http://code.google.com/p/self-balancing-avl-tree/ , se implementan todas las operaciones habituales como agregar, eliminar, concat y split