Comment générer un arbre AVL aussi déséquilibré que possible?

Question

J'ai vu cela dans un article et quelqu'un a fait valoir qu'il peut y avoir au plus la rotation du log (n) fois lorsque nous supprimons un nœud d'un arbre AVL. Je crois que nous pouvons y parvenir en générant un arbre AVL aussi déséquilibré que possible. Le problème est de savoir comment procéder. Cela m'aidera beaucoup à rechercher la recherche de rotation d'élimination. Merci beaucoup!

Answer 1

Si vous souhaitez faire un arbre AVL déséquilibré au maximum, vous recherchez un Arbre Fibonacci, qui est défini par induction comme suit:

• Un arbre Fibonacci d'ordre 0 est vide.
• Un arbre Fibonacci de l'ordre 1 est un seul nœud.
• Un arbre d'ordre de Fibonacci n + 2 est un nœud dont l'enfant gauche est un arbre d'ordre Fibonacci n et dont l'enfant droit est un arbre d'ordre Fibonacci n + 1.

Par exemple, voici un arbre Fibonacci de l'Ordre 5:

Les arbres Fibonacci représentent la quantité maximale de biais qu'un arbre AVL peut avoir, car si le facteur d'équilibre était plus déséquilibré, le facteur d'équilibre de chaque nœud dépasserait les limites placées par les arbres AVL.

Vous pouvez utiliser cette définition pour générer très facilement des arbres AVL déséquilibrés au maximum:

function FibonacciTree(int order) {
    if order = 0, return the empty tree.
    if order = 1, create a single node and return it.
    otherwise:
        let left  = FibonacciTree(order - 2)
        let right = FibonacciTree(order - 1)
        return a tree whose left child is "left" and whose right child is "right."

J'espère que cela t'aides!