Mantener un árbol binario equilibrado cuando los elementos se insertan en orden

Question

Me preguntaba si existe un algoritmo adecuado para mantener el equilibrio de un árbol binario, cuando se sabe que los elementos son siempre insertados en orden.

Una opción para esto sería usar el método estándar de crear un árbol equilibrado a partir de una matriz ordenada o lista vinculada, como se discutió en this pregunta, y también this otra pregunta. Sin embargo, me gustaría un método en el que se puedan insertar algunos elementos en el árbol, realizar búsquedas en él y agregar otros elementos más adelante, sin tener que descomponer el árbol en una lista y volver a crear todo.

Otra opción sería usar una de las muchas implementaciones de árbol de autoequilibrado, AVL, AA, rojo-negro, etc. etc. Sin embargo, todas estas cosas imponen algún tipo de sobrecarga en el proceso de inserción, y yo se preguntaba si podría haber una manera de evitar esto dada la restricción de que los elementos son siempre insertados en orden creciente.

Así que, para mayor claridad, me gustaría saber si existe un método por el cual pueda mantener un árbol binario equilibrado, de modo que pueda insertar un nuevo elemento arbitrario en cualquier punto y mantener el equilibrio del árbol, siempre que el nuevo elemento sea mayor en el orden del árbol que todos los elementos ya presentes en el árbol.

A modo de ejemplo, supongamos que hubiese el siguiente árbol:

 4 
    /\ 
    / \ 
    2  6 
/\ /\ 
    1 3 5 7 

¿Hay una manera sencilla de mantener el equilibrio cuando se inserta un nuevo elemento, si sé que el elemento será mayor que 7?

Answer 1

Si usted está realmente interesado en hacerlo usando un BST (que creo que no es la mejor opción, como se puede leer en mi otra respuesta), que podría hacerlo de esta manera:

Tener BST normales . Eso significa que las búsquedas son O (log N), si logramos mantener la profundidad durante las inserciones.

Al hacer una inserción (suponiendo que tengamos un elemento más grande que todos los anteriores), camina desde el elemento raíz hasta el elemento más a la derecha.Cuando se encuentra con un nodo cuyo subárbol es un árbol binario perfecto (todos los nodos internos tienen 2 hijos y todas las hojas tienen la misma profundidad), inserta el nuevo nodo como padre de este nodo.

Si llega al nodo más a la derecha en el árbol y no aplicó la regla anterior, eso significa que tiene un elemento secundario izquierdo, pero no tiene uno correcto. Entonces, el nuevo nodo se convierte en el hijo correcto del nodo actual.

Por ejemplo, en el primer árbol a continuación, el subárbol de 4 no es perfecto, pero el subárbol de 5 es (un árbol con un solo nodo es perfecto para la definición). Entonces, agregamos 6 como padre de 5, lo que significa que 4 es padre de 6 ahora y 5 es el hijo izquierdo de 6.

Si tratamos de agregar otro nodo entonces, el subárbol de 4 aún no es perfecto, y tampoco lo es el de 6. y la figura 6 es el derecho más nodos, así que agregamos 7 como el hijo derecho de 6.

 4    4    4 
    /\   /\   /\ 
/ \  / \  / \ 
    2  5 --> 2  6 --> 2  6 
/\   /\ / /\ /\ 
1 3   1 3 5  1 3 5 7 

Si utilizamos este algoritmo, el subárbol del hijo izquierdo de la raíz siempre será perfecto y el subárbol del niño correcto nunca tendrá una altura mayor que la del izquierdo. Por eso, la altura de todo el árbol siempre será O (log N), y también será el tiempo de búsqueda. La inserción también tomará el tiempo O (log N).

En comparación con las BST autoequilibrantes, las complejidades de tiempo son las mismas. Pero este algoritmo debería ser más fácil de implementar y podría ser más rápido que ellos.

Cuando se compara con la solución basada en arreglos de mi otra respuesta, la complejidad del tiempo de búsqueda es la misma, pero esta BST tiene un peor tiempo de inserción.

Answer 2

Supongo que sabes a priori que los elementos vienen en orden creciente. Además, supongo que quieres un árbol para buscar rápidamente un elemento específico.

No estoy seguro de si un árbol binario es más adecuado para la inserción rápida como usted lo describe. Pero puede haber otras estructuras de datos que se relacionen bien con el caso de uso que describes: aunque nunca lo he usado, me viene a la mente un skip-list. Como siempre inserta elementos superiores a todos los elementos que ya están en la colección, debería ser bastante fácil actualizar los punteros.

Answer 3

Para el requisito que describe, no necesita un árbol en absoluto. Un ordenado dynamic array es todo lo que necesita.

Al insertar, siempre inserte en el extremo (O (1) amortizado).

Al realizar una búsqueda, use binary search normal (O (log N)).

Esto supone que no necesita ninguna otra operación, o que no le importa que sean O (N).