ÁRBOL BINARIO DE BUSQUEDA

ÁRBOL BINARIO
Es un árbol binario en el que cada hijo de un vértice se designa como hijo izquierdo o hijo derecho, ningún vértice tiene más de un hijo izquierdo y un hijo derecho y cada vértice esta etiquetado con una clave que es uno de los objetos. Además a los vértices se les asignan las claves de modo que la clave de un vértice es mayor que la de todos los vértices de su subárbol izquierdoy' menor que la de todos los vértices de su subárbol derecho. Un árbol binario es una estructura homogénea que es la concatenación de un elemento T, llamado raíz, con dos árboles binarios disjuntos, llamados subárbol.
Es decir:
-Existe un nodo denominado raíz.
-Cada nodo puede tener 0,1, o 2 subárboles, tanto como izquierda o derecha.

ÁRBOLES BINARIOS DE BÚSQUEDA (ABB)
El árbol binario debúsqueda es una estructura sobre la cual se pueden realizar operaciones de inserción, búsqueda y eliminación.
Formalmente un árbol binario se define de la siguiente forma: para todo nodo T del árbol debe cumplirse que todos los valores de los nadas del subárbol izquierdo de T deben ser menores o iguales al valor del nodo T, de manera similar, todos los valores del subárbol derecho deben sermayores al nodo T.
Ejemplo de un árbol binario de búsqueda:
















Este es un Árbol binario de búsqueda de tamaño 9, profundidad 3, con raíz 8 y posee hojas 1, 4, 7, 13.
OPERACIONES CON LOS ÁRBOLES BINARIOS DE BÚQUEDA

-BÚSQUEDA: Su localización se realiza recorriendo el árbol, y tomando el subárbol derecho o izquierdo dependiendo del valor a buscar (sea mayor o menor).-Inserción: Se realiza de la siguiente manera:

1. Debe compararse el valor a insertar con la raíz del árbol. Si el valor es mayor, debe avanzar hacia el subárbol derecho; si es menor, debe avanzarse hacia el subárbol izquierdo.
2. Repetir el paso anterior hasta que se cumpla alguna de las condiciones:

2.1. Que el subárbol derecho o izquierdo sea igual a vacío, en cuyo caso se procederá conla inserción en el lugar de correspondencia.

2.2. Si la clave que quiere insertarse es igual a la raíz del árbol, no se inserta ningún elemento.
Ejemplo: Inserte las siguientes claves en un ABB que se encuentre vacío.
Claves: 120, 87, 43, 65, 140,99, 130.























ÁRBOL PERFECTAMENTE BALANCEADO

Un árbol perfectamente balanceado es un árbol AB en elque, para todo nodo, la cantidad de nodos dé su subárbol izquierdo difiere como máximo en 1 de la cantidad de nodos del subárbol derecho.
Un árbol binario es perfectamente balanceado si, para cada nodo, el número de nodos de su subárbol izquierdo y derecho difieren como mucho en 1.
Algoritmo para determinar un árbol perfectamente balanceado
ENTRADA: n cantidad de nodos.
SALIDA: árbolperfectamente balanceado.
Inicio
Si(n>O) entonces
Tomar un nodo como raíz
Construir el subárbol izquierdo Ni=n/2
Construir el subárbol derecho Nd=N-Ni-1
Fin si
Fin
Donde Ni es el número de nodos del subárbol izquierdo; n la cantidad de nodos y por último Nd, la cantidad de nodos en el subárbol derecho.
Ejemplo: Construir el árbol perfectamente balanceado con las siguientes claves:
10, 21, 5, 6,8, 20.



ÁRBOL PARCIALMENTE ORDENADO
Un árbol, es un árbol binario completo, ya que todos los niveles están llenos (el nivel n-1 siempre está completo), menos el último, pues se llena de izquierda a derecha; además, HEAP tiene todas y cada una de sus ramas ordenadas.
Operaciones básicas
-INSERTAR: primeramente si está vacío, se crea el primer nodo, llamado raíz. Luego se inserta el elementoen el nivel más bajo tan a la izquierda como sea posible, se comenzará en un nuevo nivel si el nivel n-1 está lleno. Recordaremos que un árbol parcialmente ordenado se va creando de izquierda a derecha.
Ejemplo: Construya en HEAP con las claves: 12, 24, 16, 30, 45, 9, 29,45, 60.



-ELIMINAR: Para realizar el borrado de un nodo. Tiene que haber mucha precaución y no eliminar el nodo tan...