c - programa - avl tree

Cómo generar árboles AVL maximamente desequilibrados

Question

He escrito una biblioteca en lenguaje C de árboles AVL como contenedores ordenados de propósito general . Para propósitos de prueba, me gustaría tener una forma de llenar un árbol para que esté al máximo desequilibrado, es decir, para que tenga la altura máxima para el número de nodos que contiene.

Los árboles AVL tienen la bonita propiedad de que si, a partir del árbol vacío, inserta nodos en orden ascendente (o descendente), el árbol siempre está exactamente equilibrado (es decir, tiene su altura mínima para un número dado de nodos). Una secuencia de claves enteras que genera un árbol AV _{n de} AVL exactamente equilibrado para cada número de nodos n, a partir del árbol vacío T ₀ , es simplemente

• k ₁ = 0
• k _{n + 1} = k _n +1, es decir, k _n = n-1

Estoy buscando una secuencia (con suerte simple) de claves enteras que, cuando se insertan en el árbol T ₀ inicialmente vacío, generan árboles AVL T ₀ , ..., T _n que están totalmente desbalanceados.

También me interesaría una solución donde solo el último árbol, T _n , esté desbalanceado al máximo (el número de nodos n sería un parámetro del algoritmo).

Una solución que satisface la restricción.

• max (k ₁ , ..., k _n ) - min (k ₁ , ..., k _n ) + 1 ≤ 2 n

Es preferible, pero no estrictamente requerido. Un rango clave de 4 n en lugar de 2 n puede ser un objetivo razonable.

No he podido encontrar nada en Internet con respecto a la generación, por inserción, de árboles AVL de altura máxima. Por supuesto, la secuencia de árboles generados que estoy buscando incluirá todos los llamados árboles de Fibonacci, que son los árboles AVL de una profundidad dada con el número mínimo de nodos. Curiosamente, la Wikipedia en inglés ni siquiera menciona los árboles de Fibonacci (¡ni los números de Fibonacci!) En el artículo sobre árboles AVL, mientras que la Wikipedia en alemán tiene un article muy bueno que está completamente dedicado a ellos. Pero todavía estoy en la oscuridad con respecto a mi pregunta.

Los trucos del lenguaje C son los trucos.

Answer 1

He encontrado esta respuesta a mi pregunta, pero sigo esperando que se pueda encontrar un algoritmo más simple y, sobre todo, más eficiente en el tiempo y no menos eficiente en el espacio, con suerte con propiedades de rango clave mucho mejores.

La idea es generar los árboles de Fibonacci hasta una altura determinada (que debe conocerse de antemano), evitando por completo todas las rotaciones de los árboles. Los árboles intermedios se mantienen equilibrados en AVL mediante la elección del orden de inserción. Dado que tienen la altura del más bajo de los dos árboles de Fibonacci que enlazan, todos están al máximo desequilibrados.

Las inserciones se realizan al insertar virtualmente todos los nodos en la secuencia de árboles de Fibonacci, pero, para cada árbol virtual, se insertan efectivamente solo los nodos que son subárboles de altura 1. Estos son los nodos "incrementales" entre dos árboles de Fibonacci consecutivos.

Así es como funciona en el caso max_height = 5 :

insert 0
=> Fibonacci tree of height 1 (1 node):
0
insert 8
=> Fibonacci tree of height 2 (2 nodes):
0
8
insert -8
insert 12
=> Fibonacci tree of height 3 (4 nodes):
0
-8 8
12
insert -4
insert 4
insert 14
=> Fibonacci tree of height 4 (7 nodes):
0
-8 8
-4 4 12
14
insert -12
insert -2
insert 6
insert 10
insert 15
=> Fibonacci tree of height 5 (12 nodes):
0
-8 8
-12 -4 4 12
-2 6 10 14
15

Y aquí está el código (simplificado):

void fibonacci_subtree(int root, int height, int child_delta)
{
if (height == 1) {
insert_into_tree(root);
} else if (height == 2) {
insert_into_tree(root + child_delta);
} else if (height >= 3) {
fibonacci_subtree(root - child_delta, height - 2, child_delta >> 1);
fibonacci_subtree(root + child_delta, height - 1, child_delta >> 1);
}
}
...
for (height = 1; height <= max_height; height++) {
fibonacci_subtree(0, height, 1 << (max_height - 2));
}

