La meilleure façon de calculer la hauteur dans un arbre de recherche binaire ? (équilibrer un arbre AVL)

Question

Je cherche la meilleure façon de calculer un solde de nœuds dans un système de gestion de l'information. Arbre AVL . Je pensais l'avoir fait fonctionner, mais après quelques insertions et mises à jour importantes, je constate qu'il ne fonctionne pas correctement (du tout).

Il s'agit d'une question en deux parties, la première étant comment calculer la hauteur d'un sous-arbre, je connais la définition. "La hauteur d'un nœud est la longueur du plus long chemin descendant vers une feuille à partir de ce nœud." et je le comprends, mais je n'arrive pas à le mettre en œuvre. Et pour m'embrouiller encore plus, cette citation se trouve sur wikipedia sur la hauteur des arbres "Par convention, la valeur -1 correspond à un sous-arbre ne comportant aucun nœud, tandis que zéro correspond à un sous-arbre comportant un nœud."

Et la deuxième partie consiste à obtenir le facteur d'équilibre d'un sous-arbre dans un arbre AVL, je n'ai aucun problème à comprendre le concept, "obtenir la hauteur de votre L y R sous-arbres et soustraire R de L " . Et ceci est défini comme quelque chose comme ceci : BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]

La lecture sur wikipedia dit ceci sur les premières lignes décrivant les insertions dans un arbre AVL : "Si le facteur d'équilibre devient -1, 0 ou 1, alors l'arbre est toujours sous forme AVL, et aucune rotation n'est nécessaire."

Il poursuit ensuite en disant ceci "Si le facteur d'équilibre devient 2 ou -2, alors l'arbre enraciné à ce nœud est déséquilibré, et une rotation de l'arbre est nécessaire. Au maximum, une rotation simple ou double sera nécessaire pour équilibrer l'arbre." - ce que je n'ai aucun mal à comprendre.

Mais (oui, il y a toujours un mais).

C'est là que ça devient confus, le texte dit "Si le facteur d'équilibre de R est égal à 1, cela signifie que l'insertion a eu lieu sur le côté droit (externe) de ce nœud et qu'une rotation vers la gauche est nécessaire". . Mais d'après ce que j'ai compris, le texte disait (comme je l'ai cité) que si le facteur d'équilibre se situait dans les limites de l'UE, il n'y avait pas de problème. [-1, 1] alors il n'y avait pas besoin d'équilibrage ?

J'ai l'impression d'être si proche de la compréhension du concept, j'ai mis au point les rotations d'arbres, implémenté un arbre de recherche binaire normal, et je suis sur le point de comprendre les arbres AVL, mais il me semble qu'il me manque cette épiphanie essentielle.

Editar: Je préfère les exemples de code aux formules académiques, car j'ai toujours eu plus de facilité à comprendre quelque chose en code, mais toute aide est la bienvenue.

Editar: J'aimerais pouvoir marquer toutes les réponses comme "acceptées", mais pour moi, la réponse de NIck est la première qui m'a fait "aha".

Answer 1

Eh bien, vous pouvez calculer la hauteur d'un arbre avec la fonction récursive suivante :

int height(struct tree *t) {
    if (t == NULL)
        return 0;
    else
        return max(height(t->left), height(t->right)) + 1;
}

avec une définition appropriée de max() y struct tree . Vous devriez prendre le temps de comprendre pourquoi cela correspond à la définition basée sur la longueur du chemin que vous citez. Cette fonction utilise zéro comme hauteur de l'arbre vide.

Cependant, pour quelque chose comme un arbre AVL, je ne pense pas que l'on calcule réellement la hauteur à chaque fois que l'on en a besoin. Au lieu de cela, chaque nœud de l'arbre est augmenté d'un champ supplémentaire qui se souvient de la hauteur du sous-arbre enraciné à ce nœud. Ce champ doit être maintenu à jour lorsque l'arbre est modifié par des insertions et des suppressions.

Je soupçonne que, si vous calculez la hauteur à chaque fois au lieu de la mettre en cache dans l'arbre comme suggéré ci-dessus, la forme de l'arbre AVL sera correcte, mais elle n'aura pas les performances logarithmiques attendues.

Answer 2

