aporte

ÁRBOL BINARIO DE BÚSQUEDA (ABB)

Árbol binario
la mayoría de los árboles binarios son de búsqueda
Un árbol binario no vacío, de raíz R, es un árbol binario de búsqueda si:
En caso de tener subárbolizquierdo, la raíz R debe ser mayor que el valor máximo almacenado en el subárbol izquierdo, y que el subárbol izquierdo sea un árbol binario de búsqueda.
En caso de tener subárbol derecho, la raíz Rdebe ser menor que el valor mínimo almacenado en el subárbol derecho, y que el subárbol derecho sea un árbol binario de búsqueda.


Un árbol binario de búsqueda de tamaño 9 y profundidad 3, con raíz8 y hojas 1, 4, 7 y 13
















Para una fácil comprensión queda resumido en que es un árbol binario que cumple que el subárbol izquierdo de cualquier nodo (si no está vacío) contiene valoresmenores que el que contiene dicho nodo, y el subárbol derecho (si no está vacío) contiene valores mayores.
Para estas definiciones se considera que hay una relación de orden establecida entre loselementos de los nodos. Que cierta relación esté definida, o no, depende de cada lenguaje de programación. De aquí se deduce que puede haber distintos árboles binarios de búsqueda para un mismo conjunto deelementos.
La altura h en el peor de los casos siempre el mismo tamaño que el número de elementos disponibles. Y en el mejor de los casos viene dada por la expresión , donde ceil indica redondeo porexceso.
El interés de los árboles binarios de búsqueda (ABB) radica en que su recorrido en inorden proporciona los elementos ordenados de forma ascendente y en que la búsqueda de algún elemento sueleser muy eficiente.
Dependiendo de las necesidades del usuario que trate con una estructura de este tipo, se podrá permitir la igualdad estricta en alguno, en ninguno o en ambos de los subárboles quependen de la raíz. Permitir el uso de la igualdad provoca la aparición de valores dobles y hace la búsqueda más compleja.
Recorrido de un Árbol Binario
Hay tres manera de recorrer un árbol : en...