ACTUALIZAR

La solución de godel9 resuelve el problema de la propagación de las claves de esta solución. Aquí está la salida del código de godel9:

insert 0
=> Fibonacci tree of height 1 (1 node):
0
insert 3
=> Fibonacci tree of height 2 (2 nodes):
0
3
insert -3
insert 5
=> Fibonacci tree of height 3 (4 nodes):
0
-3 3
5
insert -2
insert 1
insert 6
=> Fibonacci tree of height 4 (7 nodes):
0
-3 3
-2 1 5
6
insert -4
insert -1
insert 2
insert 4
insert 7
=> Fibonacci tree of height 5 (12 nodes):
0
-3 3
-4 -2 1 5
-1 2 4 6
7

Y aquí está el código en la versión más cercana a la mía (aquí con una matriz estática de fibs ):

static int fibs[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170 };
void fibonacci_subtree(int root, int height, int *fib)
{
if (height == 1) {
insert_into_tree(root);
} else if (height == 2) {
insert_into_tree(root + *fib);
} else if (height >= 3) {
fibonacci_subtree(root - *fib, height - 2, fib - 2);
fibonacci_subtree(root + *fib, height - 1, fib - 1);
}
}
...
for (height = 1; height <= max_height; height++) {
fibonacci_subtree(0, height, fibs + max_height - 1);
}

El último árbol de Fibonacci de altura H tiene F _{H + 2} - 1 nodos sin "agujeros" entre los valores clave, y tiene k _max - k _root = F _{H + 1} - 1. El rango de teclas se puede colocar convenientemente, si es necesario , compensando el valor clave de la raíz e, opcionalmente, intercambiando izquierda y derecha en el algoritmo.

Lo que queda sin resolver es el llenado compacto de cualquier rango de clave dado con claves enteras (mientras que es trivial para árboles exactamente equilibrados). Con este algoritmo, si desea hacer un árbol máximo desequilibrado con n nodos (con teclas de números enteros), donde n no es un número de Fibonacci - 1, y desea el menor rango posible de teclas, puede encontrar la primera altura que pueda acomode n nodos, y luego ejecute el algoritmo para esta altura, pero deteniéndose cuando se hayan insertado n nodos. Quedarán varios "agujeros" (en el peor de los casos, ca. n / φ ≅ n / 1.618).

Al contrario de lo que era mi entendimiento intuitivo cuando escribí la introducción a esta solución, la eficiencia de tiempo de este algoritmo, con o sin la mejora importante de godel9, ya es óptima, ya que es O (n) (de modo que cuando se incluyen las inserciones , se convierte en O (n log n)). Esto se debe a que el número de operaciones es proporcional a la suma de los nodos de todos los árboles de Fibonacci de T _{F 1} = T ₁ a T _{F H} = T _n , es decir, N = Σ _{h = 1 ... H} (F _{h + 2} - 1) = F _{H + 4} - H - 1. Pero dos números de Fibonacci consecutivos tienen la proporción asintótica ≅ ≅ 1.618, la proporción áurea , de modo que N / n ≅ ² ≅ 2.618. Puede comparar esto con árboles binarios completamente equilibrados, donde se aplican fórmulas muy similares, solo con un "logaritmo" de 2 en lugar de φ.

Aunque dudo que valga la pena deshacerse del factor φ ² , teniendo en cuenta la simplicidad del código actual, aún es interesante tener en cuenta lo siguiente: cuando agrega los nodos "incrementales" de cualquier árbol de Fibonacci intermedio de altura h, La diferencia entre dos teclas consecutivas de esta "frontera de Fibonacci" (mi término) es F _{H-h + 3} o F _{H-h + 4} , en un patrón alternativo peculiar. Si conociéramos una regla de generación para estas diferencias, posiblemente podríamos llenar el árbol simplemente con dos bucles anidados.

Answer 2

Interesante pregunta. Parece que ya tienes una buena solución, pero encontraría más fácil un enfoque combinatorio.

Suposiciones

• Sea U (n) el número de nodos en un árbol AVL de altura n con desequilibrio máximo.

• U (0) = 0

• U (1) = 1

• U (n) = U (n-1) + U (n-2) + 1 para n> = 2 (es decir, un nodo raíz más dos subárboles con desequilibrio máximo)

