Árbol binario de búsqueda auto-balanceable
- Á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.
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:
Véase también
Wikimedia foundation.
2010.
Mira otros diccionarios:
Á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 … Enciclopedia Universal
Árbol biselado — Un Árbol biselado o Árbol Splay 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. Realiza operaciones básicas como… … Wikipedia Español
Árbol AA — En informática un árbol AA es un tipo de árbol binario de búsqueda auto balanceable utilizado para almacenar y recuperar información ordenada de manera eficiente. Los árboles AA reciben el nombre de su inventor, Arne Andersson. Los árboles AA son … Wikipedia Español
Á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ó. Contenido 1 Descripción 2 Definición formal 2.1 Definición de la … Wikipedia Español
Árbol AVL — es un término usado en computación para referirse a 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ó … Enciclopedia Universal
Árbol (informática) — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar … Wikipedia Español
Árbol rojo-negro — Un Árbol rojo negro es un tipo de Árbol de búsqueda binario auto balanceable, una estructura de datos usada en ciencias de la computación. Fue inventada en 1972 por Rudolf Bayer quien los llamó B Árboles binarios simétricos Un Árbol rojo negro es … Enciclopedia Universal
Conjunto (informática) — Este artículo o sección sobre informática necesita ser wikificado con un formato acorde a las convenciones de estilo. Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 20 de abril de 2011. También puedes… … Wikipedia Español
Yevgeni Landis — Yevgeni Mijáilovich Landis (6 de octubre, 1921 12 de diciembre, 1997) (ruso … Wikipedia Español
Yevgeniy Landis — Yevgeniy Mikhailovich Landis (6 de octubre, 1921 12 de diciembre, 1997) (ruso: Евгений Михайлович Ландис) fue un matemático soviético nacido en Kharkov, Ucrania. Es conocido en el mundo de la computación por idear junto a Georgii Adelson Velskii… … Enciclopedia Universal
