Árboles Binarios de Búsqueda

Árboles binarios de búsqueda

La principal característica es que la información se almacena en los nodos cuidando de mantener cierto orden.

Formalmente se define un árbol binario de búsqueda de la siguiente manera:
Para todo nodo T del árbol se debe cumplir que todos los valores almacenados en el subárbol izquierdo de T sean menores o iguales a la información guardada en el nodo T. De forma similar, todos los valores almacenados en el subárbol derecho de T deben ser mayores a iguales a la información guardada en el nodo T.

El árbol binario de búsqueda es una estructura de datos sobre la cual se puede realizar eficientemente las operaciones de búsqueda, insercion y eliminación. Comparando esta estructura con otras, se pueden observar ciertas ventajas.
Por ejemplo, en un arreglo es posible localizar datos eficientemente si estos se encuentran ordenados, pero las operaciones de insercion y eliminación resultan costosas, porque involucran movimiento de los elementos dentro del arreglo.
En las listas, por otra parte, dichas operaciones se pueden llevar a cabo con facilidad, pero la operación de búsqueda, en este caso es una operación que demanda recursos, pudiendo incluso requerir recorrer todos los elementos de ella para llegar a uno en particular.






ESPACIO PARA IMAGEN DE UN ÁRBOL





Búsqueda
La operación de búsqueda en un árbol binario de búsqueda es mucho mas eficiente que en un árbol binario general, ya que al comparar el valor buscado con la información  del nodo visitado, si no es igual, se debe continuar solo por alguno de los dos subárboles.

Inserción en un árbol binario de búsqueda es una operación que se puede realizar eficientemente en este tipo de estructura de datos. La estructura crece conforme se insertan elementos al árbol. Los pasos que se deben realizar para agregar un nuevo nodo de un árbol de búsqueda son las siguientes:

1.- Comparar la clave a insertar con la raíz del árbol. Si es mayor, se sigue con el subárbol derecho. Si es menor, se continua con el subárbol izquierdo.
2.- Repetir sucesivamente el paso 1 hasta que se cumpla algunas de las siguientes condiciones:
2.1 .- El subárbol derecho, o el subárbol izquierdo, es igual a vació, en cuyo caso procederá a insertar el elemento en el lugar que le corresponde.
2.2 La clave que se quiere insertar esta en el nodo analizado, por lo tanto no se lleva a cabo la insercion. Este caso es valido solo cuando la aplicación exige que no se repitan elementos.


ELIMINACIÓN EN UN ÁRBOL BINARIO DE BÚSQUEDA.
La operación de eliminación en un árbol binario de búsqueda es un poco mas complicada que la de inserción. Esta consiste en eliminar un nodo sin violar los principios que define un árbol binario de búsqueda. se deben distinguir los siguientes casos:
1.- Si el elemento es terminal u hoja, simplemente se suprime redefiniendo el puntero de su predecesor.
2.- Si el elemento a eliminar tiene un solo descendiente, entonces tiene que sustituirse por ese descendiente.
3.- Si el elemento a eliminar tiene los dos descendientes, entonces se tiene que sustituir por el nodo que se encuentra mas a la derecha en el subárbol izquierdo.
Cabe destacar que antes de eliminar un nodo, se debe localizar este en el árbol. Para esto se utiliza el algoritmo de búsqueda presentado anteriormente.