AVL diccionario árbol

Question

Hasta ahora he estado elaborando un plan de ataque para ver cómo podía ir haciendo esto y esto es lo que tengo:

bool isEmpty() const - devuelve verdadero si está vacío, falso si no

int getSize() - devuelve cuántas palabras se almacena en el diccionario

void insert (String word) palabra -Insertar en el diccionario si no está ya presente, de lo contrario actualización.

boolfind(String word, WordNode & x) - devuelve true si la palabra está presente y coloca los datos en x.

void printSorted() - imprime las palabras del árbol en orden lexicográfico (especificado)

void remove (String word) -implements la eliminación perezosa de un nodo

que tienen el concepto de lo que quiero hacer, y yo entiendo cómo funcionan los árboles AVL. Pero me quedo completamente atrapado cuando se trata de escribir el código, ¿alguien puede ayudarme a empezar?

Answer 1

Comience por implementar un árbol binario simple (es decir, sin equilibrar), junto con el programa correspondiente para contar palabras en un archivo. Haz que funcione, entonces tendrás algo con lo que probar. No te preocupes por el equilibrio por el momento; esa es la parte realmente difícil.

Aquí es una función de inserción (no probado) para un simple árbol binario:

/* 
* Insert a new key into a binary tree, or find an existing one. 
* 
* Return the new or existing node whose key is equal to the one requested. 
* Update *node with the new (sub)tree root. 
*/ 
Node *insert(Node **node, String key) 
{ 
    if (*node == NULL) { 
     *node = new Node(key); 
     return *node; 
    } 

    if (key < (*node)->key) 
     return insert(&(*node)->left, key); 

    if (key > (*node)->key) 
     return insert(&(*node)->right, key); 

    return *node; 
} 

Una vez que tenga un simple trabajo árbol binario y probado, volver a implementar la función de inserción para realizar el equilibrio, que es el corazón de el algoritmo AVL.

empezar por conocer las invariantes de un árbol AVL:

• El factor de equilibrio de cualquier nodo (la diferencia entre la altura del niño izquierda y la altura del niño derecha) es o bien -1, 0 o 1 .
• Traversal en orden produce una orden de diccionario.

Recomiendo consultar el AVL tree insertion diagram en Wikipedia. Ilustra las cuatro rotaciones que necesitará implementar y dónde se necesitan.

Una rotación es necesaria cuando el factor de equilibrio de un nodo sale del alcance — en otras palabras, cuando la diferencia de altura entre el subárbol izquierdo y subárbol derecho es mayor que 1.

¿Cómo se determina el factor de equilibrio de un nodo? Bueno, algo de lo siguiente funcionará:

1. Añadir un miembro height a la estructura de nodos, y determinar el factor de equilibrio de cualquier nodo dado restando la altura del niño desde la altura del niño izquierda.
2. Agregue un miembro balance a la estructura de nodo. Esto puede ser un poco más difícil de entender, pero arroja un código más simple (creo).
3. Calcula alturas y saldos de los árboles por recorrido.Esto es ineficiente, tanto así que derrota el propósito de AVL. Sin embargo, es más fácil de entender y menos propenso a errores.

Recomiendo comenzar con el 3er enfoque, para que pueda probar su código de equilibrio antes.

Para aclarar lo que se entiende por "altura" y "factor de equilibrio", aquí están las funciones para calcular ellas:

int height(Node *node) 
{ 
    if (node == NULL) 
     return -1; 
    return std::max(height(node->left), height(node->right)) + 1; 
} 

int balanceFactor(Node *node) 
{ 
    assert(node != NULL); 
    return height(node->right) - height(node->left); 
} 

Averiguar cómo actualizar alturas o factores de balance de forma incremental va a implicar papel, lápiz , álgebra simple y sentido común.

Espero que esto ayude!