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:
YouTube Encyclopedic
-
1/3Views:7 5895 76422 295
-
09-Árboles de búsqueda binarios-15-Borrado de un nodo con dos hijos
-
Arboles Binarios en Python
-
Graficar árbol binario en Java (Draw binary tree in Java)
Transcription
Véase también
| Control de autoridades |
|
|---|
Datos: Q245955
Multimedia: Balanced trees / Q245955
Esta página se editó por última vez el 22 oct 2019 a las 16:34.