Les Arbres AVL

Le concept d'arbre avl, se rapporte à des arbres de recherche qui mesure la hauteur de leurs sous arbre gauche et droite de sorte qu'un algorithme de recherche soit en $\Theta(log(n))$, le plus long étant l'insertion (ré-balancement de l'arbre). On a donc un arbre binaire qui s'étale le plus possible :

La taille d'un arbre binaire est la taille maximale du chemin le plus long, un arbre vide à une taille de -1, un arbre avec 1 seul élément à une taille de 0 ... etc, le graphe ci-dessus a une taille de 5. On peu écire cette premiere définition de facon récursive :

int avltree::diff(leaf *temp)
{
    if(!temp) return -1;
    return height(temp->left) - height(temp->right);
}

int avltree::height(leaf *temp)
{
    return !temp ? 0 : 1 + std::max(
        height(temp->left),
        height(temp->right)
    );
}

code source complet

insertion d'un élément

Le nouvel élément est inséré comme dans un arbre binaire, mais après son insertion on vérifie la taille du sous arbre de tous ses parents et on effectue un équilibrage si nécessaire. On distingue 5 cas :

 // standar right rotation, including the parent update
template<>
inline leaf* avltree::rotation<right>(leaf *b)
{
    leaf *a = b->right;
    b->right = a->left;
    a->left = b;

    a->parent = b->parent;
    b->parent = a;

    if(b->right)
        b->right->parent = b;

    if(a->parent)
    {
        if(a->key < a->parent->key)
             a->parent->left = a;
        else a->parent->right = a;
    }

    return a;
}

// standar left rotation, including the parent update
template<>
inline leaf* avltree::rotation<left>(leaf *a)
{
    leaf *b = a->left;
    a->left = b->right;
    b->right = a;

    b->parent = a->parent;
    a->parent = b;

    if(a->left)
        a->left->parent = a;

    if(b->parent)
    {
        if(b->key < b->parent->key)
             b->parent->left = b;
        else b->parent->right = b;
    }

    return b;
}

template<>
inline leaf* avltree::rotation<left_right>(leaf *p)
{
    p->left = rotation<right>(p->left);
    return rotation<left>(p);
}

template<>
inline leaf* avltree::rotation<right_left>(leaf *p)
{
    p->right = rotation<left>(p->right);
    p->right->parent = p;
    return rotation<right>(p);
}

Donc a la suite de l'ajout d'une feuille dans l'arbre il faut corriger l'arbre pour faire respecter ces propriétés :

leaf* avltree::fix(leaf *tmp)
{
    if(!tmp)
        return nullptr;

    int bal_factor = diff(tmp);

    if(bal_factor > 1)
    {
        if(diff(tmp->left) > 0)
             tmp = rotation<left>(tmp);
        else tmp = rotation<left_right>(tmp);
    }
    else if(bal_factor < -1)
    {
        if(diff(tmp->right) > 0)
             tmp = rotation<right_left>(tmp);
        else tmp = rotation<right>(tmp);
    }

    return tmp;
}

leaf* avltree::balance(leaf *tmp)
{
    if(!tmp)
        return root;

    while(tmp->parent)
    {
        fix(tmp);
        tmp = tmp->parent;
    }

    fix(root->left);
    fix(root->right);

    return fix(root);
}

leaf* avltree::insert(int value, void *userdata)
{
    if(!root)
    {
        root = new leaf(value, nullptr, userdata);
        return root;
    }
    else
    {
        leaf *last = findlast(root, value);
        leaf *alloc = nullptr;

        if(!last)
            return root;
        else if(value < last->key && !last->left)
            alloc = last->left = new leaf(value, last, userdata);
        else if(value > last->key && !last->right)
            alloc = last->right = new leaf(value, last, userdata);
        else std::cout << "key " << value << " exist" << std::endl;

        root = balance(alloc);
        return alloc;
    }
}

suppression d'un élément

• on cherche l'élément (E)
• on cherche le minimum(M) a ça droite si le sous-arbre droite est plus grand
• on cherche le maximum(M) à ça gauche si le sous-arbre gauche est plus grand
• on détache un sous arbre a partir du minimum/maximum
  • soit on insère tous les éléments du sous arbre en mettant M
  • soit on ré-attache le sous arbre au parent de M à partir du nœud droit/gauche qu'il reste (puisque c'est un minimum/maximum il n'a qu'un seul enfant)

leaf* avltree::remove(int key)
{
    leaf *node;

    if(root && root->key == key && !root->asChild())
    {
        node = root;
        root = nullptr;
        return node;
    }
    else node = find(root, key);

    if(!node || node->key != key)
        return nullptr;

    leaf *removed = diff(node) < 0 ?
                    findmin(node->right) :
                    findmax(node->left);

    if(!removed)
        removed = node;

    if(removed)
    {
        printf("%d\n", removed->key);
        node->replace(removed);
        removed->detach();

        postorder_iterative(
            removed->left, this,
            [](leaf *a, void *data){
                avltree *tree = (avltree*)data;
                tree->insert(a->key, a->user);
                delete a;
            }
        );

        postorder_iterative(
            removed->right, this,
            [](leaf *a, void *data){
                avltree *tree = (avltree*)data;
                tree->insert(a->key, a->user);
                delete a;
            }
        );

        balance(removed->parent);
    }

    return removed;
}

Parcourir un arbre :

// inorder traversal, each iteration call @dosomethink with the current leaf as parameter
void avltree::inorder(leaf *tree, void *user, void(*dosomethink)(leaf*, void*))
{
    if(!tree) return;
    inorder(tree->left, user, dosomethink);
    dosomethink(tree, user);
    inorder(tree->right, user, dosomethink);
}

// preorder traversal, each iteration call @dosomethink with the current leaf as parameter
void avltree::preorder(leaf *tree, void *user, void(*dosomethink)(leaf*, void*))
{
    if(!tree) return;
    dosomethink(tree, user);
    preorder(tree->left, user, dosomethink);
    preorder(tree->right, user, dosomethink);
}

// postorder traversal, each iteration call @dosomethink with the current leaf as parameter
void avltree::postorder(leaf *tree, void *user, void(*dosomethink)(leaf*, void*))
{
    if(!tree) return;
    postorder(tree->left, user, dosomethink);
    postorder(tree->right, user, dosomethink);
    dosomethink(tree, user);
}

// iterative postorder traversal, each iteration call @dosomethink with the current leaf as parameter
void avltree::postorder_iterative(leaf *tree, void *user, void(*dosomethink)(leaf*, void*))
{
    std::stack<leaf*> s1, s2;
    s1.push(tree);
    
    while(!s1.empty())
    {
        leaf *node = s1.pop();
        if(node->left)  s1.push(node->left);
        if(node->right) s1.push(node->right);
        s2.push(node);
    }
      
    while(!s2.empty())
        dosomethink(s2.pop(), user);
}