AVL arbre dictionnaire

Question

Jusqu'à présent, je dessine un plan d'attaque pour voir comment je pourrais continuer à faire cela et ce que j'ai:

bool isEmpty() const - renvoie true si elle est vide, false sinon

int getSize() - Retourne le nombre de mots sont stockés dans le dictionnaire

void insert (String word) -Insérer mot dans le dictionnaire, sinon déjà, mise à jour d'autre.

boolfind(String word, WordNode & x) -. Renvoie true si le mot est des données actuelles et placer dans x

void printSorted() - imprime les mots dans l'arborescence dans l'ordre lexicographique (spécifié)

void remove (String word) -implements la suppression d'un noeud paresseux

J'ai le concept de ce que je veux faire descendre, et je comprends comment fonctionnent les arbres AVL. Mais je me complètement coincé quand il s'agit en train d'écrire le code, l'aide peut quiconque me commencer?

Answer 1

Commencez par la mise en œuvre d'un arbre binaire simple (qui est, sans équilibrage), ainsi que le programme correspondant à compter les mots dans un fichier. Obtenez ce travail, de sorte que vous aurez quelque chose à tester avec. Ne vous inquiétez pas d'équilibrer tout de suite; c'est la partie vraiment difficile.

Voici une fonction d'insertion (non testé) pour un simple arbre binaire:

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

Une fois que vous avez simple travail d'arbre binaire et testé, re-mettre en œuvre la fonction d'insertion pour effectuer l'équilibrage, qui est le coeur de l'algorithme de AVL.

Commencez par connaître les invariants d'un arbre AVL:

• Le facteur d'équilibre d'un nœud (la différence entre la taille de l'enfant gauche et de la taille de l'enfant droit) est soit -1, 0 ou +1.
• Dans traversal ordre produit un ordre du dictionnaire.

Je recommande référence à la AVL diagramme d'insertion arbre sur Wikipedia. Il illustre les quatre rotations, vous aurez besoin de mettre en œuvre et où ils sont nécessaires.

Une rotation est nécessaire lorsque le facteur d'équilibre d'un noeud est hors de portée, en d'autres termes, lorsque la différence de hauteur entre le sous-arbre gauche du sous-arbre droit est supérieur à 1.

Comment déterminez-vous le facteur d'équilibre d'un nœud? Eh bien, une des conditions suivantes fonctionnera:

1. Ajouter un membre de height à la structure du noeud, et déterminer le facteur d'équilibre d'un nœud donné en soustrayant la hauteur de l'enfant dès la taille de l'enfant gauche.
2. Ajouter un membre de balance à la structure de nœud. Cela pourrait être un peu plus difficile à comprendre, mais il donne un code plus simple (je pense).
3. Calculer la hauteur des arbres et des soldes par traversal. Ceci est inefficace, si bien qu'il défaites dans le but de AVL. Cependant, il est plus facile à comprendre et moins sujettes aux bugs.

Je recommande de commencer avec la 3ème approche, afin que vous puissiez tester plus tôt votre code d'équilibre.

Pour préciser ce qu'on entend par « hauteur » et « facteur d'équilibre », voici les fonctions pour les calculer:

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

Comprendre comment mettre à jour des hauteurs ou des facteurs d'équilibre est progressivement va impliquer le papier, crayon, algèbre simple, et le bon sens.

J'espère que cela aide!