arboles balanceados
Post on 13-Jun-2015
3.330 Views
Preview:
DESCRIPTION
TRANSCRIPT
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
top related