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.Mantener un árbol binario equilibrado cuando los elementos se insertan 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?
¿Es la tarea? pregunta teórica? Si es para uso real, habría usado una [skip list] (http://es.wikipedia.org/wiki/Skip_list) en lugar de una BST con estas condiciones, y la adición siempre es el último elemento. Si eso ayuda, aunque no es un árbol, házmelo saber y lo escribiré como respuesta. – amit
@amit, esa fue mi primera conjetura también. – phimuemue
@amit, no es una pregunta de tareas, principalmente por curiosidad/teórica. Como tal, aunque tienes razón de que otras estructuras de datos como las listas de omisiones (o incluso los árboles de los dedos) pueden ser adecuadas, me interesaba más una forma de hacerlo a un BST. – DarkOtter