¿Cómo generar un árbol AVL lo más desequilibrado posible?

Question

Vi esto en un documento y alguien argumentó que puede haber como mucho log (n) veces la rotación cuando eliminamos un nodo de un árbol AVL. Creo que podemos lograr esto generando un árbol AVL tan desequilibrado como sea posible. El problema es cómo hacer esto. Esto me ayudará mucho a investigar sobre la rotación de eliminación. ¡Muchas gracias!

Answer 1

Si desea hacer un árbol AVL máximo desequilibrada, que están buscando una Fibonacci tree, que se define de la siguiente manera inductiva:

• Un árbol de Fibonacci de orden 0 está vacía.
• Un árbol de Fibonacci de orden 1 es un nodo único.
árbol
• Un Fibonacci de orden n + 2 es un nodo cuyo hijo izquierdo es un árbol de Fibonacci de orden n, y cuyo derecho del niño es un árbol de Fibonacci de orden n + 1.

Por ejemplo, he aquí una de Fibonacci árbol de orden 5:

los árboles de Fibonacci representan la cantidad máxima de inclinación que un árbol AVL puede tener, ya que si el factor de equilibrio eran más desequilibrada el factor de equilibrio de cada nodo excedería los límites colocado por los árboles AVL.

Se puede usar esta definición para generar muy fácilmente árboles ladeados máximo 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." 

Espero que esto ayude!