Download Árboles - Departamento de Informática
Document related concepts
Transcript
Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 5: Árboles Prof. Montserrat Serrano Montero 1 ÍNDICE Primera parte: • Conceptos básicos • TAD Árbol binario • TAD Árbol de búsqueda 2 CONCEPTOS BÁSICOS • Árbol: Estructura no lineal que organiza sus elementos formando jerarquías. • • Nodo: Elemento del árbol. Árbol: Se define formalmente como una estructura finita formada por un nodo al cual están conectados ninguno, uno o más árboles disjuntos (no comparten elementos). Definición recursiva: lo definido se encuentra dentro de la definición. 3 CONCEPTOS BÁSICOS • • • • Bosque: Conjunto de dos o más árboles. Subárbol: Subconjunto de elementos de un árbol con estructura de árbol. Raíz: Nodo superior de un árbol. Al nodo raíz se le asocia el nivel 1. Nivel cero para el árbol vacío. Si existe una arista (rama) dirigida del nodo n al nodo m, entonces n es el padre o ascendiente directo de m y m es un hijo o descendiente directo de n. Los hijos del mismo padre son hermanos. • Un nodo que no tiene hijos se llama hoja del árbol. Nodo terminal. • Nodo interior o rama: Tiene descendientes. 4 CONCEPTOS BÁSICOS • • • Camino: Secuencia de nodos conectados dentro de un árbol. Nodo ascendiente y descendiente: n es antecesor de m si existe un camino de n a m y en este caso, m es descendiente de n. Longitud del camino: Número de nodos menos uno (r-1). (5-1) en el ej. 5 CONCEPTOS BÁSICOS • Nivel de un nodo: La longitud del camino desde el nodo raíz al nodo considerado, más uno. • Altura o profundidad de un árbol: El nivel más alto del árbol (o nivel máximo de los nodos de un árbol). Grado (aridad): Número de hijos de un nodo. El grado de un árbol se define como el máximo del grado de sus nodos. Árbol ternario: Árbol de grado 3. Un árbol unario sería un árbol de grado 1. A este árbol se le llama lista (árbol degenerado) El máximo número de nodos de un árbol de altura “h” y grado “g” sería: 6 1 + g + g2 + g3 +...+ gh-1 = ∑ gi ; 0 ≤ i ≤ (h -1) • • CONCEPTOS BÁSICOS • Representación de árboles: a) Grafo b) Jerarquía de márgenes c) Conjuntos incluidos d) Listas incluidas 7 TAD ÁRBOL BINARIO • Árbol binario: Árbol de grado 2. De cada nodo parten como máximo dos subárboles disjuntos (izquierdo y derecho). También puede estar vacío. ESPECIFICACIÓN INFORMAL: TAD ArbolB (VALORES: rango del problema; OPERACIONES: Inicia, EsVacio, Insertar, Suprimir, Izquierdo, Derecho, Raiz); Inicia ( ) → ArbolB Efecto: Crea un árbol binario vacío y lo deja en disposición de ser utilizado. EsVacio (ArbolB) → Boolean 8 Efecto: Devuelve true si el árbol binario es vacío y false en caso contrario. TAD ÁRBOL BINARIO Insertar (ArbolB, Elemento) → ArbolB Efecto: Introduce en el ArbolB un nuevo nodo cuyo valor está dado por el Elemento pasado. Excepción: Árbol lleno en implementa. estática. Suprimir (ArbolB, Elemento) → ArbolB Efecto: Borra del árbol binario el nodo cuyo valor coincide con el que se pasa en Elemento, si éste existe. Excepción: Error si el árbol binario está vacío. Izquierdo (ArbolB) → ArbolB Efecto: Devuelve el hijo izquierdo del árbol binario pasado como entrada. Excepción: Error si el árbol binario está vacío. Derecho (ArbolB) → ArbolB Efecto: Devuelve el hijo derecho del árbol binario pasado como entrada. Excepción: Error si el árbol binario está vacío. Raiz (ArbolB) → Elemento Efecto: Devuelve el Elemento contenido en el nodo raíz del árbol binario pasado como 9 entrada. Excepción: Error si el árbol binario está vacío. DECLARACIÓN DE TIPOS • Con arrays: const MaxNodos = ...; type indice = 0..MaxNodos; {máx nº de nodos} tInfo = ...; {depende del problema} tNodo = record info: tInfo; iz: indice; de: indice; end; tArbol = record raiz: indice; (1) libre: indice; (6) nodos: array [1..MaxNodos] of tNodo; end; 10 DECLARACIÓN DE TIPOS • Con punteros: (seguir con esta implementación) tInfo = ...; {depende del problema} tArbol = ^Nodo; Nodo = record info: tInfo; iz, de: tArbol end; 11 ALGORITMOS BÁSICOS procedure Inicia (var ArbolB: tArbol); begin ArbolB:= nil end; function EsVacio (ArbolB: tArbol): boolean; begin EsVacio:= (ArbolB = nil) end; function Izquierdo (ArbolB: tArbol): tArbol; begin if not EsVacio (ArbolB) then Izquierdo:= ArbolB^.iz else writeln (‘El árbol está vacío’) end; function Derecho (ArbolB: tArbol): tArbol; begin if not EsVacio (ArbolB) then Derecho:= ArbolB^.de else writeln (‘El árbol está vacío’) end; procedure Raiz (ArbolB: tArbol; var Elemento: tInfo); begin if not EsVacio (ArbolB) then Elemento:= ArbolB^.info else writeln (‘El árbol está vacío’) 12 end; ALGORITMOS DE RECORRIDO • Utilizados para visualizar o consultar datos almacenados en un árbol. • Métodos: a) En profundidad: Recorre el árbol por subárboles. 1. Enorden 2. Preorden 3. Postorden b) En amplitud: Recorre el árbol por niveles. • Los métodos en profundidad pueden implementarse de forma recursiva e iterativa. La forma iterativa requiere utilizar una pila. • El recorrido en amplitud se implementa de forma iterativa con ayuda de una cola como estructura de datos auxiliar. • Aplicación de estos algoritmos: acceso a 13 datos de almacenamiento en memoria secundaria. ALGORITMOS DE RECORRIDO • Recorrido recursivo enorden (IND): 1. Recorrer el subárbol izquierdo (I) 2. Visitar el nodo raíz (N) 3. Recorrer el subárbol derecho (D). Resultado: 4-2-5-1-6-3-7 1 2 4 3 5 6 7 procedure enorden (Arbol: tArbol); begin if Arbol <> nil then begin enorden (Arbol^.iz); write (Arbol^.info, ‘- ‘); enorden (Arbol^.de) end end; 14 ALGORITMOS DE RECORRIDO • Recorrido recursivo preorden (NID): 1. Visitar el nodo raíz (N) 2. Recorrer el subárbol izquierdo (I). 3. Recorrer el subárbol derecho (D). 1 Resultado: 1-2-4-5-3-6-7 3 2 5 4 6 7 procedure preorden (Arbol: tArbol); begin if Arbol <> nil then begin write (Arbol^.info, ‘- ‘); preorden (Arbol^.iz); preorden (Arbol^.de) end end; 15 ALGORITMOS DE RECORRIDO • Recorrido recursivo postorden (IDN): 1. Recorrer el subárbol izquierdo (I). 2. Recorrer el subárbol derecho (D). 3. Visitar el nodo raíz (N). 1 Resultado: 4-5-2-6-7-3-1 2 3 5 4 6 7 procedure postorden (Arbol: tArbol); begin if Arbol <> nil then begin postorden (Arbol^.iz); postorden (Arbol^.de); write (Arbol^.info, ‘ - ‘) end end; 16 ALGORITMOS DE RECORRIDO • Hay otras posibles combinaciones, considerando recorrido primero el subárbol derecho: 1. Enorden: DNI 7-3-6-1-5-2-4 2. Preorden: NDI 1-3-7-6-2-5-4 3. Postorden: DIN 7-6-3-5-4-2-1 Ejemplo. Deducir los tres recorridos en profundidad del árbol binario siguiente: • A C B D H E I F G J Enorden: H-D-I-B-J-E-A-F-C-G Preorden: A-B-D-H-I-E-J-C-F-G Postorden: H-I-D-J-E-B-F-G-C-A 17 ALGORITMOS DE RECORRIDO • Recorrido iterativo en amplitud: 1. Tomar el puntero a la raíz y ponerlo en la cola. 2. Quitar el primer elemento de la cola, mostrar el contenido del nodo y almacenar en la cola los punteros correspondientes a sus hijos izquierdo y derecho. 3. Repetir el paso 2. procedure amplitud (Arbol: tArbol); var A: tArbol; cola: tCola; begin Inicia (cola); A:= Arbol; if A<>nil then Encolar (cola, A); while not EsVacia (cola) do begin Desencolar (cola, A); write (A^.info, ‘ – ‘); if A^.iz <> nil then Encolar (cola, A^.iz); if A^.de <> nil then Encolar (cola, A^.de) end end; 18 ALGORITMOS DE RECORRIDO • Recorrido iterativo enorden (IND): Se utiliza una pila donde almacenar punteros a los distintos nodos del árbol. 3. Recupera 1. 2. Se recupera van colocando dede la la pila pila eny la escribe y pila se escribe punteros, 1. Como el 6.a1Como lano raíztiene tiene no yhijo loshijo sucesivos derecho, derecho, recupera hijos se pasa izquierdos dea la recuperar piladey cada escribe de la nodo. 4. pila Elyhijo a escribir derecho el de 8. El 4 es 8 tiene 6. Pone un en hijoladerecho, pila el que puntero se coloca a 6. en la pila. Después se coloca en la pila el hijo izquierdo de 12 que será el que se 19 recupere a continuación. ALGORITMOS DE RECORRIDO • Recorrido iterativo enorden (IND): procedure enorden (Arbol: tArbol); var A: tArbol; P: tPila; begin Inicia (P); A := Arbol; repeat while A <> nil do begin Apilar (P, A); A := A^.iz end; if not EsVacia (P) then begin Cima (P, A); Desapilar (P); write (A^.info, ‘ – ‘); A := A^.de end; until EsVacia (P) and EsVacio (A) end; 20 ÁRBOLES DE EXPRESIÓN • Los árboles binarios se utilizan para almacenar expresiones aritméticas en memoria, esencialmente en compiladores de lenguajes de programación. • Los paréntesis no se almacenan en el árbol pero están implicados en la forma del árbol. (A + B) * C A+B*C 21 ÁRBOLES DE EXPRESIÓN • Ejemplo 1: Deducir las expresiones que representan los siguientes árboles binarios. •Solución: Ejemplo 2: Dibujar la representación en árbol binario de /cada a) X * (Y - Z) una de las siguientes expresiones: b) A + [ (B * - (C + D)] a) / [ +(AY)] + B) c) X [A**Y( X * C* C ] b) (X * Y / A) + (B * C) 22 ÁRBOLES BINARIOS DE BÚSQUEDA • Árbol binario de búsqueda: Árbol binario ordenado. El valor en el nodo raíz es mayor que todos los del subárbol izquierdo y menor que todos los del subárbol derecho. • • Si recorremos el árbol enorden, está ordenado. Las operaciones básicas sobre este tipo de árboles binarios son: a) Búsqueda b) Inserción c) Borrado 23 d) Recorridos ESPECIFICACIÓN • TAD Árbol binario de búsqueda: Busqueda (ABB, Clave) → ABB Efecto: Devuelve el valor de una referencia al nodo que tiene la clave buscada y nil si la clave no está en el árbol. Insertar (ABB, Clave) → ABB Efecto: Introduce en el árbol como nodo hoja, la clave pasada como valor de entrada. Suprimir (ABB, Clave) → ABB Efecto: Borra del árbol binario el elemento pasado como entrada, si éste existe. Excepción: Error si el árbol binario está vacío. 24 IMPLEMENTACIÓN • Operación Búsqueda: function Busqueda (ABB: tArbol; Clave: tInfo): tArbol; begin if ABB = nil then Busqueda := nil else if ABB^.info = Clave then Busqueda := ABB else if ABB^.info > Clave then Busqueda := Busqueda (ABB^.iz, Clave) else Busqueda := Busqueda (ABB^.de, Clave) end; 25 IMPLEMENTACIÓN • Operación Insertar: • Pasos a seguir: 1. Asignar memoria para un nuevo nodo. 2. Buscar en el árbol para encontrar la posición de inserción del nuevo nodo, que se colocará como nodo hoja. 3. Enlazar el nuevo nodo al árbol. Ej: Tenemos que almacenar los números 8 3 1 20 1 10 5 4 • Para insertar 8, la única elección es insertar 8 en el nodo raíz: Como 3 < 8, 3 va en el subárbol izquierdo. 26 IMPLEMENTACIÓN • Operación Insertar: El 1 irá a la izquierda y debajo de 3: 20 debe ir a la derecha de 8 Los restantes elementos se sitúan de la misma forma: 27 IMPLEMENTACIÓN • Operación Insertar: procedure Insertar (var ABB: tArbol; Clave: tInfo); var N: tArbol; begin if ABB = nil then begin new (N); N^.info := Clave; Crea el nodo cuando se N^.iz := nil; llega a una posición hoja N^.de := nil; ABB := N; end else if ABB^.info > Clave then {Clave menor} Insertar (ABB^.iz, Clave) {Izquierda} else if ABB^.info < Clave then Insertar (ABB^.de, Clave) {Derecha} end; 28 IMPLEMENTACIÓN • Operación Suprimir: Compleja, ya que el nodo a suprimir puede ser cualquiera y la operación de supresión debe mantener la estructura del ABB. • Se pueden presentar 3 casos con tratamientos diferentes: 1. El nodo a borrar es un nodo hoja. - Se borra el nodo. 2. El nodo a borrar sólo tiene un descendiente. - Se puentea el nodo. 3. El nodo a borrar es normal, es decir, tiene los dos nodos hijos: (2 alternativas) a) Reemplazar la clave a eliminar por la mayor de las claves menores. b) Reemplazar la clave a eliminar por la menor de las claves mayores. • Implementamos con un ejemplo el caso 3, 29 alternativa a). IMPLEMENTACIÓN • Se quiere borrar la clave 20. Pasos a seguir: 1. Situarse en el nodo raíz del subárbol izquierdo del nodo a borrar. 2. Se desciende por la derecha hasta encontrar un nodo N sin descendiente derecho. 3. Se traslada la clave del nodo N al nodo a borrar. 30 4. Se borra el nodo N. IMPLEMENTACIÓN • • Árbol resultante, una vez borrada la clave 20. Es un árbol de búsqueda: 1, 5, 10, 12, 15, 17, 18, 22, 24, 30, 35 31 IMPLEMENTACIÓN • Operación Suprimir: procedure Suprimir (var ABB: tArbol; Clave: tInfo); var N: tArbol; procedure Borra2hijos (var ABB: tArbol); begin if ABB < > nil then if ABB^.info > Clave then {Clave menor} Suprimir (ABB^.iz, Clave) else if ABB^.info < Clave then {Clave mayor} Suprimir (ABB^.de, Clave) else {Clave encontrada} begin N := ABB;{Puntero aux al nodo a borrar} if ABB^.iz = nil then {Comprueba 2 ABB := ABB^.de descendientes} else if ABB^.de = nil then ABB := ABB^.iz else Borra2hijos (ABB^.iz); {Se toma el dispose (N) nodo izq a la clave end que se quiere borrar} 32 end; IMPLEMENTACIÓN • Operación Suprimir: procedure Borra2hijos (var ABB: tArbol); begin if ABB^.de < > nil then {Se desciende por la Borra2hijos (ABB^.de) derecha hasta nodo else hoja derecha} begin {Se cambia la información de la clave a borrar por la mayor de las claves menores} N^.info := ABB^.info; {Puntero auxiliar al nuevo nodo a borrar} N := ABB; {Se enlaza al árbol el posible nodo izquierdo del nuevo a borrar} ABB := ABB^.iz end 33 end; INTERÉS DE LOS ABB • El esfuerzo para localizar un elemento es menor que en una lista. • El nº de comparaciones, como máximo en un ABB, es el nº de niveles del árbol, que es más pequeño cuanto más completo sea el árbol. • Dada una estructura con n elementos: 1. En una lista habrá que hacer una media de n/2 comparaciones. 2. En un ABB habrá que hacer 2k-1 comparaciones siendo k la altura del árbol. n = 2k-1; 2k-1=2*log2(n+1)-1 34 Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 5: Árboles equilibrados Prof. Montserrat Serrano Montero 35 Nadie que no haya cometido nunca un error ha intentado nunca algo nuevo. Einstein ÍNDICE Segunda parte: • Conceptos básicos • Buscando el equilibrio. • Diseño e implementación de árboles AVL 36 INTERÉS DE LOS ÁRBOLES DE BÚSQUEDA • Optimizar el proceso de búsqueda. En el caso de un árbol binario ordenado habrá que hacer un máximo de k comparaciones para encontrar el elemento buscado, siendo k la altura del árbol. En el caso más favorable, el árbol binario está completo. Así, el número máximo de elementos que puede tener un árbol binario de altura h es: nmax = 1 + 2 + 4 + 8 + ...+ 2 k-1 = 2k –1 37 k = log2(nmax + 1) CONCEPTOS BÁSICOS • Si los elementos se añaden en el árbol según el algoritmo de inserción visto para los ABB, la estructura resultante del árbol dependerá del orden en que sean añadidos. • Si todos los elementos se insertan en orden creciente o decreciente, el árbol va a tener todas sus ramas izquierda o derecha, respectivamente, vacías. • La búsqueda en estos árboles será totalmente 38 secuencial. Comparaciones: O (n) CONCEPTOS BÁSICOS • La idea asociada a la eficiencia en la búsqueda de un elemento es la de árbol equilibrado. • Intuitivamente quiere decir que “una rama del árbol no sea mucho más larga que otra”, “que el número de niveles no sea demasiado grande para el número de nodos existentes”, “que no haya desproporción de elementos de una rama con respecto a otra”. 39 CONCEPTOS BÁSICOS • Un árbol binario lleno de altura h tiene todas sus hojas a nivel h y todos los nodos que están a nivel menor que h tiene cada uno dos hijos. • Un árbol binario completo de altura h es un árbol binario que está relleno a partir del nivel h-1, con el nivel h relleno de izquierda a derecha. • Un árbol binario lleno, es completo. 40 CONCEPTOS BÁSICOS • Un árbol perfectamente equilibrado es un árbol binario en el que para todo nodo, el número de nodos en el subárbol izquierdo y el número de nodos en el subárbol derecho difieren como mucho en una unidad. • Un árbol equilibrado en sentido AVL (Adelson-Velskii y Landis, 1962) es un árbol binario en el que la diferencia de alturas de los subárboles izquierdo y derecho correspondientes a cualquier nodo del árbol no es superior a uno. 41 CONCEPTOS BÁSICOS • Un árbol binario completo es un árbol equilibrado, mientras que un árbol binario lleno es totalmente equilibrado. En la figura: a) Árbol equilibrado AVL b) Árbol totalmente equilibrado c) y d) Árboles no equilibrados 42 CONCEPTOS BÁSICOS • Un árbol binario de búsqueda va perdiendo o ganando equilibrio al insertar o suprimir elementos. • Ejemplo: Árbol Árbol perfectamente binario de equilibrado, búsqueda tras equilibrado. trasinsertar insertar14. 10. Árbol totalmente equilibrado, Árbol lleno. 43 ÁRBOL BINARIO EQUILIBRADO (AVL) • La altura o profundidad de un árbol binario es el nivel máximo de sus hojas. La altura de un árbol nulo se considera cero. • El factor de equilibrio o balance de un nodo se define como la altura del subárbol derecho menos la altura del subárbol izquierdo correspondiente. • El factor de equilibrio de cada nodo en un 44 árbol equilibrado será 1, -1 ó 0. BUSCANDO EL EQUILIBRIO • Los algoritmos de inserción y borrado de los ABB no garantizan que la estructura resultante sea equilibrada en sentido AVL. • Es necesario definir otras operaciones auxiliares que se van a utilizar para garantizar que estas inserciones y supresiones sean equilibradas. • Estas operaciones o manipulaciones se denominan rotaciones de nodos. • Existen dos tipos de rotaciones de nodos: A) Simples: Izquierda y derecha. B) Dobles: Sucesiones de dos simples. 45 BUSCANDO EL EQUILIBRIO • ROTACIÓN SIMPLE IZQUIERDA: A1 < A < A2 < B < A3 • Ejemplo: 46 BUSCANDO EL EQUILIBRIO • ROTACIÓN SIMPLE DERECHA: A1 < A < A2 < B < A3 • Ejemplo: • Construir el ABB mediante la inserción de los elementos 1, 2, 3, 4, 5, 6 y 7 de forma que quede equilibrado AVL. 47 BUSCANDO EL EQUILIBRIO • ROTACIÓN DOBLE IZQUIERDA-DERECHA: • Ejemplo: 48 BUSCANDO EL EQUILIBRIO • ROTACIÓN DOBLE DERECHA-IZQUIERDA: • Ejemplo: . 49 Diseño e implementación de árboles AVL • • DECLARACIÓN DE TIPOS: Añadimos al tipo de datos que representa cada nodo un campo más: el factor de equilibrio (fe). type tInfo = ...; tArbolE = ^NodoAE; NodoAE = record Info: tInfo; Fe: -1..1; Iz, De: tArbolE end; 50 INSERCIÓN EN AVL • Se quiere insertar un nodo en un árbol equilibrado en sentido AVL de raíz R y subárboles izquierdo I y derecho D. • Supóngase que se inserta en I aumentando su altura. Esta inserción puede dar lugar a tres situaciones distintas: Caso A: • hI = hD Tras la inserción se conserva el equilibrio. No es necesario realizar ninguna operación para restaurar el equilibrio. 51 INSERCIÓN EN AVL Caso B: • hI < hD Tras la inserción, ambos subárboles tienen la misma altura. Se mejora la condición de equilibrio del árbol. Caso C: • hI > hD Tras la inserción, la diferencia de alturas entre los subárboles es mayor que la unidad. El árbol se desequilibra y hay que hacer rotaciones para que siga siendo AVL. Dos subcasos: 1. Inserción de un nodo menor que el raíz de 52 I. 2. Inserción de un nodo mayor que el raíz de I. INSERCIÓN EN AVL Caso C: Ejemplo 1. Se produce al insertar un nodo de clave 1 ó 3. Este índice es menor que el nodo raíz del subárbol izquierdo (4). La rotación a llevar a cabo para reequilibrar el árbol sería una rotación simple izquierda sobre el nodo raíz del árbol desequilibrado: el 8. 2. Se produce al insertar un nodo de clave 5 ó 7. Este índice es mayor que el nodo raíz del subárbol izquierdo (4). La rotación a llevar a cabo sería una rotación doble izquierda53 derecha sobre el nodo raíz del árbol desequilibrado. Diseño e implementación de árboles AVL • • INSERCIÓN: (tratamiento rotaciones) Inserción de las claves 68, 45, 29: • Movimiento de los punteros: Rotación I (1) n^.iz := n1^.de; (2) n1^.de := n; (3) n := n1 (1) nil 54 Diseño e implementación de árboles AVL • • INSERCIÓN: (tratamiento rotaciones) Inserción de las claves 75 y 90: • Movimiento de los punteros: Rotación D (1) n^.de := n1^.iz; (2) n1^.iz := n; (3) n := n1 (1) nil 55 Diseño e implementación de árboles AVL • • INSERCIÓN: (tratamiento rotaciones) Inserción de la clave 70: • Movimiento de los punteros: Rotación DI (1) n1^.iz := n2^.de; (2) n2^.de := n1; (3) n^.de := n2^.iz; (4) n2^.iz := n; (5) n := n2 (3) nil 56 Diseño e implementación de árboles AVL • • INSERCIÓN: (tratamiento rotaciones) Inserción de la clave 34: • Movimiento de los punteros: Rotación ID (1) n1^.de := n2^.iz; (2) n2^.iz := n1; (3) n^.iz := n2^.de; (4) n2^.de := n; (5) n := n2 (1) (3) nil nil 57 Diseño e implementación de árboles AVL • INSERCIÓN: function EsVacio (R: tArbolE): boolean; begin EsVacio:= (R = nil) end; function Crear (Clave: tInfo): tArbolE; var n: tArbolE; begin new (n); with n^ do begin info:= Clave; iz := nil; de := nil; fe := 0 {propio de un nodo hoja} end; Crear := n end; 58 Diseño e implementación de árboles AVL • INSERCIÓN: procedure rsi (var n: tArbolE; n1: tArbolE); begin Ajuste del factor de equilibrio (1) n^.iz := n1^.de; (2) n1^.de := n; if n1^.fe = -1 then begin{Si la rotación es por inserción se cumple} n^.fe := 0; n1^.fe := 0 end else begin {n1^.fe=0} n^.fe := -1; n1^.fe := 1 end; (3) n := n1; Los factores de equilibrio se end; incrementan en uno si se fue por la rama derecha, se decrementa en 1 59 si se fue por la rama izquierda. Diseño e implementación de árboles AVL • INSERCIÓN: procedure rdid (var n: tArbolE; n1: tArbolE); var n2: tArbolE begin n2 := n1^.de; (3) n^.iz := n2^.de; (4) n2^.de := n; (1) n1^.de := n2^.iz; (2) n2^.iz := n1; Ajuste del factor de equilibrio if (n2^.fe = 1) then n1^.fe := -1 else n1^.fe := 0; if (n2^.fe = -1) then n^.fe :=1 else n^.fe := 0; n2^.fe := 0; (5) n := n2; end; 60 Diseño e implementación de árboles AVL • INSERCIÓN: procedure rsd (var n: tArbolE; n1: tArbolE); begin (1) n^.de := n1^.iz; (2) n1^.iz := n; if n1^.fe = 1 then Ajuste del factor de equilibrio begin {Si la rotación es por inserción se cumple} n^.fe := 0; n1^.fe := 0 end else begin {n1^.fe=0} n^.fe := 1; n1^.fe := -1 end; (3) n := n1; end; 61 Diseño e implementación de árboles AVL • INSERCIÓN: procedure rddi (var n: tArbolE; n1: tArbolE); var n2: tArbolE begin n2 := n1^.iz; (3) n^.de := n2^.iz; (4) n2^.iz := n; (1) n1^.iz := n2^.de; (2) n2^.de := n1; if (n2^.fe = 1) then n^.fe := -1 else n^.fe := 0; if (n2^.fe = -1) then n1^.fe :=1 else n1^.fe := 0; n2^.fe := 0; (5) n := n2; end; 62 Diseño e implementación INSERCIÓN:de árboles AVL • procedure InsertarE (var r: tArbolE; var hh: boolean; Clave: tInfo); var n1: tArbolE; begin if EsVacio (r) then {se ha llegado a nodo hoja} begin r := Crear (Clave); hh := true {la altura del árbol ha crecido} end; else if (Clave < r^.info) then {Seguimos por la izquierda} begin InsertarE (r^.iz, hh, Clave); if hh then {decrementar en 1 Fe porque se insertó por case r^.fe of rama izquierda} 1: begin r^.fe := 0; hh := false end; 0: r^.fe := -1; -1: begin {Debe valer –2. Desequilibrio izquierda} n1 := r^.iz; if (n1^.fe = -1) then rsi (r, n1) {desequilibrio izq} else rdid (r, n1); {n1^.fe = 1} hh := false end 63 end; {case} end {if} • Diseño e implementación de árboles AVL INSERCIÓN: else if (Clave > r^.info) then {Seguimos por la derecha} begin InsertarE (r^.de, hh, clave); if hh then {incrementar en 1 Fe porque se insertó por case r^.fe of rama derecha} -1: begin {se reequilibra solo} r^.fe := 0; hh := false end; 0: r^.fe := 1; 1: begin {Debe valer 2. Desequilibrio derecha} n1 := r^.de; if (n1^.fe = 1) then rsd (r, n1) {desequilibrio dcha} else rddi (r, n1); hh := false end end; {case} end {if} else begin {Clave = r^.info} writeln (‘No está previsto insertar claves repetidas’); hh := false end 64 end; SUPRIMIR EN AVL • Sigue la estrategia del algoritmo de supresión en árboles binarios de búsqueda. • Al suprimir un nodo con cierta clave, el árbol resultante debe seguir siendo un árbol equilibrado. • Una vez eliminado un nodo siguiendo los criterios ABB, se regresa por el camino calculando los nuevos factores de equilibrio (Fe). • Si en alguno de los nodos se viola el criterio de equilibrio debe restaurarse el mismo, teniendo en cuenta que pueden producirse más de una rotación en el retroceso. • En los procedimientos el argumento boolean hh, será activado cuando la altura del árbol disminuya por eliminación de nodo o reestructuración del subárbol. 65 SURPIMIR EN AVL • Casos en la reestructuración: Caso A: Eliminar el nodo con clave 42 Rotación I, porque n^.fe := -2 y n1^.fe < = 0 66 SUPRIMIR EN AVL • Casos en la reestructuración: Caso B: Eliminar el nodo con clave 21 El Fe del nodo visitado disminuye en 1 si la eliminación se hizo por su rama derecha y se incrementa en 1 si la eliminación se hizo por su rama izquierda. Rotación DI, porque n^.fe := 2 y n1^.fe < 0 67 SUPRIMIR EN AVL • Casos en la reestructuración: Caso C: Eliminar el nodo con clave 25 Rotación D, porque n^.fe := 2 y n1^.fe >= 0 68 SUPRIMIR EN AVL • Casos en la reestructuración: Caso B: Reestructurar 65: Rotación DI, porque n^.fe := 2 y n1^.fe < 0 69 Diseño e implementación de árboles AVL • SUPRIMIR: procedure EquilibrarI (var n: tArbolE; var hh: var n1: tArbolE; boolean); begin case n^.fe of -1: n^.fe := 0; 0 : begin n^.fe := 1; hh := false end; 1: begin {Hay que restaurar el equilibrio} n1:= n^.de; if n1^.fe >=0 then begin if n1^.fe = 0 then hh := false; {no disminuye h} rsd (n, n1) end else rddi (n, n1) end; 70 end end; Diseño e implementación de árboles AVL • SUPRIMIR: procedure EquilibrarD (var n: tArbolE; var hh: var n1: tArbolE; boolean); begin case n^.fe of 1 : n^.fe := 0; 0 : begin n^.fe := -1; hh := false end; -1: begin {Hay que restaurar el equilibrio} n1:= n^.iz; if n1^.fe <=0 then begin if n1^.fe = 0 then hh := false; rsi (n, n1) end else rdid (n, n1) end; 71 end end; Diseño e implementación de árboles AVL • SUPRIMIR: procedure SuprimirE (var r: tArbolE; var hh: boolean; Clave: tInfo); var q: tArbolE; procedure bor (var d: tArbolE; var hh: boolean); begin if d^.de <> nil then begin bor (d^.de,hh); if hh then EquilibrarD (d, hh); end else begin q^.info := d^.info; q := d; d := d^.iz; hh := true end end; 72 Diseño e implementación de árboles AVL • SUPRIMIR: begin {Suprimir} if not EsVacio(r) then if Clave < r^.info then begin Suprimir (r^.iz, hh, Clave); if hh then EquilibrarI (r, hh) end else if Clave > r^.info then begin Suprimir (r^.de, hh, Clave); if hh then EquilibrarD (r, hh) end else begin {Ha sido encontrado el nodo} q := r; if q^.de = nil then begin r := q^.iz; hh:= true {Disminuye la altura} 73 end (Sigue) Diseño e implementación de árboles AVL • SUPRIMIR: else if q^.iz = nil then begin r := q^.de; hh := true end else begin bor ( q^.iz, hh); if hh then EquilibrarI (r, hh) end dispose (q); end {else encontrar nodo} end; 74 Ejemplos de supresión de nodos • Dado el siguiente árbol, realizar las supresiones de nodos siguientes de forma que en cada paso quede un árbol AVL: 5, 9, 8, 6, 3 75 Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 5: Árboles equilibrados Prof. Montserrat Serrano Montero 76 Nadie que no haya cometido nunca un error ha intentado nunca algo nuevo. Einstein ÍNDICE Segunda parte: • Conceptos básicos • Buscando el equilibrio. • Diseño e implementación de árboles AVL 77 INTERÉS DE LOS ÁRBOLES DE BÚSQUEDA • Optimizar el proceso de búsqueda. En el caso de un árbol binario ordenado habrá que hacer un máximo de k comparaciones para encontrar el elemento buscado, siendo k la altura del árbol. En el caso más favorable, el árbol binario está completo. Así, el número máximo de elementos que puede tener un árbol binario de altura h es: nmax = 1 + 2 + 4 + 8 + ...+ 2 k-1 = 2k –1 78 k = log2(nmax + 1) CONCEPTOS BÁSICOS • Si los elementos se añaden en el árbol según el algoritmo de inserción visto para los ABB, la estructura resultante del árbol dependerá del orden en que sean añadidos. • Si todos los elementos se insertan en orden creciente o decreciente, el árbol va a tener todas sus ramas izquierda o derecha, respectivamente, vacías. • La búsqueda en estos árboles será totalmente 79 secuencial. Comparaciones: O (n) CONCEPTOS BÁSICOS • La idea asociada a la eficiencia en la búsqueda de un elemento es la de árbol equilibrado. • Intuitivamente quiere decir que “una rama del árbol no sea mucho más larga que otra”, “que el número de niveles no sea demasiado grande para el número de nodos existentes”, “que no haya desproporción de elementos de una rama con respecto a otra”. 80 CONCEPTOS BÁSICOS • Un árbol binario lleno de altura h tiene todas sus hojas a nivel h y todos los nodos que están a nivel menor que h tiene cada uno dos hijos. • Un árbol binario completo de altura h es un árbol binario que está relleno a partir del nivel h-1, con el nivel h relleno de izquierda a derecha. • Un árbol binario lleno, es completo. 81 CONCEPTOS BÁSICOS • Un árbol perfectamente equilibrado es un árbol binario en el que para todo nodo, el número de nodos en el subárbol izquierdo y el número de nodos en el subárbol derecho difieren como mucho en una unidad. • Un árbol equilibrado en sentido AVL (Adelson-Velskii y Landis, 1962) es un árbol binario en el que la diferencia de alturas de los subárboles izquierdo y derecho correspondientes a cualquier nodo del árbol no es superior a uno. 82 CONCEPTOS BÁSICOS • Un árbol binario completo es un árbol equilibrado, mientras que un árbol binario lleno es totalmente equilibrado. En la figura: a) Árbol equilibrado AVL b) Árbol totalmente equilibrado c) y d) Árboles no equilibrados 83 CONCEPTOS BÁSICOS • Un árbol binario de búsqueda va perdiendo o ganando equilibrio al insertar o suprimir elementos. • Ejemplo: Árbol Árbol perfectamente binario de equilibrado, búsqueda tras equilibrado. trasinsertar insertar14. 10. Árbol totalmente equilibrado, Árbol lleno. 84 ÁRBOL BINARIO EQUILIBRADO (AVL) • La altura o profundidad de un árbol binario es el nivel máximo de sus hojas. La altura de un árbol nulo se considera cero. • El factor de equilibrio o balance de un nodo se define como la altura del subárbol derecho menos la altura del subárbol izquierdo correspondiente. • El factor de equilibrio de cada nodo en un 85 árbol equilibrado será 1, -1 ó 0. BUSCANDO EL EQUILIBRIO • Los algoritmos de inserción y borrado de los ABB no garantizan que la estructura resultante sea equilibrada en sentido AVL. • Es necesario definir otras operaciones auxiliares que se van a utilizar para garantizar que estas inserciones y supresiones sean equilibradas. • Estas operaciones o manipulaciones se denominan rotaciones de nodos. • Existen dos tipos de rotaciones de nodos: A) Simples: Izquierda y derecha. B) Dobles: Sucesiones de dos simples. 86 BUSCANDO EL EQUILIBRIO • ROTACIÓN SIMPLE IZQUIERDA: A1 < A < A2 < B < A3 • Ejemplo: 87 BUSCANDO EL EQUILIBRIO • ROTACIÓN SIMPLE DERECHA: A1 < A < A2 < B < A3 • Ejemplo: • Construir el ABB mediante la inserción de los elementos 1, 2, 3, 4, 5, 6 y 7 de forma que quede equilibrado AVL. 88 BUSCANDO EL EQUILIBRIO • ROTACIÓN DOBLE IZQUIERDA-DERECHA: • Ejemplo: 89 BUSCANDO EL EQUILIBRIO • ROTACIÓN DOBLE DERECHA-IZQUIERDA: • Ejemplo: . 90 Diseño e implementación de árboles AVL • • DECLARACIÓN DE TIPOS: Añadimos al tipo de datos que representa cada nodo un campo más: el factor de equilibrio (fe). type tInfo = ...; tArbolE = ^NodoAE; NodoAE = record Info: tInfo; Fe: -1..1; Iz, De: tArbolE end; 91 INSERCIÓN EN AVL • Se quiere insertar un nodo en un árbol equilibrado en sentido AVL de raíz R y subárboles izquierdo I y derecho D. • Supóngase que se inserta en I aumentando su altura. Esta inserción puede dar lugar a tres situaciones distintas: Caso A: • hI = hD Tras la inserción se conserva el equilibrio. No es necesario realizar ninguna operación para restaurar el equilibrio. 92 INSERCIÓN EN AVL Caso B: • hI < hD Tras la inserción, ambos subárboles tienen la misma altura. Se mejora la condición de equilibrio del árbol. Caso C: • hI > hD Tras la inserción, la diferencia de alturas entre los subárboles es mayor que la unidad. El árbol se desequilibra y hay que hacer rotaciones para que siga siendo AVL. Dos subcasos: 1. Inserción de un nodo menor que el raíz de 93 I. 2. Inserción de un nodo mayor que el raíz de I. INSERCIÓN EN AVL Caso C: Ejemplo 1. Se produce al insertar un nodo de clave 1 ó 3. Este índice es menor que el nodo raíz del subárbol izquierdo (4). La rotación a llevar a cabo para reequilibrar el árbol sería una rotación simple izquierda sobre el nodo raíz del árbol desequilibrado: el 8. 2. Se produce al insertar un nodo de clave 5 ó 7. Este índice es mayor que el nodo raíz del subárbol izquierdo (4). La rotación a llevar a cabo sería una rotación doble izquierda94 derecha sobre el nodo raíz del árbol desequilibrado. Diseño e implementación de árboles AVL • • INSERCIÓN: (tratamiento rotaciones) Inserción de las claves 68, 45, 29: • Movimiento de los punteros: Rotación I (1) n^.iz := n1^.de; (2) n1^.de := n; (3) n := n1 (1) nil 95 Diseño e implementación de árboles AVL • • INSERCIÓN: (tratamiento rotaciones) Inserción de las claves 75 y 90: • Movimiento de los punteros: Rotación D (1) n^.de := n1^.iz; (2) n1^.iz := n; (3) n := n1 (1) nil 96 Diseño e implementación de árboles AVL • • INSERCIÓN: (tratamiento rotaciones) Inserción de la clave 70: • Movimiento de los punteros: Rotación DI (1) n1^.iz := n2^.de; (2) n2^.de := n1; (3) n^.de := n2^.iz; (4) n2^.iz := n; (5) n := n2 (3) nil 97 Diseño e implementación de árboles AVL • • INSERCIÓN: (tratamiento rotaciones) Inserción de la clave 34: • Movimiento de los punteros: Rotación ID (1) n1^.de := n2^.iz; (2) n2^.iz := n1; (3) n^.iz := n2^.de; (4) n2^.de := n; (5) n := n2 (1) (3) nil nil 98 Diseño e implementación de árboles AVL • INSERCIÓN: function EsVacio (R: tArbolE): boolean; begin EsVacio:= (R = nil) end; function Crear (Clave: tInfo): tArbolE; var n: tArbolE; begin new (n); with n^ do begin info:= Clave; iz := nil; de := nil; fe := 0 {propio de un nodo hoja} end; Crear := n end; 99 Diseño e implementación de árboles AVL • INSERCIÓN: procedure rsi (var n: tArbolE; n1: tArbolE); begin Ajuste del factor de equilibrio (1) n^.iz := n1^.de; (2) n1^.de := n; if n1^.fe = -1 then begin{Si la rotación es por inserción se cumple} n^.fe := 0; n1^.fe := 0 end else begin {n1^.fe=0} n^.fe := -1; n1^.fe := 1 end; (3) n := n1; Los factores de equilibrio se end; incrementan en uno si se fue por la rama derecha, se decrementa en 1 100 si se fue por la rama izquierda. Diseño e implementación de árboles AVL • INSERCIÓN: procedure rdid (var n: tArbolE; n1: tArbolE); var n2: tArbolE begin n2 := n1^.de; (3) n^.iz := n2^.de; (4) n2^.de := n; (1) n1^.de := n2^.iz; (2) n2^.iz := n1; Ajuste del factor de equilibrio if (n2^.fe = 1) then n1^.fe := -1 else n1^.fe := 0; if (n2^.fe = -1) then n^.fe :=1 else n^.fe := 0; n2^.fe := 0; (5) n := n2; end; 101 Diseño e implementación de árboles AVL • INSERCIÓN: procedure rsd (var n: tArbolE; n1: tArbolE); begin (1) n^.de := n1^.iz; (2) n1^.iz := n; if n1^.fe = 1 then Ajuste del factor de equilibrio begin {Si la rotación es por inserción se cumple} n^.fe := 0; n1^.fe := 0 end else begin {n1^.fe=0} n^.fe := 1; n1^.fe := -1 end; (3) n := n1; end; 102 Diseño e implementación de árboles AVL • INSERCIÓN: procedure rddi (var n: tArbolE; n1: tArbolE); var n2: tArbolE begin n2 := n1^.iz; (3) n^.de := n2^.iz; (4) n2^.iz := n; (1) n1^.iz := n2^.de; (2) n2^.de := n1; if (n2^.fe = 1) then n^.fe := -1 else n^.fe := 0; if (n2^.fe = -1) then n1^.fe :=1 else n1^.fe := 0; n2^.fe := 0; (5) n := n2; end; 103 Diseño e implementación INSERCIÓN:de árboles AVL • procedure InsertarE (var r: tArbolE; var hh: boolean; Clave: tInfo); var n1: tArbolE; begin if EsVacio (r) then {se ha llegado a nodo hoja} begin r := Crear (Clave); hh := true {la altura del árbol ha crecido} end; else if (Clave < r^.info) then {Seguimos por la izquierda} begin InsertarE (r^.iz, hh, Clave); if hh then {decrementar en 1 Fe porque se insertó por case r^.fe of rama izquierda} 1: begin r^.fe := 0; hh := false end; 0: r^.fe := -1; -1: begin {Debe valer –2. Desequilibrio izquierda} n1 := r^.iz; if (n1^.fe = -1) then rsi (r, n1) {desequilibrio izq} else rdid (r, n1); {n1^.fe = 1} hh := false end 104 end; {case} end {if} • Diseño e implementación de árboles AVL INSERCIÓN: else if (Clave > r^.info) then {Seguimos por la derecha} begin InsertarE (r^.de, hh, clave); if hh then {incrementar en 1 Fe porque se insertó por case r^.fe of rama derecha} -1: begin {se reequilibra solo} r^.fe := 0; hh := false end; 0: r^.fe := 1; 1: begin {Debe valer 2. Desequilibrio derecha} n1 := r^.de; if (n1^.fe = 1) then rsd (r, n1) {desequilibrio dcha} else rddi (r, n1); hh := false end end; {case} end {if} else begin {Clave = r^.info} writeln (‘No está previsto insertar claves repetidas’); hh := false end 105 end; SUPRIMIR EN AVL • Sigue la estrategia del algoritmo de supresión en árboles binarios de búsqueda. • Al suprimir un nodo con cierta clave, el árbol resultante debe seguir siendo un árbol equilibrado. • Una vez eliminado un nodo siguiendo los criterios ABB, se regresa por el camino calculando los nuevos factores de equilibrio (Fe). • Si en alguno de los nodos se viola el criterio de equilibrio debe restaurarse el mismo, teniendo en cuenta que pueden producirse más de una rotación en el retroceso. • En los procedimientos el argumento boolean hh, será activado cuando la altura del árbol disminuya por eliminación de nodo o reestructuración del subárbol. 106 SURPIMIR EN AVL • Casos en la reestructuración: Caso A: Eliminar el nodo con clave 42 Rotación I, porque n^.fe := -2 y n1^.fe < = 0 107 SUPRIMIR EN AVL • Casos en la reestructuración: Caso B: Eliminar el nodo con clave 21 El Fe del nodo visitado disminuye en 1 si la eliminación se hizo por su rama derecha y se incrementa en 1 si la eliminación se hizo por su rama izquierda. Rotación DI, porque n^.fe := 2 y n1^.fe < 0 108 SUPRIMIR EN AVL • Casos en la reestructuración: Caso C: Eliminar el nodo con clave 25 Rotación D, porque n^.fe := 2 y n1^.fe >= 0 109 SUPRIMIR EN AVL • Casos en la reestructuración: Caso B: Reestructurar 65: Rotación DI, porque n^.fe := 2 y n1^.fe < 0 110 Diseño e implementación de árboles AVL • SUPRIMIR: procedure EquilibrarI (var n: tArbolE; var hh: var n1: tArbolE; boolean); begin case n^.fe of -1: n^.fe := 0; 0 : begin n^.fe := 1; hh := false end; 1: begin {Hay que restaurar el equilibrio} n1:= n^.de; if n1^.fe >=0 then begin if n1^.fe = 0 then hh := false; {no disminuye h} rsd (n, n1) end else rddi (n, n1) end; 111 end end; Diseño e implementación de árboles AVL • SUPRIMIR: procedure EquilibrarD (var n: tArbolE; var hh: var n1: tArbolE; boolean); begin case n^.fe of 1 : n^.fe := 0; 0 : begin n^.fe := -1; hh := false end; -1: begin {Hay que restaurar el equilibrio} n1:= n^.iz; if n1^.fe <=0 then begin if n1^.fe = 0 then hh := false; rsi (n, n1) end else rdid (n, n1) end; 112 end end; Diseño e implementación de árboles AVL • SUPRIMIR: procedure SuprimirE (var r: tArbolE; var hh: boolean; Clave: tInfo); var q: tArbolE; procedure bor (var d: tArbolE; var hh: boolean); begin if d^.de <> nil then begin bor (d^.de,hh); if hh then EquilibrarD (d, hh); end else begin q^.info := d^.info; q := d; d := d^.iz; hh := true end end; 113 Diseño e implementación de árboles AVL • SUPRIMIR: begin {Suprimir} if not EsVacio(r) then if Clave < r^.info then begin Suprimir (r^.iz, hh, Clave); if hh then EquilibrarI (r, hh) end else if Clave > r^.info then begin Suprimir (r^.de, hh, Clave); if hh then EquilibrarD (r, hh) end else begin {Ha sido encontrado el nodo} q := r; if q^.de = nil then begin r := q^.iz; hh:= true {Disminuye la altura} 114 end (Sigue) Diseño e implementación de árboles AVL • SUPRIMIR: else if q^.iz = nil then begin r := q^.de; hh := true end else begin bor ( q^.iz, hh); if hh then EquilibrarI (r, hh) end dispose (q); end {else encontrar nodo} end; 115 Universidad de Valladolid Departamento de informática Campus de Segovia Estructura de datos Tema 5:Otros árboles 116 ÍNDICE Tercera parte: • Árboles generales • Bosques • Árboles enhebrados 117 ÁRBOLES GENERALES • Un árbol de otro grado se puede transformar a binario. • Pasos: a) Quedarse con el enlace al hijo situado más a la izquierda de cada nodo. b) El hermano derecho más próximo se sitúa como subárbol derecho del hermano izquierdo. 118 ÁRBOLES GENERALES 1. 2. 3. El nodo raíz es A 119 BOSQUES • Un bosque es un conjunto de dos o más árboles disjuntos. • Para poderse transformar a un árbol binario, los árboles disjuntos tienen que estar ordenados. • Pasos: a) Transformar cada árbol del bosque en binario según el criterio de transformación de árboles generales. b) Situar el nodo raíz de cada árbol como subárbol derecho del árbol más situado a su izquierda. 120 BOSQUES Bosque: Árbol binario: 121 BOSQUES • Recorrido preorden: a) Visitar la raíz del primer árbol. b) Recorrer los subárboles del primer árbol (en preorden). c) Recorrer los árboles restantes (en preorden). Equivale a recorrer en preorden el árbol binario correspondiente. Resultado: A-B-C-D-E-F-G-H-I 122 BOSQUES • Recorrido postorden: a) Recorrer los subárboles del primer árbol (en postorden). b) Visitar la raíz del primer árbol. c) Recorrer los árboles restantes (en postorden). Equivale a recorrer enorden el árbol binario. Resultado: B-C-D-A-F-E-H-I-G 123 ÁRBOLES ENHEBRADOS • Una forma de aprovechar los nodos a nil de un árbol binario consiste en utilizarlos como apuntadores a otros nodos del árbol. • A estos punteros se les llama hebras: a) El puntero derecho de un nodo hoja apunta al nodo sucesor del árbol en el recorrido enorden. b) El puntero izquierdo apunta al nodo predecesor. 124 ÁRBOLES ENHEBRADOS • Para distinguir los hijos de las hebras, modificamos la estructura del árbol binario. • Se introducen dos campos booleanos que indican si el puntero es un enlace a un hijo o a una hebra: type tipoInfo = ...; tArbolEn=^Nodo; Nodo = record info: tipoInfo; hiz, hde: boolean; iz, de: tArbolEn end; • Así si hiz ó hde valen true, esto hace que iz y de sean hebras. 125 ÁRBOLES ENHEBRADOS • Se incluye un nodo cabecera que no tiene información. Su estructura es: 126