Come generare un albero AVL il più spoglio possibile?

Question

L'ho visto su un foglio di carta e qualcuno ha obiettato che al momento della cancellazione di un nodo di un albero AVL può esserci al massimo il log (n) di rotazione. Credo che possiamo ottenere questo generando un albero AVL il più sbilenco possibile. Il problema è come farlo. Questo mi aiuterà molto nella ricerca della cosa di rotazione di rimozione. Grazie mille!

Answer 1

Se si vuole fare un albero al massimo sbilenco AVL, si sono alla ricerca di un Fibonacci tree, che è definito induttivamente come segue:

• Un Fibonacci albero di ordine 0 è vuoto.
• Un albero di ordine 1 di Fibonacci è un nodo singolo.
• Un Fibonacci albero di ordine n + 2 è un nodo il cui figlio sinistro è un albero di Fibonacci di ordine n e il cui diritto del bambino è un albero di Fibonacci di ordine n + 1.

Per esempio, ecco una Fibonacci albero di ordine 5:

gli alberi Fibonacci rappresentano la quantità massima di disallineamento che un albero AVL può avere, poiché se il fattore di equilibrio erano più squilibrata il fattore di equilibrio di ciascun nodo supererebbe i limiti locale dagli alberi AVL.

È possibile utilizzare questa definizione per generare molto facilmente al massimo sbilenco alberi AVL:

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." 

Spero che questo aiuti!