Á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 untiempo 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 larotación de árboles, en momentos clave.
Tiempos para varias operaciones en términos del número de nodosen 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
INTRODUCCIÓN

En el presente trabajohablaremos sobre la elaboración de un informe realizado por los estudiantes de la UCENM en la clase de Programación IV. El tema trata sobre el Árbol binario de búsqueda auto-balanceable enfocándonos en su utilidad y sus tipos, para que sirve, como se realiza y al final daremos unos ejemplos.
Un árbol binario de búsqueda auto-balanceable o equilibrado es un árbol binario de búsqueda que intentamantener 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.




















OBJETIVOS























Á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 queintenta 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 soninsertadas en orden. Mantener baja la altura se consigue habitualmente realizando transformaciones en el árbol, como larotació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 algunasimplementaciones 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




Árboles binarios de búsqueda
Un árbol binario de búsqueda es aquel que es:
Una estructura vacía ó
Un elemento o clave de información (nodo) más un número finito -a lo sumo dos- de estructuras tipoárbol, disjuntos, llamados subárboles y además cumplen lo siguiente:
• Todas las claves del subárbol izquierdo al nodo son menores que la clave del nodo.
• Todas las claves del subárbol derecho al nodo son mayores que la clave del nodo.
• Ambos subárboles son árboles binarios de búsqueda.
Un ejemplo de árbol binario de búsqueda:


Figura 2
Al definir el tipo de datos que representa laclave de un nodo dentro de un árbol binario de búsqueda es necesario que en dicho tipo se pueda establecer una relación de orden. Por ejemplo, suponer que el tipo de datos de la clave es un puntero (da igual a lo que apunte). Si se codifica el árbol en Pascal no se puede establecer una relación de orden para las claves, puesto que Pascal no admite determinar si un puntero es mayor o menor que...