• Para mayor comodidad, supongamos que U (n-1) es siempre el subárbol izquierdo, y U (n-2) siempre es el derecho.

• Deje que cada nodo esté representado por una cadena única que representa la ruta desde la raíz hasta el nodo. El nodo raíz es la cadena de caracteres, los nodos de nivel 1 son "L" y "R", los nodos de nivel 2 son "LL", "LR", "RL" y "RR", etc.

Conclusiones:

• Una cadena válida para un nodo en el nivel A en U (n) tiene una longitud de A y satisface la desigualdad: n - count ("L") - 2 * count ("R")> = 1

• cuenta ("L") + cuenta ("R") = A o cuenta ("L") = A - cuenta ("R")

• Así, contar ("R") <= n - A - 1

• Podemos usar las siguientes funciones para generar todas las rutas válidas en un nivel determinado y para determinar el valor clave en cada nodo.

  void GeneratePaths(int height, int level)
  {
  int rLimit = height - level - 1;
  GeneratePaths(height, rLimit, level, string.Empty, 0);
  }
  void GeneratePaths(int height, int rLimit, int level, string prefix, int prefixlen)
  {
  if (prefixlen + 1 < level)
  {
  GeneratePaths(height, rLimit, level, prefix + "L", prefixlen + 1);
  if (rLimit > 0)
  GeneratePaths(height, rLimit - 1, level, prefix + "R", prefixlen + 1);
  }
  else if (prefixlen + 1 == level)
  {
  InsertNode(prefix + "L", height)
  if (rLimit > 0)
  InsertNode(prefix + "R", height);
  }
  }
  void InsertNode(string path, int height)
  {
  int key = fibonacci(height);
  int index = height - 2;
  for (int i=0; i < path.length(), i++)
  {
  int difference = fibonacci(index);
  char c = path.charAt(i);
  if (c == ''L'')
  {
  key -= difference;
  index -= 1;
  }
  else if (c == ''R'')
  {
  key += difference;
  index -= 2;
  }
  }
  InsertKey(key);
  }

Si utiliza estas funciones para generar un árbol U (5), obtendrá este resultado. (Tenga en cuenta que las teclas en el borde izquierdo del árbol siguen la secuencia de fibonacci del 1 al 5)

 5
3 7
2 4 6 8
1 3 4 6
1

Answer 3

Solucion basica

Los árboles de Fibonacci tienen varias propiedades que se pueden usar para formar un árbol de Fibonacci compacto:

1. Cada nodo en un árbol de Fibonacci es en sí mismo un árbol de Fibonacci.
2. El número de nodos en un árbol de Fibonacci de altura n es igual a F _{n + 2} - 1.
3. El número de nodos entre un nodo y su hijo izquierdo es igual al número de nodos en el hijo derecho del niño izquierdo del nodo.
4. El número de nodos entre un nodo y su hijo derecho es igual al número de nodos en el hijo izquierdo derecho del nodo.

Sin pérdida de generalidad, asumiremos que nuestro árbol de Fibonacci tiene la siguiente propiedad adicional:

1. Si un nodo tiene la altura n, entonces el niño izquierdo tiene la altura n-2, y el niño derecho tiene la altura n-1.

Combinando estas propiedades, encontramos que el número de nodos entre un nodo de altura n y sus hijos izquierdo y derecho es igual a F _n-1 - 1, y podemos usar este hecho para generar un árbol de Fibonacci compacto:

static int fibs[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170};
void fibonacci_subtree(int root, int height, int *fib)
{
if (height == 1) {
insert_into_tree(root);
} else if (height == 2) {
insert_into_tree(root + *fib);
} else if (height >= 3) {
fibonacci_subtree(root - *fib, height - 2, fib - 2);
fibonacci_subtree(root + *fib, height - 1, fib - 1);
}
}
...
for (height = 1; height <= max_height; height++) {
fibonacci_subtree(0, height, fibs + max_height - 1);
}

Este algoritmo genera el número mínimo de nodos posibles para una altura dada, y también produce el rango mínimo posible. Puede cambiar el rango haciendo que el nodo raíz sea distinto de cero.

Algoritmo de llenado compacto

La solución básica solo produce árboles de Fibonacci, que siempre tienen nodos F _{n + 2} - 1. ¿Qué sucede si desea generar un árbol desequilibrado con un número diferente de nodos a la vez que minimiza el rango?

