Árbol de búsqueda binario autoequilibrado
En informática , un árbol de búsqueda binaria autoequilibrado (BST) es cualquier árbol de búsqueda binaria basado en nodos que mantiene automáticamente su altura (número máximo de niveles por debajo de la raíz) pequeña frente a inserciones y eliminaciones arbitrarias de elementos. [1] Estas operaciones, cuando están diseñadas para un árbol de búsqueda binario autoequilibrado, contienen medidas de precaución contra el aumento ilimitado de la altura del árbol, por lo que estas estructuras de datos abstractas reciben el atributo "autoequilibrado".
Para los árboles binarios de altura equilibrada , la altura se define como logarítmica en el número de elementos. Este es el caso de muchos árboles de búsqueda binarios, como los árboles AVL y los árboles rojo-negro ; este último se denominó árbol B binario simétrico [2] y se le cambió el nombre; sin embargo, aún puede confundirse con el concepto genérico de árbol de búsqueda binario autoequilibrado debido a las iniciales.
Pero los árboles Splay y Treaps también se consideran autoequilibrantes, aunque no se garantiza que su altura sea logarítmica en el número de elementos.
Los árboles de búsqueda binarios autoequilibrados proporcionan implementaciones eficientes para listas ordenadas mutables y se pueden usar para otras estructuras de datos abstractas, como matrices asociativas , colas de prioridad y conjuntos .
La mayoría de las operaciones en un árbol de búsqueda binaria (BST) toman un tiempo directamente proporcional a la altura del árbol, por lo que es deseable mantener la altura pequeña. Un árbol binario con altura h puede contener como máximo 2 0 +2 1 +···+2 h = 2 h +1 −1 nodos. Se sigue que para cualquier árbol con n nodos y altura h :
En otras palabras, la altura mínima de un árbol binario con n nodos es log 2 ( n ), redondeado hacia abajo ; es decir, . [1]
