Árbol binario de búsqueda
| ||||
Árbol Binario de Búsqueda (ABB). Son árboles binarios en los que se cumple que para cada nodo, el valor de la clave de la raíz del subárbol izquierdo es menor que el valor de la clave del nodo y que el valor de la clave raíz del subárbol derecho es mayor que el valor de la clave del nodo. Las operaciones para un ABB son similares que las realizadas en un árbol binario general.
Buscar un elemento
Partiendo siempre del nodo raíz, el modo de buscar un elemento se define de forma recursiva.
- Si el árbol está vacío, se termina la búsqueda: el elemento no está en el árbol.
- Si el valor del nodo raíz es igual que el del elemento que se busca, se termina la búsqueda con éxito.
- Si el valor del nodo raíz es mayor que el elemento que se busca, se continua la búsqueda en el árbol izquierdo.
- Si el valor del nodo raíz es menor que el elemento que se busca, se continua la búsqueda en el árbol derecho.
Insertar un elemento
Para insertar un elemento se basa en el algoritmo de búsqueda. Si el elemento está en el árbol no se inserta. Si no lo está, se inserta a continuación del último nodo visitado.Se necesita un puntero auxiliar para conservar una referencia al padre del nodo raíz actual. El valor inicial para ese puntero es NULL.
Fuente
Estructuras Dinámicas de Datos - Salvador Pozo Coronado (en www.conclase.net)
