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.
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:
No hay comentarios:
Publicar un comentario