Asignatura: Estructura de Datos AvanzadaTema: rboles Diplomado en Informtica AplicadaCentro de Estudio de Ingeniera de Sistemas (CEIS)Instituto Superior Politcnico Jos Antonio Echeverra (CUJAE)

Tema 3: rboles ContenidoDefinicin de rbolrboles BinariosRecorridos en rboles binariosrboles de bsqueda:rboles lexicogrficosrboles hilvanadosImplementacin en un lenguaje de programacin

Tema 3: rboles Contenidorboles generalesTransformacin de rboles generales en binariosImplementacin en un lenguaje de programacin Colocacin secuencial de rboles

BibliografaData Structures / Algorithms in Java. Robert Lafore. Pginas: 280-370Thinking in Java. Pginas: 395-445.Aprenda Java como si estuviera en primero. Pginas: 135-139.Aprenda Java en 21 das. Pginas: 135-151. El C++. Lenguaje de Programacin. Bjarne Stroustrup. Pginas 143-180 :.

ObjetivosConozcan las estructuras de datos arbreas y las formas de trabajar con ellas en la solucin de problemas de mediana complejidad

IntroduccinEstructuras de datos estudiadas:

Listas lineales y sus variantes.

Las relaciones entre los nodos de informacin son lineales.Todos los nodos tienen un nico antecesor, excepto el primero que no tiene antecesor.

Todos los nodos tienen un nico sucesor, excepto el ltimo que no tiene sucesor.

IntroduccinQu estructura de datos se debe utilizar para representar estructuras jerrquicas o taxonmicas? Ejemplo:

Definicin de rbolUn rbol (tree) es un T.D.A. que consta de un conjunto finito T de nodos y una relacin R (paternidad) entre los nodos tal que: Hay un nodo, especialmente designado, llamado la raz del rbol T. Los nodos restantes, excluyendo la raz, son particionados en m (m 0) conjuntos disjuntos T1, T2, ..., Tm, cada uno de los cuales es, a su vez, un rbol, llamado subrbol de la raz del rbol T. A los nodos que no son races de otros subrboles se les denomina hojas del rbol T, o sea, no tienen sucesores o hijos.

Definicin de rbolSi n es un nodo y A1, A2, A3, A4, A5, , Ak son rboles con races n1, n2, n3, n4,, nk . Se puede construir un nuevo rbol haciendo que n se constituya en padre de los nodos n1, n2, n3, n4,, nk.

En dicho rbol, n es la raz y A1, A2, A3, A4, A5, , Ak son los subrboles de la raz.

Los nodos n1, n2, n3, n4,, nk reciben el nombre de hijos del nodo n.

AclaracionesSi el conjunto finito T de nodos del rbol es vaco, entonces se trata de un rbol vaco.

En esta estructura existe slo un nodo sin padre, que es la raz del rbol.

Todo nodo, a excepcin del nodo raz, tiene uno y slo un padre.

Los subrboles de un nodo son llamados hijos.

Ejemplos Padre de C: Padre de E: Padre de G Padre de A: Hijos de A: Hijos de C: Hijos de F: ABCNONOCBFG

AclaracionesPara todo nodo k, distinto de la raz, existe una nica secuencia de la forma:

k0, k1, k2, k3, ..., kn, donde k0=raz y kn=k

Con n >= 1, donde. ki es el sucesor de ki-1, para 1

EjemplosSecuencias de A a G de A a E de A a FC es sucesor de A yF es sucesor de C

Otras definicionesGrado de un nodo: cantidad de hijos de un nodo.

Grado de un rbol al mayor de los grados de todos sus nodos.

Nodo hoja a un nodo sin hijos o con grado = 0.

Nodo rama a un nodo que tiene hijos, o sea, a la raz de un subrbol.

EjemplosGrado de A: de E: de G: de J: Grado del rbol: Nodos hojas:Nodos ramas:23103D, H, I, J, F, KA, B, C, E, G

Otras definicionesNivel de un nodo al nivel de su padre ms uno. Por definicin, la raz del rbol tiene nivel 0. Esta definicin es recursiva.

EjemplosNivel de A: de E: de B: de I: de G:02132

Otras definicionesrbol completo de nivel n a un rbol en el que cada nodo de nivel n es una hoja y cada nodo de nivel menor que n tiene, al menos, un subrbol no vaco.

Ejemplosrbol completo de nivel 2Cada nodo del nivel n es una hojarbol no completo de nivel 2Un nodo del nivel n-1 es una hoja

