// Bin_Tree_Lib.h (c) 2007 adolfo@di-mare.com /** \file Bin_Tree_Lib.h \brief Funciones de apoyo para la clase \c Bin_Tree. \author Adolfo Di Mare \date 2007 - Why English names??? ==> http://www.di-mare.com/adolfo/binder/c01.htm#sc04 */ #include "Bin_Tree.h" #include // assert() #include // cout #include /** Retorna la longitud del camino desde \c "T" hasta la raíz del árbol. - Retorna la profundidad del sub-árbol respecto de su raíz. - La profundidad de la raíz del árbol es cero. - [ T.isEmpty() ] ==> [ depth(T) == 0 ] - [ T.isEmpty() == true ] ==> [ height(T) == -1 ] */ template int depth( const Bin_Tree & T ) { if ( T.isEmpty() ) { return -1; } unsigned n = 0; Bin_Tree F = T; do { F = F.father(); ++n; } while ( ! F.isEmpty() ); return n-1; } /// Calcula la altura de sub-árbol. /// - Esta función es el paso recursivo necesario para implementar \c height(). /// - Recorre recursivamente el árbol y recuerda la máxima profundidad encontrada en \c "max". /// - \c "actual" es la profundidad del nodo actual. template void height_recurse( Bin_Tree T, int &max, int actual ) { if ( T.isEmpty() ) { if (max < actual) { max = actual; // se deja el más grande de los 2 } } else { height_recurse( T.left(), max, actual+1 ); height_recurse( T.right(), max, actual+1 ); } return; } /** Retorna la altura de \c "T" o \c -1 si el árbol está vacío. - La altura es la distanca desde \c "T" hasta la hoja más profunda en el sub-árbol formado por todos los descendientes de \c "T". - La altura de un nodo hoja siempre es cero. - [ T.isLeaf() == true ] ==> [ height(T) == 0 ] - [ T.isEmpty() == true ] ==> [ height(T) == -1 ] \code [ depth() height() ] a [0 4] a [0 4] |--b [1 1] |--b [1 1] | |--f [2 0] | |--f [2 0] | +--h [2 0] | +--h [2 0] +--e [1 3] +--e [1 3] |--i [2 0] |--i [2 0] +--j [2 2] +--j [2 2] |--l [3 0] |--l [3 0] +--m [3 1] +--m [3 1] |--n [4 0] |--n [4 0] +--o [4 0] +--o [4 0] \endcode */ template inline int height( Bin_Tree T ) { #if 1 if( T.isEmpty() ) { return -1; } else { int hLeft = height( T.left() ); int hRigth = height( T.right() ); return 1 + ( hLeft > hRigth ? hLeft : hRigth ); } #else int actual, max; max = 0; actual = 0; height_recurse( T, max, actual ); // max = ( max > 0 ? max-1 : 0 ); return max-1; #endif } /** Copia profunda de \c "other". - Copia todo el valor de \c "other" sobre \c "T", de forma que el nuevo valor de \c "*this" sea un duplicado exacto del valor de \c "other". - El valor anterior de \c "T" se pierde. - El objeto \c "other" mantiene su valor anterior. - Luego de la copia, cuando el valor de \c "other" cambia, el de \c "*this" no cambiará, y viceversa, pues la copia es una copia profunda; no es superficial. - Si \c "T" es \c "other" entonces su valor no cambia. - Después de esta operación siempre ocurre que T == other . \par Complejidad: O( \c T.count() ) + O( \c other.count() ). \see http://www.di-mare.com/adolfo/binder/c04.htm#sc05 */ template void copyDeep( Bin_Tree& T, const Bin_Tree &other ) { if ( &T == &other ) { return; // mismo árbol ==> evita auto-copia } else if ( other.isEmpty() ) { // si el otro está vacío T.erase(); // yo también quedo vacío return; } if ( T.same(other) ) { // T.erase(); // mismo valor ==> borra a "T" } Bin_Tree Root( other.data() ); // nueva raíz del árbol if ( ! other.left().isEmpty() ) { // copia el hijo izquierdo Bin_Tree Child; copyDeep( Child, other.left() ); Root.makeLeftChild( Child ); } if ( ! other.right().isEmpty() ) { // copia el hijo derecho Bin_Tree Child; copyDeep( Child, other.right() ); Root.makeRightChild( Child ); } T = Root; } /// Compara recursivamente los árboles \c "p" y \c "q". template bool comp(const Bin_Tree& p, const Bin_Tree& q) { if ( p.same(q) ) { return true; } if ( p.isEmpty() || q.isEmpty() ) { // son diferentes... return false; // ...pues sólo 1 está vácio } if ( ! (p.data() == q.data()) ) { return false; // valor diferente en la raíz } if ( ! comp( p.left(), q.left() ) ) { return false; // valor diferente en el sub-árbol izquierdo } if ( ! comp( p.right(), q.right() ) ) { return false; // valor diferente en el sub-árbol derecho } return true; // pues nunca encontró sub-árboles diferentes } /// Graba el valor del árbol como hilera Lisp: \c (a (b (f) (h)) (e (i) (k (l) (m (n) (o))))). template std::ostream& operator << ( std::ostream & COUT , const Bin_Tree & T ) { if ( T.isEmpty() ) { return COUT; } { COUT << '(' << *T; // raíz if ( ! T.left().isEmpty() ) { COUT << ' '; COUT << T.left(); } if ( ! T.right().isEmpty() ) { COUT << ' '; COUT << T.right(); } COUT << ')'; } return COUT; } template inline bool operator == (const Bin_Tree &p, const Bin_Tree &q) { return comp( p , q ); } template inline bool operator != (const Bin_Tree &p, const Bin_Tree &q) { return !(p == q); } /** Cuenta la cantidad de valores almacenados en el árbol. - Cuenta conrrectamente aún si el árbol tiene ciclos. - El conjunto \c "S" registra cuáles sub-árboles fueron ya contados. - Lo usual es invocar \c S.clear() antes de invocar esta función. \dontinclude test_Bin_Tree.cpp \skipline test::sizeStrong() \until }} \see test_Bin_Tree::test_sizeStrong() */ template int sizeStrong( const Bin_Tree& T, std::set & S ) { if ( T.isEmpty() ) { return 0; } else if ( S.find( &T.data() ) == S.end() ) { S.insert( &T.data() ); return 1 + sizeStrong( T.left() , S ) + sizeStrong( T.right() , S ); } else { return 0; } } /// Usa \c T.ok() para verificar la invariante de \c Bin_Tree template inline bool check_ok(const Bin_Tree& T) { return T.ok(); } /// Agrega una copia de \c "val" al árbol binario ordenado \c "T". /// - No agrega duplicados. template void orderedInsert( Bin_Tree & T , const E& val ) { // Versión no recursiva if ( T.isEmpty() ) { T.changeRoot( val ); return; } Bin_Tree Root = T; // Root es la raíz Bin_Tree Child ( val ); // El nuevo sub-árbol hoja a insertar while ( ! Root.isEmpty() ) { if ( val < Root.data() ) { if ( Root.left().isEmpty() ) { Root.makeLeftChild( Child ); break; } else { Root = Root.left(); } } else if ( val > Root.data() ) { if ( Root.right().isEmpty() ) { Root.makeRightChild( Child ); break; } else { Root = Root.right(); } } else { break; // DUPLICADO: no hace nada } } return; } /// Agrega una copia de \c "val" al árbol binario ordenado \c "T". /// - No agrega duplicados. /// /// \author Carlos Andres Gonzalez Vargas template void orderedInsert_Recursive( Bin_Tree & T , const E& val ) { if ( T.isEmpty() ) { // Si el arbol esta vacío T.changeRoot( val ); // insertar el valor en el arbol return; } if ( val < T.data() ){ // si el valor del arbol es menor que le valor a insertar if ( T.left().isEmpty() ){ // si el hijo izquierdo esta vacio T.makeLeftChild( Bin_Tree(val) ); // inserte un nuevo subarbol con el valor a insertar return; } else { //si el hijo izquierdo existe orderedInsert( T.left(), val ); //insertese ahora con el hijo izquierdo como base } } else if ( val > T.data() ) {//si el valor del arbol es mayor que le valor a insertar if ( T.right().isEmpty() ){//si el hijo derecho esta vacio T.makeRightChild(Bin_Tree (val)); //inserte un nuevo subarbol con el valor a insertar return;//regresar } else { //si el hijo derecho existe orderedInsert(T.right(),val);//insertese ahora con el hijo derecho como base } } else { return; // no inserta duplicados } return; //regresar } /* Determina si existe un reordenamiento de los hijos del árbol \c T1 que resulta en el árbol \c T2. - Los siguientes árboles son homomorfos: \code a a a / \ / \ / \ / \ / \ / \ b e e b e b / \ / \ / \ / \ / \ / \ f h i k k i h f i k f h / \ / \ / \ l m m l m l / \ / \ / \ n o o n n o \endcode */ template bool homomorfo( const Bin_Tree & T1, const Bin_Tree & T2 ) { if ( T1.isEmpty() && T2.isEmpty() ) { return true; // 2 árboles vacíos son homomorfos } if ( T1.isEmpty() || T2.isEmpty() ) { return false; // solo 1 de los 2 no está vacío } if ( T1.data() != T2.data() ) { return false; // valor diferente en la raíz del árbol } /* T1 T2 / \ / \ / \ / \ T1_paco T1_lola T2_paco T2_lola */ Bin_Tree T1_paco = T1.left(); Bin_Tree T2_paco = T2.left(); Bin_Tree T1_lola = T1.right(); Bin_Tree T2_lola = T2.right(); if ( homomorfo( T1_paco, T2_paco ) ) { if ( homomorfo( T1_lola, T2_lola ) ) { return true; } if ( homomorfo( T1_paco, T2_lola ) ) { return homomorfo( T1_lola, T2_paco ); } else { return false; } } else if ( homomorfo( T1_paco, T2_lola ) ) { return homomorfo( T1_lola, T2_paco ); } else { // assert( !homomorfo( T1_paco, T2_paco ) && ! homomorfo( T1_paco, T2_lola ) ); return false; } } /** Convierte a \c "T" en su sub-árbol espejo. - Recursivamente, sus hijos quedan en orden inverso del orden en el que aparecían originalmente en \c "T". \code a a / \ / \ / \ / \ b e e b / \ / \ / \ / \ f h i k k i h f / \ / \ l m m l / \ / \ n o o n \endcode */ template void mirror( Bin_Tree T ) { if ( T.isEmpty() ) { return; // se sale si el árbol está vacío } // intercambia los hijos Bin_Tree Left = T.left(); // sostiene a cada hijo Bin_Tree Right = T.right(); T.makeLeftChild( Right ); // Pone el hijo derecho a la izquierda T.makeRightChild( Left ); // Pone el hijo izquierdo a la derecha mirror( Left ); mirror( Right ); // recursivamente modifica los hijos } // Graba en \c COUT en orden IPD el contenido del árbol binario \c "T". template void IPD( std::ostream & COUT, const Bin_Tree & T ) { if ( T.isEmpty() ) { return; // porque ya terminó } IPD ( COUT , T.left() ); COUT << " " << T.data(); IPD ( COUT , T.right() ); } /** Rota la raíz del arbol binario \c "K2" con su hijo izquierdo. \author Jorge Arturo Cordero Vargas \author Mark Allen Weiss \code [ K2 ] [ K1 ] / \ ====\ / \ / \ ====/ / \ [ K1 ] /\ /\ [ K2 ] / \ / \ / \ / \ / \ / Z \ / X \ / \ /\ /\ /______\ /______\ /\ /\ / \ / \ / \ / \ / X \ / Y \ / Y \ / Z \ /______\ /______\ /______\ /______\ \endcode */ template Bin_Tree rotateWithLeftChild( Bin_Tree K2 ) { Bin_Tree K1 = K2.left(); // AvlNode k1 = k2.left; K2.makeLeftChild( K1.right() ); // k2.left = k1.right; K1.makeRightChild( K2 ); // k1.right = k2; return K1; // return k1; } /** Rota la raíz del arbol binario \c "K1" con su hijo derecho. \author Jorge Arturo Cordero Vargas \author Mark Allen Weiss \code [ K1 ] [ K2 ] / \ ====\ / \ / \ ====/ / \ /\ [ K2 ] [ K1 ] /\ / \ / \ / \ / \ / X \ / \ / \ / Z \ /______\ /\ /\ /\ /\ /______\ / \ / \ / \ / \ / Y \ / Z \ / X \ / Y \ /______\ /______\ /______\ /______\ \endcode */ template Bin_Tree rotateWithRightChild( Bin_Tree K1 ) { Bin_Tree K2 = K1.right(); // AvlNode k2 = k1.right; K1.makeRightChild( K2.left() ); // k1.right = k2.left; K2.makeLeftChild( K1 ); // k2.left = k1; return K2; // return k2; } /** Hace una rotacion doble con el hijo izquierda para el arbol binario \c "K3". - Primero rota el hijo izquierdo con su hijo derecho. - Luego \c "K3" con el nuevo hijo izquierdo. \author Jorge Arturo Cordero Vargas \author Mark Allen Weiss \code [ K3 ] [ K2 ] / \ / \ / \ / \ [ K1 ] /\ / \ / \ / \ ====\ [ K1 ] [ K3 ] / \ / D \ ====/ / \ / \ /\ [ K2 ] /______\ / \ / \ / \ / \ /\ /\ /\ /\ / A \ / \ / \ / \ / \ / \ /______\ / \ / A \ / B \ / C \ / D \ /\ /\ /______\ /______\ /______\ /______\ / \ / \ / B \ / C \ /______\/______\ K1 <= K2 <= K3 \endcode */ template Bin_Tree doubleWithLeftChild( Bin_Tree K3 ) { K3.makeLeftChild( rotateWithRightChild( K3.left() ) ) ; // k3.left = rotateWithRightChild( k3.left ); return rotateWithLeftChild( K3 ); // return rotateWithLeftChild( k3 ); } /** Hace una rotacion doble con el hijo de la derecha para el arbol binario \c "K1". - Primero rota el hijo derecho con su hijo izquierdo. - Luego \c "K3" con el nuevo hijo derecho. \author Jorge Arturo Cordero Vargas \author Mark Allen Weiss \code [ K1 ] [ K2 ] / \ / \ / \ / \ /\ [ K3 ] / \ / \ / \ ====\ [ K1 ] [ K3 ] / A \ / \ ====/ / \ / \ /______\ [ K2 ] /\ / \ / \ / \ / \ /\ /\ /\ /\ / \ / D \ / \ / \ / \ / \ / \ /______\ / A \ / B \ / C \ / D \ /\ /\ /______\ /______\ /______\ /______\ / \ / \ / B \ / C \ /______\/______\ K1 <= K2 <= K3 \endcode */ template Bin_Tree doubleWithRightChild( Bin_Tree K1 ) { K1.makeRightChild( rotateWithLeftChild( K1.right() ) ); // k1.right = rotateWithLeftChild( k1.right ); return rotateWithRightChild( K1 ); // return rotateWithRightChild( k1 ); } /** Inserta el valor \c "val" en el árbol \c "T". - No agrega duplicados. - Usa inserción AVL para mantener a \c "T" balanceado. \author Jorge Arturo Cordero Vargas \author Mark Allen Weiss \date 2007 \see http://www.cs.fiu.edu/~weiss/dsaajava/code/DataStructures/AvlTree.java */ template void insertAVL( Bin_Tree & T, const E & val ) { if ( T.isEmpty() ) { T.changeRoot( val ); } else if ( val < T.data() ) { if ( T.left().isEmpty() ) { T.makeLeftChild( Bin_Tree(val) ); } else { Bin_Tree Left = T.left(); insertAVL( Left , val ); T.makeLeftChild( Left ); } if ( height(T.left())-height(T.right()) == 2 ) { if ( val < T.left().data() ) { T = rotateWithLeftChild( T ); } else { T = doubleWithLeftChild( T ); } } } else if ( val > T.data() ) { if ( T.right().isEmpty() ) { T.makeRightChild( Bin_Tree(val) ); } else { Bin_Tree Right = T.right(); insertAVL( Right , val ); T.makeRightChild( Right ); } if ( height(T.right())-height(T.left()) == 2 ) { if ( val > T.right().data() ) { T = rotateWithRightChild( T ); } else { T = doubleWithRightChild( T ); } } } else { ; // DUPLICADO: no hace nada } return; /* El método \c insertAVL() deberá insertar en un árbol binario un valor no repetido, y asegurarse de que el árbol se encuentre siempre balanceado, esto es, que en ninguno de sus nodos la altura del subárbol derecho y la del subárbol izquierdo difieran en mas de 1 nivel. Para esto, se buscó un algoritmo en internet - http://www.cs.fiu.edu/~weiss/dsaajava/code/DataStructures/AvlTree.java que cumpliera con la especificación de la tarea. Este algoritmo se encarga de insertar un nodo en el árbol con insert(), y determinar, de ser necesario, el tipo y dirección de la rotación que se debe hacer en éste, ya sea unitaria con las funciones \c rotateWithLeftChild() y \c rotateWithRightChild(), o dobles con \c doubleWithLeftChild() y \c doubleWithLeftChild(); para reestablecer el balance del árbol. */ } /** \fn template void deleteAVL( Bin_Tree & T , const E& val ); \brief Elimina el valor \c "val" del árbol \c "T". - Usa borrado AVL para mantener a \c "T" balanceado. */ template void deleteAVL( Bin_Tree & T , const E & val ); /** \fn template void balanceAVL( Bin_Tree & T ); \brief Balancea el árbol ordenado \c "T" si está desbalanceado. */ template void balanceAVL( Bin_Tree & T ); /// Verifica que \c "T" es un árbol ordendao ascendentemente. template bool isAscending( const Bin_Tree & T ) { if ( T.isEmpty() ) { return true; } if ( ! isAscending( T.left() ) ) { return false; } if ( ! isAscending( T.right() ) ) { return false; } // verifica que los hijos estén correctamente ordenados if ( ! T.left().isEmpty() ) { if ( ! ( T.left().data() <= T.data() ) ) { return false; // hijo izquierdo desordenado } } if ( ! T.right().isEmpty() ) { if ( ! ( T.right().data() >= T.data() ) ) { return false; // hijo derecho desordenado } } return true; } /// Verifica que \c "T" es un árbol balanceado AVL ascendente. template bool isAVL( const Bin_Tree & T ) { if ( T.isEmpty() ) { return true; } if ( ! isAVL( T.left() ) ) { return false; } if ( ! isAVL( T.right() ) ) { return false; } // verifica que la altura de los hijos difiera en 1 como máximo int left = height( T.left() ); int right = height( T.right() ); int diff = ( left > right ? left-right : right-left ); if (diff > 1) { return false; } // verifica que los hijos estén correctamente ordenados if ( ! T.left().isEmpty() ) { if ( ! ( T.left().data() <= T.data() ) ) { return false; // hijo izquierdo desordenado } } if ( ! T.right().isEmpty() ) { if ( ! ( T.right().data() >= T.data() ) ) { return false; // hijo derecho desordenado } } return true; } #if 0 template void balanceAVL( Bin_Tree & T ) { } template void insertAVL( Bin_Tree & T , const E& val ) { orderedInsert( T , val ); balanceAVL(T); } template void deleteAVL( Bin_Tree & T , const E& val) { orderedDelete( T , val ); balanceAVL(T); } #else // #include "A41369-A55609.h" #include "A52512.h" // #include "A54641.h" #endif // EOF: Bin_Tree_Lib.h