Arbol
Arbol
Arbol
1 DE SEPTIEMBRE DE 2017
UNIVERSIDAD NACIONAL DE PIURA.
INGENIERIA INFORMATICA
OBJETIVOS:
1) Estructurar datos en orden.
2) Conocer la terminología de un árbol.
3) Conocer los diferentes tipos de árboles binarios.
4) Saber recorrer un árbol en sus tres formas diferente.
5) Utilizar un árbol binario en una expresión algebraica.
6) Construir arboles de búsqueda.
7) Saber los procedimientos de los árbol B.
Árbol:
1. Definición:
Un árbol es una estructura (posiblemente no lineal) de datos compuesta de nodos,
vértices y aristas que es acíclica. Un árbol que no tiene ningún nodo se llama
árbol vacío o nulo. Un árbol que no está vacío consta de un nodo raíz y potencialmente
muchos niveles de nodos adicionales que forman una jerarquía.
2. Terminología:
Nivel: El nivel de un nodo se define por 1 + (el número de conexiones entre el nodo y
la raíz).
Ejemplo:
Suponiendo que se tiene n = 10.000 elementos que van a ser los nodos de un árbol binario
completo. Determinar la profundidad del árbol.
En el árbol binario completo con n nodos, la profundidad del árbol es el valor entero de
log2 n + 1, que es a su vez la distancia del camino más largo desde la raíz a un nodo más
uno.
Profundidad = int (log2 10000) + 1 = int (13.28) + 1 = 14
3. TAD Árbol binario:
La estructura de árbol binario constituye un tipo abstracto de datos; las operaciones
básicas que
definen el TAD árbol binario son las siguientes:
Tipo de dato: Dato que se almacena en los nodos del árbol.
Operaciones
Crear Árbol: Inicia el árbol como vacío.
Construir: Crea un árbol con un elemento raíz y dos ramas, izquierda y derecha
que son a su vez árboles.
Es Vacío: Comprueba si el árbol no tiene nodos.
Raíz: Devuelve el nodo raíz.
Izquierdo: Obtiene la rama o subárbol izquierdo de un árbol dado.
Derecho: Obtiene la rama o subárbol derecho de un árbol dado.
Borrar: Elimina del árbol el nodo con un elemento determinado.
Pertenece Determina si un elemento se encuentra en el árbol.
4. ESTRUCTURA DE UN ARBOL BINARIO:
Un árbol binario se construye con nodos. Cada nodo debe contener el campo dato
(datos a almacenar) y dos campos de enlace (apuntador), uno al subárbol izquierdo
(izquierdo, izdo) y otro al subárbol derecho (derecho, dcho). El valor null indica un árbol o
un subárbol vacío.
La Figura muestra la representación enlazada de dos árboles binarios de raíz A. El primero
es un árbol degenerado a la izquierda; el segundo es un árbol binario completo de
profundidad 4.
5. Creación de un árbol binario:
A partir del nodo raíz de un árbol se puede acceder a los demás nodos del árbol, por ello
se mantiene la referencia a la raíz del árbol. Las ramas izquierda y derecha son, a su vez,
árboles binarios que tienen su raíz, y así recursivamente hasta llegar a las hojas del árbol.
La clase ArbolBinario tiene el campo raíz, un constructor que inicializa raíz y métodos para
implementar las operaciones:
1) package arbolBinario;
2) public class ArbolBinario
3) {
4) protected Nodo raiz;
5) public ArbolBinario()
6) {
7) raiz = null;
8) }
9) public ArbolBinario(Nodo raiz)
10) {
11) this.raiz = raiz;
12) }
13) public Nodo raizArbol()
14) {
15) return raiz;
16) }
17) // Comprueba el estatus del árbol
18) boolean esVacio()
19) {
20) return raiz == null;
21) }
22) // ...
El método nuevoArbol() crea un árbol de raíz un nodo con el campo dato, rama izquierda
y derecha pasadas en los argumentos.
1) public static Nodo nuevoArbol(
2) Nodo ramaIzqda, Object dato, Nodo ramaDrcha)
3) {
4) return new Nodo(ramaIzqda, dato, ramaDrcha);
5) }
Así, para crear el árbol binario de la Figura, se utiliza un esquema secuencial y con una
Pila que guarda, en cada paso, los subárboles:
1) import TipoPila.PilaVector;
2) ArbolBinario arbol;
3) Nodo a1, a2, a;
4) PilaVector pila = new PilaVector();
5) a1 = ArbolBinario.nuevoArbol(null,"Maria",null);
6) a2 = ArbolBinario.nuevoArbol(null,"Rodrigo",null);
7) a = ArbolBinario.nuevoArbol(a1,"Esperanza",a2);
8) pila.insertar(a);
9) a1 = ArbolBinario.nuevoArbol(null,"Anyora",null);
10) a2 = ArbolBinario.nuevoArbol(null,"Abel",null);
11) a = ArbolBinario.nuevoArbol(a1,"M Jesus",a2);
12) pila.insertar(a);
13) a2 = (Nodo) pila.quitar();
14) a1 = (Nodo) pila.quitar();
15) a = ArbolBinario.nuevoArbol(a1,"Esperanza",a2);
16) arbol = new ArbolBinario(a);
6.ÁRBOL DE EXPRESIÓN:
Una aplicación muy importante de los árboles binarios son los árboles de expresiones. Una
expresión es una secuencia de tokens (componentes de léxicos que siguen unas reglas
establecidas). Un token puede ser un operando o bien un operador.
1) push(s,NULL); //insertamos en una pila (stack) el valor NULL, para asegurarnos de que esté vacía
2) push(s,raíz); //insertamos el nodo raíz
3) MIENTRAS (s <> NULL) HACER
4) p = pop(s); //sacamos un elemento de la pila
5) tratar(p); //realizamos operaciones sobre el nodo p
6) SI (D(p) <> NULL) //preguntamos si p tiene árbol derecho
7) ENTONCES push(s,D(p));
8) FIN-SI
9) SI (I(p) <> NULL) //preguntamos si p tiene árbol izquierdo
10) ENTONCES push(s,I(p));
11) FIN-SI
12) FIN-MIENTRAS
Recorrido en postorden:
En este caso se trata primero el subárbol izquierdo, después el derecho y por último el
nodo actual. Otra forma para entender el recorrido con este método seria seguir el orden:
nodo izquierdo, nodo derecha, nodo raíz. En el árbol de la figura el recorrido en postorden
sería: 2, 5, 11, 6, 7, 4, 9, 5 y 2.
D-E-B-F-G-C-A.
Recorrido en inorden:
En este caso se trata primero el subárbol izquierdo, después el nodo actual y por último el
subárbol derecho. En un ABB este recorrido daría los valores de clave ordenados de
menor a mayor. Otra forma para entender el recorrido con este método seria seguir el
orden: nodo izquierdo, nodo raíz, nodo derecha. En el árbol de la figura el recorrido en
inorden sería: 2, 7, 5, 6, 11, 2, 5, 4, 9.
Esquema de implementación:
ARBOL B:
B-árbol es un árbol de búsqueda que puede estar vacío o aquel cuyos nodos pueden
tener varios hijos, existiendo una relación de orden entre ellos, tal como muestra el dibujo.
Un árbol-B de orden M (el máximo número de hijos que puede tener cada nodo) es un
árbol que satisface las siguientes propiedades:
La idea tras los árboles-B es que los nodos internos deben tener un número variable de
nodos hijo dentro de un rango predefinido. Cuando se inserta o se elimina un dato de la
estructura, la cantidad de nodos hijo varía dentro de un nodo. Para que siga
manteniéndose el número de nodos dentro del rango predefinido, los nodos internos se
juntan o se parten. Dado que se permite un rango variable de nodos hijo, los árboles-B no
necesitan rebalancearse tan frecuentemente como los árboles binarios de búsqueda
auto-balanceables. Pero, por otro lado, pueden desperdiciar memoria, porque los nodos
no permanecen totalmente ocupados. Los límites (uno superior y otro inferior) en el
número de nodos hijo son definidos para cada implementación en particular. Por ejemplo,
en un árbol-B 2-3 (A menudo simplemente llamado árbol 2-3 ), cada nodo sólo puede
tener 2 ó 3 nodos hijo.
Un árbol-B se mantiene balanceado porque requiere que todos los nodos hoja se
encuentren a la misma altura.
Los árboles B tienen ventajas sustanciales sobre otras implementaciones cuando el tiempo
de acceso a los nodos excede al tiempo de acceso entre nodos. Este caso se da
usualmente cuando los nodos se encuentran en dispositivos de almacenamiento
secundario como los discos rígidos. Al maximizar el número de nodos hijo de cada nodo
interno, la altura del árbol decrece, las operaciones para balancearlo se reducen, y
aumenta la eficiencia. Usualmente este valor se coloca de forma tal que cada nodo
ocupe un bloque de disco, o un tamaño análogo en el dispositivo. Mientras que los
árboles B 2-3 pueden ser útiles en la memoria principal, y además más fáciles de explicar,
si el tamaño de los nodos se ajustan para caber en un bloque de disco, el resultado
puede ser un árbol B 129-513.
ESTRUCTURA:
#define TAMANO 1000
1) struct stclave {
2) int valor;
3) long registro;
4) };
5) class bnodo {
6) public:
7) bnodo (int nClaves); // Constructor
8) ~bnodo (); // Destructor
9) private:
10) int clavesUsadas;
11) stclave *clave;
12) bnodo **puntero;
13) bnodo *padre;
14) friend class btree;
15) };
Búsqueda:
La búsqueda es similar a la de los árboles binarios. Se empieza en la raíz, y se recorre el
árbol hacia abajo, escogiendo el sub-nodo de acuerdo a la posición relativa del valor
buscado respecto a los valores de cada nodo. Típicamente se utiliza la búsqueda
binaria para determinar esta posición relativa.
Procedimiento
Inserción:
Las inserciones se hacen en los nodos hoja.