Nota: Esta lección se lee mejor con palomitas a la mano y el código completo de BTS

*Dale click a las palomitas para ir al Código*

…Bienvenidos a a segunda parte de Árboles, es de lo más útil que nos encontraremos pero ¿Qué demonios son?

«BTS: Binary Search Tree, osea que es un árbol binario de búsqueda (ósea que esta ordenado)…Si, eso es todo, así de simple un árbol binario ordenado.Punto»

Ejemplo de BTS

Digo que un árbol esta «ordenado» cuando tengo un nodo (lo llamamos nodoRaiz) tal que para cualquier nodo que elija se tienen que cumplirse que:

El hijo izquierdo de nodoRaiz (si es que hay) debe ser menor
El hijo derecho de nodoRaiz (si es que hay) debe de ser mayor.

Esta regla se debe de cumplir para TODOS los nodos del árbol.

Para verificarlo basta con que miremos de izquierda a derecha el árbol y veamos is los elementos van de menor a mayor:

BTS

¿Y que vamos a buscar?

De igual manera que con los arboles normales ls BTS guardan su información en nodos, pero más bien la forma de encontrarlos va a ser por comparación, sea de números, ID o por orden alfabético o un método se te ocurra.

Operaciones

Veamos las operaciones que podemos hacer con un BST:

Búsqueda

Ejemplo de Búsqueda

Se usa principalmente para dos operaciones derivadas:

Una función que se llama Existe que busca si existe un elemento.
Una función que se llama ObtenerElemento que regresa un objeto cuyo identificador sea igual al que pedimos.
Una función que se llama EliminarElemento que ..bueno, elimina un elemento (que primero hay que encontrar)

Algoritmo

¿Es el nodo donde estas ahora el que buscas?, si es así regresa el valor, sino:
¿Es menor? Ve a la rama izquierda
¿Es mayor? Ve a la rama derecha
¿Es una hoja? …No existe

Insertar Elemento

Aquí lo primero es preguntarnos si nuestro árbol va a permitir elementos duplicados, sino también (recomendable) hay que tener eso en cuenta.

Recuerda, siempre se inserta en las hojas.

Insertar

Algoritmo

Si esta vacío va a la raíz
Si donde estamos es igual al elemento a añadir hay que ver que onda con los duplicados
Si es menor que el elemento actual recursivamente inserta en la rama derecha
Si es mayor que el elemento actual recursivamente inserta en la rama izquierda
Si llegamos a una hoja, le haremos un hijo y pondremos el dato ahí

Eliminar Elementos

Ok, ok, no te alarmes, pero esta puede que sea la operación más difícil de todas (pero ni tanto)

Pero es que hay varias «formas»de hacerlo dependiendo del número de hijos que tengas, así que vamos con el algoritmo:

Algoritmo:

Como podemos dividir esto en 3 casos, hoy a explicarlo como 3 casos diferentes pero recuerda que todos están unidos:

Caso 1: Si eres un nodo hoja has que tu padre apunte a NULL y borralo, tan simple.

Caso 2: Si tienes un hijo entonces has que tu padre apunte a tu hijo y borralo, tan simple.

Caso 3: Si tienes 2 hijos (aquí esta lo feo) … Así que habrá que hacer dos caminos 3A y 3B desde aquí, pero antes explicaré que vamos a hacer:

..Espera, creo que me he perdido en esa última parte ¿Como que 3A y 3B?

Lo que pasa es que no hay «una forma correcta» de eliminar un nodo con dos hijos ya que a fuerzas hay que cambiar la estructura del árbol para que no perdamos información.

Así que ahora hay que pensar: ¿Qué vamos a poner en donde esta el nodo que vamos a eliminar? ¡Pues muy fácil!, mira este árbol binario, quizá con dibujos sea más fácil:

Aquí un BTS con sus elementos ordenados

Ahora, ¿recuerdas que podemos hacer barras verticales de manera que solo toquen a un nodo?..y eso hace que sea más obvio que esta ordenado:

Perdonen calidad de GIF

Bueno digamos que quiero eliminar el 23, ¿Qué hago?

Pues nuestro objetivo es eliminarlo pero haciendo cuanto menos desastre mejor, así que habrá que elegir en un valor que este muy próximo a 23, mira, aquí esta una lista de cuanto vale cada nodo de forma ordenada:

05,12,21,23,26,53…

Bueno, en realidad solo nos importan los valores próximos a 23:

05,12,21,23,26,53…

Bueno tenemos dos candidatos: O el 21 o el 26, ahora bien: ¿Cuál?

La respuesta es que no tengo ni idea, quizá dependiendo de como este tu árbol te convenga más usar uno u el otro, quizá te de lo mismo, quizá uno sea la raíz de un árbol enorme que no te conviene reajustar, la verdad es que depende, así que te dejo a que tu eligas como quieras (con una función tuya o al azar o siempre poniendo siempre el mismo-el de la derecha o el de la izquierda- o lo que tu quieras) .

…Pongamos otro ejemplo, ahora con la raíz, el 53, si quisiéramos eliminarlo tenemos dos opciones.

¡Es por eso que esto es tan difícil, porque no hay un camino «correcto» pero bueno, explicado este texto enorme continuamos…Ya elegimos uno pero ¿Ahora qué?

Camino 3A(Queremos que en donde estaba nuestro nodo este algo más grande):

Si quieres eso tendremos que buscar del nodo en el que estamos, de su subarbol derecho el que tenga el valor mínimo (o dicho de otra forma el que este más a la izquierda)
Una vez que lo encuentres lo colocas donde estaba el nodo que querías eliminar y ahora eliminas recursivamente el nodo que acabas de encontrar

Camino 3B(Queremos que en donde estaba nuestro nodo este algo más pequeño):

Si quieres eso tendremos que buscar del nodo en el que estamos, de su subarbol izquierdo el que tenga el valor máximo (o dicho de otra forma el que este más a la derecha)
Una vez que lo encuentres lo colocas donde estaba el nodo que querías eliminar y ahora eliminas recursivamente el nodo que acabas de encontrar