C'est là que ça devient confus, le texte dit "Si le facteur d'équilibre de R est 1, cela signifie que l'insertion s'est produite sur le côté droit (externe) de ce nœud et qu'une rotation vers la gauche est nécessaire". Mais si j'ai bien compris, le texte dit (comme je l'ai cité) que si le facteur d'équilibre est compris entre [-1, 1], il n'y a pas besoin d'équilibrage ?

R est l'enfant de droite du noeud actuel N .

Si balance(N) = +2 alors vous avez besoin d'une sorte de rotation. Mais quelle rotation utiliser ? Eh bien, cela dépend de balance(R) : si balance(R) = +1 alors vous avez besoin d'une rotation à gauche sur N mais si balance(R) = -1 alors vous aurez besoin d'une sorte de double rotation.

Answer 3

Donnez BinaryTree<T, Comparator>::Node a subtreeHeight initialisé à 0 dans son constructeur, et mis à jour automatiquement à chaque fois avec :

template <typename T, typename Comparator>
inline void BinaryTree<T, Comparator>::Node::setLeft (std::shared_ptr<Node>& node) {
    const std::size_t formerLeftSubtreeSize = left ? left->subtreeSize : 0;
    left = node;
    if (node) {
        node->parent = this->shared_from_this();
        subtreeSize++;
        node->depthFromRoot = depthFromRoot + 1;
        const std::size_t h = node->subtreeHeight;
        if (right)
            subtreeHeight = std::max (right->subtreeHeight, h) + 1;
        else
            subtreeHeight = h + 1;
    }
    else {
        subtreeSize -= formerLeftSubtreeSize;
        subtreeHeight = right ? right->subtreeHeight + 1 : 0;
    }
}

template <typename T, typename Comparator>
inline void BinaryTree<T, Comparator>::Node::setRight (std::shared_ptr<Node>& node) {
    const std::size_t formerRightSubtreeSize = right ? right->subtreeSize : 0;
    right = node;
    if (node) {
        node->parent = this->shared_from_this();
        subtreeSize++;
        node->depthFromRoot = depthFromRoot + 1;
        const std::size_t h = node->subtreeHeight;
        if (left)
            subtreeHeight = std::max (left->subtreeHeight, h) + 1;
        else
            subtreeHeight = h + 1;
    }
    else {
        subtreeSize -= formerRightSubtreeSize;
        subtreeHeight = left ? left->subtreeHeight + 1 : 0;
    }
}

Notez que les membres de données subtreeSize y depthFromRoot sont également mis à jour. Ces fonctions sont appelées lors de l'insertion d'un nœud (tous testés), par exemple.

template <typename T, typename Comparator>
inline std::shared_ptr<typename BinaryTree<T, Comparator>::Node>
BinaryTree<T, Comparator>::Node::insert (BinaryTree& tree, const T& t, std::shared_ptr<Node>& node) {
    if (!node) {
        std::shared_ptr<Node> newNode = std::make_shared<Node>(tree, t);
        node = newNode;
        return newNode;
    }
    if (getComparator()(t, node->value)) {
        std::shared_ptr<Node> newLeft = insert(tree, t, node->left);
        node->setLeft(newLeft);
    }
    else {
        std::shared_ptr<Node> newRight = insert(tree, t, node->right);
        node->setRight(newRight);
    }
    return node;
}

Si vous supprimez un nœud, utilisez une autre version de removeLeft y removeRight en remplaçant subtreeSize++; con subtreeSize--; . Algorithmes pour rotateLeft y rotateRight peut être adapté sans trop de problèmes non plus. Les éléments suivants ont été testés et approuvés :

template <typename T, typename Comparator>
void BinaryTree<T, Comparator>::rotateLeft (std::shared_ptr<Node>& node) {  // The root of the rotation is 'node', and its right child is the pivot of the rotation.  The pivot will rotate counter-clockwise and become the new parent of 'node'.
    std::shared_ptr<Node> pivot = node->right;
    pivot->subtreeSize = node->subtreeSize;
    pivot->depthFromRoot--;
    node->subtreeSize--;  // Since 'pivot' will no longer be in the subtree rooted at 'node'.
    const std::size_t a = pivot->left ? pivot->left->subtreeHeight + 1 : 0;  // Need to establish node->heightOfSubtree before pivot->heightOfSubtree is established, since pivot->heightOfSubtree depends on it.
    node->subtreeHeight = node->left ? std::max(a, node->left->subtreeHeight + 1) : std::max<std::size_t>(a,1);
    if (pivot->right) {
        node->subtreeSize -= pivot->right->subtreeSize;  // The subtree rooted at 'node' loses the subtree rooted at pivot->right.
        pivot->subtreeHeight = std::max (pivot->right->subtreeHeight, node->subtreeHeight) + 1;
    }
    else
        pivot->subtreeHeight = node->subtreeHeight + 1;
    node->depthFromRoot++;
    decreaseDepthFromRoot(pivot->right);  // Recursive call for the entire subtree rooted at pivot->right.
    increaseDepthFromRoot(node->left);  // Recursive call for the entire subtree rooted at node->left.
    pivot->parent = node->parent;
    if (pivot->parent) {  // pivot's new parent will be its former grandparent, which is not nullptr, so the grandparent must be updated with a new left or right child (depending on whether 'node' was its left or right child).
        if (pivot->parent->left == node)
            pivot->parent->left = pivot;
        else
            pivot->parent->right = pivot;
    }
    node->setRightSimple(pivot->left);  // Since pivot->left->value is less than pivot->value but greater than node->value.  We use the NoSizeAdjustment version because the 'subtreeSize' values of 'node' and 'pivot' are correct already.
    pivot->setLeftSimple(node);
    if (node == root) {
        root = pivot;
        root->parent = nullptr; 
    }
}

où

inline void decreaseDepthFromRoot (std::shared_ptr<Node>& node) {adjustDepthFromRoot(node, -1);}
inline void increaseDepthFromRoot (std::shared_ptr<Node>& node) {adjustDepthFromRoot(node, 1);}

template <typename T, typename Comparator>
inline void BinaryTree<T, Comparator>::adjustDepthFromRoot (std::shared_ptr<Node>& node, int adjustment) {
    if (!node)
        return;
    node->depthFromRoot += adjustment;
    adjustDepthFromRoot (node->left, adjustment);
    adjustDepthFromRoot (node->right, adjustment);
}

Voici le code complet : http://ideone.com/d6arrv

Answer 4

Cette solution de type BFS est assez simple. Il suffit de sauter les niveaux un par un.

def getHeight(self,root, method='links'):
    c_node = root
    cur_lvl_nodes = [root]
    nxt_lvl_nodes = []
    height = {'links': -1, 'nodes': 0}[method]

    while(cur_lvl_nodes or nxt_lvl_nodes):
        for c_node in cur_lvl_nodes:
            for n_node in filter(lambda x: x is not None, [c_node.left, c_node.right]):
                nxt_lvl_nodes.append(n_node)

        cur_lvl_nodes = nxt_lvl_nodes
        nxt_lvl_nodes = []
        height += 1

    return height