Otras definicionesPadre de un nodo al nodo raz del subrbol ms pequeo que contiene a dicho nodo y en el cual l no es raz.

Hijo de un nodo al (los) nodo(s) raz(ces) de uno de sus subrboles.

Predecesor de un nodo al nodo que le antecede en un recorrido del rbol.

Hermano de un nodo a otro nodo hijo de su padre.

Ejemplos Padre de G: Hijos de C: Hermanos de I:CFEGJH

Otras definicionesrbol ordenado a todo rbol para el que se considera el orden relativo de los sucesores o subrboles de cualquier nodo. Es decir, en un rbol ordenado se habla de primero, segundo o ltimo hijo de un nodo en particular. El primer hijo de un nodo de un rbol ordenado es denominado el hijo mayor de ese nodo y el ltimo hijo es denominado el menor.

El rbol es ordenado si al intercambiar el orden relativo de los subrboles de un nodo, representa una situacin semnticamente diferente.

Ejemplos: rbol genealgico de Mara (sin los hermanos)El rbol es ordenado El primer subrbol corresponde al padre. El segundo subrbol a la madre.

Otras definicionesrbol orientado a un rbol para el cual no interesa el orden relativo de los sucesores o subrboles de cualquier nodo, ya que slo se tiene en cuenta la orientacin de los nodos.

Ejemplo: La estructura organizativa de una empresa, donde no es importante el orden de los subdirectores a la hora de representarlos en el rbol.

En la solucin de problemas informticos, los ms utilizados son los rboles ordenados.

Otras definicionesUna floresta es una coleccin de dos o ms rboles disjuntos.

Aclaraciones: Disjuntos significa que no hay nodos en comn entre dos rboles cualesquiera de la misma. De un rbol se obtiene una floresta al quitarle la raz, si tiene dos hijos o ms. De una floresta se obtiene un rbol al aadir un nodo que sea raz de todos los rboles que la conforman.

EjemplosBDEGCIHJFEs una florestaNO es una florestaAEs un rbol

Definicin de rbol BinarioUn rbol binario (en ingls binary tree) es un rbol ordenado de, a lo sumo, grado 2.

Aclaraciones: A lo sumo grado 2 significa que cada nodo tiene como mximo dos hijos, o sea, dos subrboles. Al ser ordenado el rbol, importa el orden de los subrboles, es decir, que ser necesario especificar de cada nodo cul es el hijo izquierdo y cul el hijo derecho.

EjemploEl rbol genealgico es un rbol binario. Cada nodo tiene dos hijos Es significativo el orden de los subrboles.

rbol Binario: CaractersticasCada nodo del rbol binario contiene: InformacinHijo DerechoHijo Izquierdo Una referencia a su informacin. Un apuntador a su hijo izquierdo. Un apuntador a su hijo derecho.

Recorridos de un rbol BinarioLos recorridos se clasifican de acuerdo al momento en que se visita la raz del rbol y los subrboles izquierdo y derecho.

Existen tres recorridos:

Recorrido en Preorden

Recorrido en orden simtrico o inorden

Recorrido en orden final o Postorden

Recorrido en Preorden

Visitar la raz.

Recorrer subrbol izquierdo en preorden.

Recorrer subrbol derecho en preorden.

Recorrido en PreordenADEFGCBDBEAFCGRecorrido:Raz. Subrbol izquierdo en preorden. Subrbol derecho en preorden.ABDECFG

Recorrido en Simtrico

Recorrer subrbol izquierdo en simtrico.

Visitar la raz.

Recorrer subrbol derecho en simtrico.

Recorrido en SimtricoADEFGCBDBEAFCGRecorridoSubrbol izquierdo en simtrico. Raz. Subrbol derecho en simtrico.DBEAFCG

Recorrido en Postorden

Recorrer subrbol izquierdo en orden final.

Recorrer subrbol derecho en orden final.

Visitar la raz.

Recorrido en SimtricoADEFGCBDBEAFCGRecorridoSubrbol izquierdo en orden final. Subrbol derecho en orden final.Raz.DEBFGCA