En ese caso, necesita generar el siguiente árbol de Fibonacci más grande con algunas modificaciones:

• Algún número de elementos al final de la secuencia no se insertará.
• Esos elementos crearán brechas, y la ubicación de esas brechas debe ser rastreada.
• La diferencia entre nodos debe reducirse adecuadamente.

Aquí hay un enfoque que aún aprovecha la naturaleza recursiva de la solución:

void fibonacci_subtree(int root, int height, int *fib, int num_gaps, bool prune_gaps)
{
if(height < 1)
return;
if(prune_gaps && height <= 2) {
if(!num_gaps) {
if(height == 1) {
insert_into_tree(root);
} else if(height == 2) {
insert_into_tree(root + *fib);
}
}
return;
}
if(height == 1) {
insert_into_tree(root);
} else {
int max_rr_gaps = *(fib - 1);
int rr_gaps = num_gaps > max_rr_gaps ? max_rr_gaps : num_gaps;
num_gaps -= rr_gaps;
int max_rl_gaps = *(fib - 2);
int rl_gaps = num_gaps > max_rl_gaps ? max_rl_gaps : num_gaps;
num_gaps -= rl_gaps;
int lr_gaps = num_gaps > max_rl_gaps ? max_rl_gaps : num_gaps;
num_gaps -= lr_gaps;
int ll_gaps = num_gaps;
fibonacci_subtree(root - *fib + lr_gaps, height - 2, fib - 2, lr_gaps + ll_gaps, prune_gaps);
fibonacci_subtree(root + *fib - rl_gaps, height - 1, fib - 1, rr_gaps + rl_gaps, prune_gaps);
}
}

El bucle principal es un poco más complicado para acomodar un rango arbitrario de teclas:

void compact_fill(int min_key, int max_key)
{
int num_nodes = max_key - min_key + 1;
int *fib = fibs;
int max_height = 0;
while(num_nodes > *(fib + 2) - 1) {
max_height++;
fib++;
}
int num_gaps = *(fib + 2) - 1 - num_nodes;
int natural_max = *(fib + 1) - 1;
int max_r_gaps = *(fib - 1);
int r_gaps = num_gaps > max_r_gaps ? max_r_gaps : num_gaps;
natural_max -= r_gaps;
int root_offset = max_key - natural_max;
for (int height = 1; height <= max_height; height++) {
fibonacci_subtree(root_offset, height, fibs + max_height - 1, num_gaps, height == max_height);
}
}

Solución de forma cerrada

Si observa las diferencias entre cada par de palabras generadas por la solución básica, encontrará que alternan entre dos elementos secuenciales de la secuencia de Fibonacci. Este patrón alternativo se define por la palabra Fibonacci :

Una palabra de Fibonacci es una secuencia específica de dígitos binarios (o símbolos de cualquier alfabeto de dos letras). La palabra Fibonacci se forma por concatenación repetida de la misma manera que los números de Fibonacci se forman por suma repetida.

Resulta que hay una solución de forma cerrada para la palabra Fibonacci :

static double phi = (1.0 + sqrt(5.0)) / 2.0;
bool fibWord(int n)
{
return 2 + floor(n * phi) - floor((n + 1) * phi);
}

Puede usar esta solución de forma cerrada para resolver el problema usando dos bucles anidados:

// Used by the outer loop to calculate the first key of the inner loop
int outerNodeKey = 0;
int *outerFib = fibs + max_height - 1;
for(int height = 1; height <= max_height; height++) {
int innerNodeKey = outerNodeKey;
int *smallFib = fibs + max_height - height + 3; // Hat tip: @WalterTross
for(int n = fibs[height] - 1; n >= 0; n--) {
insert_into_tree(innerNodeKey);
// Use closed-form expression to pick between two elements of the Fibonacci sequence
bool smallSkip = 2 + floor(n * phi) - floor((n + 1) * phi);
innerNodeKey += smallSkip ? *smallFib : *(smallFib + 1);
}
if(height & 0x1) {
// When height is odd, add *outerFib.
outerNodeKey += *outerFib;
} else {
// Otherwise, backtrack and reduce the gap for next time.
outerNodeKey -= (*outerFib) << 1;
outerFib -= 2;
}
}