Árbol binario de búsqueda
Decimos que A es un árbol binario de búsqueda (ABB) si y solo si se satisfacen las dos condiciones al mismo tiempo: Donde "
Cabe destacar que la búsqueda en este tipo de árboles es muy eficiente, representa una función logarítmica.
Ejemplo de versión iterativa en el lenguaje de programación C, suponiendo que estamos buscando una clave alojada en un nodo donde está el correspondiente "dato" que precisamos encontrar: Véase ahora la versión recursiva en ese mismo lenguaje: Otro ejemplo en Python: En Pascal: Una especificación en maude para la operación de búsqueda quedaría de la siguiente forma: La inserción es similar a la búsqueda y se puede dar una solución tanto iterativa como recursiva.
Si tenemos inicialmente como parámetro un árbol vacío se crea un nuevo nodo como único contenido el elemento a insertar.
Como en el caso de la búsqueda puede haber varias variantes a la hora de implementar la inserción en el TAD (Tipo Abstracto de Datos), y es la decisión a tomar cuando el elemento (o clave del elemento) a insertar ya se encuentra en el árbol, puede que este sea modificado o que sea ignorada la inserción.
Es obvio que esta operación modifica el ABB perdiendo la versión anterior del mismo.
A continuación se muestran las dos versiones del algoritmo en pseudolenguaje, iterativa y recursiva, respectivamente.
Existen varios casos a tener en consideración: El siguiente algoritmo en C realiza el borrado en un ABB.
El procedimiento reemplazar busca la mayor clave del subárbol izquierdo y la asigna al nodo a eliminar.
Su implementación en maude es la siguiente: Se puede hacer un recorrido de un árbol en profundidad o en anchura.
El coste de recorrer el ABB es O(n), ya que se necesitan visitar todos los vértices.
En el montículo, como en todos los árboles binarios de búsqueda, cada nodo padre tiene un valor mayor que sus hijos y además es completo, esto es cuando todos los niveles están llenos con excepción del último que puede no estarlo.
Esto significa que todos los posibles nodos existen en esos niveles, no hay ningún hueco.
Un requirimiento adicional para un árbol binario completo es que para el nivel "n", los nodos deben estar ocupados de izquierda a derecha, no pudiendo haber un hueco a la izquierda de un nodo ocupado.
Un árbol como tal podría ser comparado con los árboles Huffman que tratan de encontrar elementos que son accedidos frecuentemente cerca de la raíz para producir una densa información; de todas maneras, los árboles Huffman solo puede guardar elementos que contienen datos en las hojas y estos elementos no necesitan ser ordenados.
