Arboles II: El Ataque de los BST

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*palomitas


…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”

bst-2

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:

  1. El hijo izquierdo de nodoRaiz (si es que hay) debe ser menor
  2. 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

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

busqueda

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

  1. ¿Es el nodo donde estas ahora el que buscas?, si es así regresa el valor, sino:
  2. ¿Es menor? Ve a la rama izquierda
  3. ¿Es mayor? Ve a la rama derecha
  4. ¿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.gif

Insertar

Algoritmo

  1. Si esta vacío va a la raíz
  2. Si donde estamos es igual al elemento a añadir hay que ver que onda con los duplicados
  3. Si es menor que el elemento actual recursivamente inserta en la rama derecha
  4. Si es mayor que el elemento actual recursivamente inserta en la rama izquierda
  5. 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:

bst

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:

bts

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.

BSTs.png

¡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):

  1. 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)
  2. 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):

  1. 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)
  2. 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

 

 

 

 

 


AVL: La versión Pro

Un Árbol AVL es un BTS muy especial, en el que además que todas las cosas que ya conocemos le agregamos algo mas… Es que se auto balancea.

Decimos que un BTS es un AVL si que la diferencia entre la profundidad de dos nodos cuales quiera no puede ser mas de uno.

AVL

 

 


Rotaciones

 

Hay muchas versiones de las rotaciones, muchos nombre, así que haré mi mejor esfuerzo para mostrarles todas las versiones que hay de las mismas:

La Super Pro

Con estas rotaciones podemos sacar todas las que necesitamos:

SuperRotaciones.png

Las Rotaciones Pro

 

Ahora veamos las Comunes y como las podemos representar usando las que creamos arriba:

Right-Right Rotation (Rotación Derecha)

También la llaman simplemente Right Rotation y es literalmente igual a la que tenemos allá arriba, ¿Puedes verlo? (X y sus hijos son T1 arriba)

 

RightRotation.png

La Clásica Rotación Derecha

Left-Left Rotation (Rotación Izquierda)

También la llaman simplemente Left Rotation y es literalmente igual a la que tenemos allá arriba, ¿Puedes verlo? (Z y sus hijos son T3 arriba)

 

LeftRotation.png

La Clásica Rotación Izquierda

 

 

Right-Left Rotation (Rotación Derecha-Izquierda)

Logramos esto de manera completa así:

RightLeftRotation.png

La Compleja Derecha Izquierda

 

Pero también  lo podemos expresar como:

  1. Primero has una rotación a la Derecha en Hijo derecho de la Raíz
  2. Después has una rotación a la Izquierda en la Raíz

Veámoslo en acción:

 

RightLeftRotationPart1.png

Paso 1: Rotación Derecha en Z

RightLeftRotationPart2.png

Paso 2: Rotación Izquierda en X

Left-Right Rotation (Rotación Izquierda-Derecha)

Logramos esto de manera completa así:

LeftRightRotation.png

La Compleja Izquierda-Derecha

 

Pero también  lo podemos expresar como:

  1. Primero has una rotación a la Izquierda en Hijo Izquierdo de la mañana
  2. Después has una rotación a la Derecha en la Raíz

Veámoslo en acción:

LeftRightRotationPart1.png

Paso 1: Rotación Izquierda en X

LeftRightRotationPart2.png

Paso 2: Rotación Derecha en Z

 

 

 

 

btn1 btn
btn

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s