1.1. Un árbol rojo-negro es un tipo abstracto de datos. Concretamente, es un árbol binario de búsqueda equilibrado, una estructura de datos utilizada en informática y ciencias de la computación.
1.2. Como en todos los árboles binarios de búsqueda, es posible moverse ordenadamente a través de los elementos de forma eficiente si hay forma de localizar el padre de cualquier nodo. El tiempo de desplazarse desde la raíz hasta una hoja a través de un árbol equilibrado que tiene la mínima altura posible es de O
1.3. Se dice que un nodo es rojo o negro haciendo referencia a dicho atributo.
1.4. Los árboles rojo-negro son isométricos a los árboles 2-3-4. En otras palabras, para cada árbol 2-3-4, existe un árbol correspondiente rojo-negro con los datos en el mismo orden.
2. Arbol Biselado
2.1. Es un Árbol binario de búsqueda auto-balanceable, con la propiedad adicional de que a los elementos accedidos recientemente se accederá más rápidamente en accesos posteriores.
2.2. Esta estructura de datos fue inventada por Robert Tarjan y Daniel Sleator y todas las operaciones normales de un árbol binario de búsqueda son combinadas con una operación básica, llamada biselación.
2.3. Volviendo a acceder al primer elemento se dispara una operación que toma del orden de O, operaciones para volver a balancear el árbol antes de devolver este primer elemento, esto es un retraso significativo para esa operación final, aunque el rendimiento se amortiza si tenemos en cuenta la secuencia completa, que es del orden de O
2.4. El buen rendimiento de un árbol biselado depende del hecho de que es auto-balanceado, y además se optimiza automáticamente.
3. Arboles tipo ABB
3.1. Un tipo particular de árbol binario que presenta una estructura de datos en forma de árbol
3.2. El interés de los árboles binarios de búsqueda (ABB) radica en que su recorrido en in orden proporciona los elementos ordenados de forma ascendente y en que la búsqueda de algún elemento suele ser muy eficiente.
3.3. Este algoritmo de ordenamiento no balancea al recorrer el metodo por ende no siempre queda eficiente el algoritmo
3.4. Todas las operaciones realizadas sobre árboles binarios de búsqueda están basadas en la comparación de los elementos o clave de los mismos, por lo que es necesaria una subrutina,
4. Arboles tipo avl
4.1. Un árbol AVL es un tipo especial de árbol binario ideado por los matemáticos rusos Adelson-Velskii y Landis. Fue el primer árbol de búsqueda binario auto-balanceable que se ideó.
4.2. Están siempre equilibrados de tal modo que para todos los nodos, la altura de la rama izquierda no difiere en más de una unidad de la altura de la rama derecha o viceversa. Gracias a esta forma de equilibrio (o balanceo),
4.3. Para conseguir la propiedad de equilibrio, la inserción y el borrado de los nodos se ha de realizar de una forma especial. Si al realizar una operación de inserción o borrado se rompe la condición de equilibrio, hay que realizar una serie de rotaciones de los nodos.
4.4. El reequilibrado se produce de abajo hacia arriba sobre los nodos en los que se produce el desequilibrio. Pueden darse dos casos: rotación simple o rotación doble; a su vez ambos casos pueden ser hacia la derecha o hacia la izquierda.
