REPUBLICA BOLIVARIANA DE VENEZUELAUNIVERSIDAD FERMIN TORO

FACULTAD DE INGENIERIA

Cabudare, Enero 2013

Alumnos: Jonathan Bastidas C.I. 17.048.561

Cleiver Manzanilla C.I. 17.304.303

Arboles Balanceados

Es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él. Se dice que un nodo

a es padre de un nodo b si existe un enlace desde a hasta b

(en ese caso, también decimos que b es hijo de a). Sólo puede haber un único nodo sin padres, que llamaremos raíz.

Es un nodo que no tiene hijos.

Es una estructura de datos ampliamente usada que imita la forma de un árbol (un conjunto de nodos conectados).

Son los demás nodos que tienen padre y uno o varios hijos.

Es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario").

ÁRBOL BINARIO

Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato. En el caso contrario el hijo es llamado un nodo interno.

NODO EXTERNO E INTERNO

- Los árboles binarios de búsqueda. - Los montículos binarios.- Codificación de Huffman.

ÁRBOL

ÁRBOLES

NODO

HOJA

USOS COMUNES DE LOS ÁRBOLES BINARIOS

RAMA

Árbol binario perfecto: Es un árbol binario lleno en el que todas las hojas (vértices con cero hijos) están a la misma profundidad (distancia desde la raíz, también llamada altura).

- Enumerar todos los elementos.- Buscar un elemento.- Dado un nodo, listar los hijos (si los hay).- Borrar un elemento.- Eliminar un subárbol (algunas veces llamada podar).- Añadir un subárbol (algunas veces llamada injertar).- Encontrar la raíz de cualquier nodo.Usos comunes de los árboles:- Representación de datos jerárquicos.- Como ayuda para realizar búsquedas en conjuntos de datos.

Los árboles binarios pueden ser construidos a partir de lenguajes de programación de varias formas. En un lenguaje con registros y referencias, los árboles binarios son construidos típicamente con una estructura de nodos y punteros en la cual se almacenan datos, cada uno de estos nodos tiene una referencia o puntero a un nodo izquierdo y a un nodo derecho denominados hijos.

Es una estructura sobre la cual se pueden realizar eficientemente las operaciones de búsqueda, inserción y eliminación.

ÁRBOLES

OPERACIONES COMUNES EN ÁRBOLES

MÉTODOS PARA ALMACENAR ÁRBOLES BINARIOSÁRBOLES BINARIOS DE BUSQUEDA

Árbol binario: Es un árbol con raíz en el que cada nodo tiene como máximo dos hijos.

Árbol binario lleno: Es un árbol en el que cada nodo tiene cero o dos hijos.

TIPOS DE ÁRBOLES BINARIOS

EJEMPLO DE ÁRBOL BINARIO DE BÚSQUEDA

Observe que si en el árbol mostrado se sustituye el valor 140 del nodo por 160, 99 por 105 y 43 por 55; el árbol continúa siendo un árbol binario de búsqueda. Ahora bien, si en dicho árbol se remplaza el valor 87 del nodo por 125, entonces el árbol deja de ser un árbol binario de búsqueda puesto que viola el principio que dice que: “Todos los nodos del subárbol izquierdo del nodo T deben ser menores o iguales al nodo T” (en este caso 125 no es menor a 120).

También es posible observar que si se efectúa un recorrido inorden sobre un árbol de búsqueda se obtendrá una clasificación de los nodos en forma ascendente. El recorrido inorden del árbol de la figura anterior produce el siguiente resultado:22-43-56-65-87-93-99-120-130-135-140

120

87 140

99

43

130

135 93

22 65

56

120

87 140

99

43

130

135 93

22 65

56

INSERCIÓN EN UN ÁRBOL BINARIO DE BÚSQUEDA

La inserción es una operación que se puede realizar eficientemente en un árbol binario de búsqueda.

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

2.1 El sub árbol derecho es igual a vacío, o el subárbol izquierdo es igual a vació; en cuyo caso se procederá a insertar el elemento en el lugar que le corresponde.

2.2 La clave que quiere insertarse es igual a la raíz del árbol; en cuyo caso no se realiza la inserción.

Consiste en eliminar un nodo del árbol sin violar los principios que definen justamente un árbol binario de búsqueda.

PASOS QUE DEBEN REALIZARSE PARA INSERTAR UN ELEMENTO A UN ÁRBOL BINARIO DE BÚSQUEDA

ÁRBOL BINARIO

BORRADO EN UN ÁRBOL BINARIO DE BÚSQUEDA

3. Si el elemento a borrar tiene los dos descendientes, entonces se tiene que sustituir por el nodo que se encuentra más a la izquierda en el subárbol derecho o por el nodo que se encuentra más a la derecha en el subárbol izquierdo.

Los árboles balanceados también pueden usarse para una implantación eficiente de colas de prioridad.

1. Si el elemento a borrar es terminal u hoja, simplemente se suprime.

2. Si el elemento a borrar tiene un solo descendiente, entonces tiene que sustituirse por ese descendiente.

La búsqueda más eficiente se efectúa en un árbol binario balanceado. Desafortunadamente, la función Inserta no asegura que el árbol permanezca balanceado, el grado de balance depende del orden del orden en que son insertados los nodos en el árbol.

Un árbol binario balanceado es un árbol binario en el cual las alturas de los dos sub árboles de todo nodo difieren a lo sumo en 1.

El balance de un nodo en un árbol binario se define como la altura de su subárbol izquierdo menos la altura de su subárbol derecho.

PARA BORRAR UN ELEMENTO EN UN ARBOL SE DEBE DISTINGUIR LOS SIGUIENTES CASOS

ARBOLES BALANCEADOS