Arboles Binarios

CAPÍTULO 1 – TEMA 4 – Operaciones sobre un árbol binario.
Árbol binario de búsqueda
Consideraciones para construir el árbol:
* El primer elemento se utiliza para crear el ‘nodo raíz’.
* Los valores del árbol deben ser tales que pueda existir un orden.
* Los valores del sub-árbol izquierdo, de cualquier nodo, son menores o iguales al valor del nodo.
* Los valores del sub-árbolderecho, de cualquier nodo, son mayores al valor del nodo.
Pasos para construir el árbol binario de búsqueda:
1. Colocar el primer valor como raíz.
2. Comparar el siguiente valor con la raíz;
* si es menor, se coloca por el lado izquierdo;
* si es mayor, se coloca por el lado derecho.
3. Se comparan los siguientes valores con sus antecesores y se ubica por el ladocorrespondiente.
Práctica: Construir el árbol binario de búsqueda para D, F, E, B, A, C, G. Donde A < Z.

Inserción en un árbol binario de búsqueda
Pasos para insertar un valor en un árbol binario de búsqueda:
1. Comparar el valor a insertar con la raíz:
* si es menor, avanza hacia la izquierda;
* si es mayor, avanza hacia la derecha.
2. Repetir el paso hasta cumplir con las siguientescondiciones:
* (el sub-árbol derecho es igual o vacío) o (el sub-árbol izquierdo es igual o vacío) //en cuyo caso se inserta el nodo en la posición que le corresponde.
* Si el valor a insertar es igual a la raíz del árbol, entonces no se realiza la inserción.
Práctica: Construir el árbol binario de búsqueda para 120, 87, 43, 65, 140, 99, 130, 22, 56. Una vez construido el árbol supongamosque deseamos insertar 100 y 35.

Eliminación
Consiste en eliminar un nodo del árbol sin violar los principios que definen, justamente, al árbol binario de búsqueda.
Consideraciones:
1. Si el elemento a borrar es una hoja, simplemente se suprime.
2. Si el elemento a borrar tiene un solo descendiente, entonces se sustituirá por ese descendiente.
3. Si el elemento a borrar tiene dosdescendientes, entonces:
* se sustituye por el nodo que se encuentre más a la izquierda de sub-árbol derecho; o
* por el nodo que se encuentre más a la derecha del sub-árbol izquierdo.
<< Siempre y cuando permita mantener la ordenación. >>
Práctica: Eliminar los siguientes nodos: 22, 99, 87, 120, 135, 56.

CAPÍTULO 1 – TEMA 5 – Árboles en montón; Ordenación por montón.El árbol en montón se usa en un elegante algoritmo de ordenación llamado ordenación por montón.
Árbol de montón o montón máximo: Si cada nodo N de un árbol tiene la siguiente propiedad: El valor de N es mayor o igual al valor de cualquier hijo de N.
Árbol de montón mínimo: El valor de N es menor o igual al valor de cualquier hijo de N.
Construcción de un árbol de montón (sea máximo o mínimo):1. El primer elemento será la raíz.
2. Luego se compara cada valor a insertar con su antecesor directo hasta que se ubique en el lugar adecuado.
<< Es importante tener en cuenta que los valores se colocan construyendo un árbol completo y luego se comparan>>
Práctica: Construir el árbol de montón para 44, 30, 50, 22, 60, 55, 77, 55.

Realizaremos la representaciónsecuencial de un árbol de montón.

Llamaremos H al árbol completo de la figura 12.
Obsérvese que H es un árbol en montón (significa que el mayor elemento de H aparece en lo <<alto>> del montón).

Práctica: Realizar la representación secuencial de H.
Donde:
* ÁRBOL[K], siendo K=1, es la raíz del árbol H.
* Los hijos izquierdo: ÁRBOL[2*K]
* Los hijos derechos:ÁRBOL[2*K+1]
<<Los nodos de árbol H de un mismo nivel deben quedar uno tras otro en el arreglo>>

Inserción en un árbol de montón
Pasos:
1. Se añade el ÍTEM o valor a insertar al final del árbol, de manera que siga siendo un árbol completo, aunque no necesariamente un montón.
2. Se hace subir al ÍTEM hasta su lugar apropiado en el árbol, para que cumpla nuevamente con...