Árbol binario de búsqueda auto-balanceable

En ciencias de la computación, un árbol binario de búsqueda auto-balanceable o equilibrado es un árbol binario de búsqueda que intenta mantener su altura, o el número de niveles de nodos bajo la raíz, tan pequeños como sea posible en todo momento, automáticamente. Esto es importante, ya que muchas operaciones en un árbol de búsqueda binaria tardan un tiempo proporcional a la altura del árbol, y los árboles binarios de búsqueda ordinarios pueden tomar alturas muy grandes en situaciones normales, como cuando las claves son insertadas en orden. Mantener baja la altura se consigue habitualmente realizando transformaciones en el árbol, como la rotación de árboles, en momentos clave.

Las rotaciones internas en árboles binarios son operaciones internas comunes utilizadas para mantener el balance perfecto o casi perfecto del árbol binario. Un árbol balanceado permite operaciones en tiempo logarítmico

Tiempos para varias operaciones en términos del número de nodos en el árbol n:

Operación	Tiempo en cota superior asintótica
Búsqueda	O(log n)
Inserción	O(log n)
Eliminación	O(log n)
Iteración en orden	O(n)

Para algunas implementaciones estos tiempos son el peor caso, mientras que para otras están amortizados.

Estructuras de datos populares que implementan este tipo de árbol:

• Árbol AVL
• Árbol rojo-negro

Véase también

• Árbol-B

• Datos: Q245955
• Multimedia: Balanced trees / Q245955