rbol Binario: Implementacin en C++class TBinTreeNode{protected: void* aInfo; TBinTreeNode* aLeft; TBinTreeNode* aRight; TBinTreeNode* Left() {return aLeft;} void Left(TBinTreeNode* pNode) {aLeft = pNode;} TBinTreeNode* Right() {return aRight;} void Right(TBinTreeNode* pNode) {aRight = pNode;}public: TBinTreeNode(void* pInfo) : aInfo(pInfo), aLeft(NULL), aRight(NULL) {} virtual int Degree(); void* Info() {return aInfo;} virtual bool IsLeaf() {return (!aLeft && !aRight);} // Degree() == 0};

rbol: Implementacin en C++class TBinTree {protected: TBinTreeNode* aRoot;public: TBinTree() {aRoot = NULL;} ~TBinTree(); virtual void* DeleteNode(TBinTreeNode*); bool DivideTree(TBinTreeNode*, TBinTree* &, TBinTree* &); bool Empty(){return !aRoot;} TBinTreeNode* GetFather(TBinTreeNode*); virtual TGLinkedList* GetLeaves(); virtual bool InsertNode(TBinTreeNode*, char, TBinTreeNode*); int NodeLevel(TBinTreeNode*); TBinTreeNode* Root() {return aRoot;} void Root(TBinTreeNode* pRoot) {aRoot = pRoot;} int TreeDegree(); int TreeLevel();};

rboles de BsquedaPermiten realizar operaciones (recorridos, bsqueda de un elemento, etc) de forma ms eficiente.

Hay dos momentos para la manipulacin de un rbol:La construccin del rbol.El recorrido del rbol para realizar las operaciones requeridas segn el problema a resolver.

Existen dos tipos especiales de rboles: rboles lexicogrficos. rboles hilvanados.

rboles LexicogrficosUn rbol lexicogrfico es un rbol binario que, recorrido en orden simtrico, permite obtener la informacin de los nodos en algn criterio de ordenamiento.

La tcnica de construccin de un rbol lexicogrfico consiste en un proceso recursivo que va colocando los nodos en el subrbol izquierdo o derecho del nodo raz, segn sea el criterio de ordenamiento deseado (ascendente o descendente).

rboles LexicogrficosSiguiendo un ordenamiento ascendente:

Se compara el nodo que se quiere insertar con la raz del rbol. Si es menor, se coloca en el subrbol izquierdo siguiendo el mismo proceso.

Si es mayor, se coloca en el subrbol derecho siguiendo el mismo proceso.

rboles Lexicogrficos: Ejemplorbol lexicogrfico con ordenamiento ascendente.24157Si se recorre en orden simtrico, se obtiene la informacin de sus nodos en orden ascendente: 1, 2, 4, 5, 7 con independencia del orden de la lista original.Lista: 2, 7, 1, 4, 5 Lista: 4, 7, 2, 1, 5 47215

ProblemasEl recorrido de rboles con programas recursivos resulta costoso ya que implica un gasto adicional de memoria y tiempo de ejecucin. Para rboles muy grandes se puede desbordar el stack del sistema relativamente pronto.Cul es la solucin?rboles hilvanados

rboles HilvanadosUn rbol hilvanado (o rbol entrelazado) es un rbol binario en el que cada hijo izquierdo de valor nulo es sustituido por un enlace o hilvn al nodo que le antecede en orden simtrico (excepto el primer nodo en orden simtrico) y cada hijo derecho de valor nulo es sustituido por un enlace o hilvn al nodo que le sigue en el recorrido en orden simtrico (excepto el ltimo nodo en orden simtrico).

rboles HilvanadosAhora, un recorrido en orden simtrico se puede implementar sin necesidad de recursin.

Sin embargo, se requiere que los nodos tengan en su estructura algn atributo que permita saber cundo un enlace es real y cundo se trata de un hilvn. En este caso es necesario un atributo para cada hijo.

rbol HilvanadoCada nodo del rbol hilvanado contiene: InformacinHijo DerechoHijo Izquierdo Una referencia a su informacin. Un apuntador a su hijo izquierdo. Un apuntador a su hijo derecho. Indicador Izquierdo (Verdadero o Falso). Indicador Derecho (Verdadero o Falso).5TTIndicador Derecho (T)Indicador Izquierdo (T)

rboles HilvanadosNULLNULLRecorrido Simtrico:1, 3, 4, 5, 6, 8, 9

Construyendo rboles Hilvanados1. Se coloca el nodo raz del rbol

Si el nodo a insertar es el hijo izquierdo del nodo N:

Se pone como hijo izquierdo del nodo a insertar a lo que era el hijo izquierdo del nodo N.

Se pone como hijo derecho del nodo a insertar al nodo N.

Se pone como hijo izquierdo del nodo N al nodo a insertar.

Construyendo rboles HilvanadosSi el nodo a insertar es el hijo derecho del nodo N:

Se pone como hijo derecho del nodo a insertar a lo que era el hijo derecho del nodo N.

Se pone como hijo izquierdo del nodo a insertar al nodo N.

Se pone como hijo derecho del nodo N al nodo a insertar.

Construyendo rboles HilvanadosNULLNULLNULLNULLNULLNULLFTNULLFT

rbol Hilvanado: Implementacin en C++class TThreadedTreeNode : public TBinTreeNode{private: bool aIsLeft; // Indicador Izquierdo bool aIsRight; // Indicador Derechopublic: TThreadedTreeNode(void* pInfo): TBinTreeNode(pInfo) { aIsLeft = false; aIsRight = false;}};

rboles BalanceadosLa bsqueda en un rbol lexicogrfico puede convertirse en una bsqueda secuencial. Esto sucede porque el rbol no est balanceado, es decir los nodos no estn distribuidos uniformemente y se han insertado todos los nodos en profundidad. Esto podra ser salvado si se utilizara un rbol balanceado que al insertar toma en cuenta la cantidad de niveles del rbol y distribuye los nodos uniformemente.

rboles BalanceadosLos rboles balanceados (B-Tree) son rboles en los que cada nodo tiene entradas del mismo tipo. Un rbol balanceado no es un rbol de bsqueda binario, pues cada nodo puede tener ms de dos hijos.

rboles AVLUn rbol AVL es un rbol binario de bsqueda en el que las alturas de los subrboles izquierdo y derecho de cualquier nodo se diferencian a lo sumo en uno.

La bsqueda es similar a como se hace en un rbol binario de bsqueda (lexicogrficos), pero la insercin y la eliminacin deben considerar la propiedad del balance.

rboles GeneralesLa estructura anterior se puede representar con un rbol binario?

rboles GeneralesSon rboles cuyo grado es mayor que dos.Cmo representarlos?

rboles GeneralesPor cada nodo: la informacin y una lista de referencias a cada uno de sus hijos. Secuencial: Se pierde espacio, cada nodo tiene un agrado diferente.

Enlazada: la manipulacin de la lista de hijos se hace difcil.1

rboles GeneralesTransformar el rbol general en binario Cada nodo tiene en su enlace izquierdo a su primer hijo en el general y a la derecha de un nodo van sus hermanos en el general.

Aclaraciones: El rbol se convierte en binario donde el enlace izquierdo representa al primer hijo (en el rbol general) y el enlace derecho al siguiente hermano (en el rbol general). El rbol es ordenado porque a la izquierda est su primer hijo (si lo tiene) y a la derecha estarn sus hermanos (si los tiene) con sus descendientes.2

Transformacin de General en BinarioABCDFEHGEl que no tiene hijo izquierdo es hoja en el general.El que no tiene hijo derecho es el ltimo hermano en el general.rbol General rbol Binario del General

Transformacin de General en Binariorbol Binario de la Floresta FlorestaN - cantidad de rboles de la floresta. Si N=0 entonces el rbol binario es vaco. Si N>0 - raz del binario es raz del 1er rbol. Hijo izquierdo sus descendientes. Hijo derecho, la raz del 2do rbol.ABCEGDHFKLJI

rbol General: Implementacin en C++class TGBinTreeNode: public TBinTreeNode{public: TGBinTreeNode(void* pInfo): TBinTreeNode(pInfo) {} bool IsLeaf() {return !aLeft;} int Degree();};

rbol General: Implementacin en C++int TGBinTreeNode::Degree(){ int degree = 0; TBinTreeNode* cursor = Left(); while (cursor) { degree++; cursor = cursor->Right(); } return degree;}

rbol General: Implementacin en C++class TGBinTree: public TBinTree{public: void* DeleteNode(TGBinTreeNode*); TGBinTreeNode* GetFather(TGBinTreeNode*); TGLinkedList* GetLeaves(); TGLinkedList* GetSons(TBinTreeNode*); bool InsertNode(TGBinTreeNode*, TGBinTreeNode*); };

Colocacin Secuencial de rbolesSe puede colocar secuencialmente un rbol?Cundo colocar secuencialmente un rbol?Cuando debe recorrerse en mltiples ocasiones y no sufre frecuentes inserciones y/o eliminaciones.

Ejemplo: una frmula que debe ser evaluada muchas veces.12Si

Colocacin Secuencial de rbolesLos mtodos ms conocidos son:

Almacenamiento en Preorden Secuencial. Almacenamiento en Orden Familiar. Almacenamiento en Postorden Secuencial.Cmo colocar secuencialmente un rbol?3

Colocacin en Preorden Secuencial Se transforma a binario Los nodos deben colocarse secuencialmente recorriendo al rbol en preorden.3. Por cada nodo se registra tres campos:

INFO rbol binario recorrido en Preorden ENLDER Siguiente hermano en el rbol general, hijo derecho en el binario. Convencin: -1 si no existeTERM Indica si el nodo es terminal (no tienen hijo en el general) y no tiene hijo izquierdo (en el binario).

Colocacin en Preorden SecuencialABFDECIJHGA-1FB 4FE 3TF-1TC 6FG-1TD-1FH 8T I 9TJ-1T

ENLDERINFOTERM

Colocacin en Preorden SecuencialAclaraciones: Los hermanos se obtienen a travs del enlace derecho.

Si un nodo no es terminal la siguiente posicin de la lista secuencial est ocupada por su hijo. De lo contrario, es familia de otro nodo (hermano o hijo).

Los subrboles estn juntos, primero el padre y luego los hijos.

Implementacin en C++typedef int TIndex;class TPreOrderNode{private: void* aInfo; TIndex aRightLink; bool aEnd;public: TPreOrderNode(void* pInfo, bool pEnd) : aInfo(pInfo), aRightLink (-1), aEnd(pEnd){} void* Info() {return aInfo;} TIndex RightLink () {return aRightLink;} void RightLink(TIndex pRightLink) {aRightLink = pRightLink;} bool End() {return aEnd;}};

Colocacin en Orden Familiar Se transforma a binario Los nodos deben colocarse secuencialmente recorriendo al rbol en postorden invertido.3. Por cada nodo se registra tres campos:

INFO rbol binario recorrido en Postorden invertido ENLIZQ primer hijo en el rbol general e hijo izquierdo en el binario. Convencin: -1 si no existeTERM Indica ltimo hermano en el rbol general y enlace derecho en NULL en el binario. Indica el nodo final de cada familia

Colocacin en Orden FamiliarABFDECIJHGA 1TB 8FC 7FD 4TH-1F I-1FJ-1TG-1T E-1FF-1T

ENLIZQINFOFAM

Colocacin en Orden FamiliarAclaraciones: El nodo raz (si no es una floresta) y los nodos que no tienen un siguiente hermano se tienen FAM en T (True). El que sigue a un nodo es su hermano si FAM es F (False). Los hermanos estn juntos secuencialmente. El enlace izquierdo indica el subndice del primer hijo y los otros a continuacin son los hermanos hasta que FAM tome valor True.

Implementacin en C++class TFamilyNode {private: void* aInfo; TIndex aLeftLink; bool aFamily;public: TFamilyNode(void* pInfo, bool pFamily) : aInfo(pInfo), aLeftLink(-1), aFamily(pFamily){} void* Info() {return aInfo;} TIndex LeftLink () {return aLeftLink;} void LeftLink (TIndex pLeftLink) {aLeftLink = pLeftLink;} bool Family() {return aFamily;}};

Colocacin en Postorden Secuencial Se transforma a binario. Los nodos deben colocarse secuencialmente recorriendo al rbol en simtrico.3. Por cada nodo se registra dos campos:

INFO rbol binario recorrido en Simtrico GRADO Grado del nodo

Colocacin en Postorden SecuencialABFDECIJHGE 0F 0B 2G 0C 1H 0 I 0J 0 D 3A 3

GRADOTERM

Colocacin en Postorden SecuencialAclaraciones: Cada padre del rbol general est precedido de sus hijos, por tanto, es fcil encontrar el subrbol izquierdo de cada nodo del rbol binario. Se puede encontrar si recorremos la representacin secuencial comenzando por el ltimo elemento teniendo en cuenta el grado. Notar que si despus de un padre aparece un nodo sin hijos el padre del primero se busca al final. Ejemplo: el padre de C se busca al final.

Implementacin en C++class TPostOrderNode {private: void* aInfo; int aDegree;public: TPostOrderNode(void* pInfo, int pDegree) : aInfo(pInfo), aDegree(pDegree){} void* Info() {return aInfo;} int Degree() {return aDegree;}};