lkptr - simple reference LinKed PoinTeR:
Functions
Bin_Tree_Lib.h File Reference

Funciones de apoyo para la clase Bin_Tree<E>. More...

#include "Bin_Tree.h"
#include <cassert>
#include <iostream>
#include <set>
#include "A52512.h"

Go to the source code of this file.

Functions

template<class E >
int depth (const Bin_Tree< E > &T)
 Retorna la longitud del camino desde "T" hasta la raíz del árbol.
template<class E >
void height_recurse (Bin_Tree< E > T, int &max, int actual)
 Calcula la altura de sub-árbol.
template<class E >
int height (Bin_Tree< E > T)
 Retorna la altura de "T" o -1 si el árbol está vacío.
template<class E >
void copyDeep (Bin_Tree< E > &T, const Bin_Tree< E > &other)
 Copia profunda de "other".
template<class E >
bool comp (const Bin_Tree< E > &p, const Bin_Tree< E > &q)
 Compara recursivamente los árboles "p" y "q".
template<class E >
std::ostream & operator<< (std::ostream &COUT, const Bin_Tree< E > &T)
 Graba el valor del árbol como hilera Lisp: (a (b (f) (h)) (e (i) (k (l) (m (n) (o))))).
template<class E >
bool operator== (const Bin_Tree< E > &p, const Bin_Tree< E > &q)
template<class E >
bool operator!= (const Bin_Tree< E > &p, const Bin_Tree< E > &q)
template<class E >
int sizeStrong (const Bin_Tree< E > &T, std::set< E * > &S)
 Cuenta la cantidad de valores almacenados en el árbol.
template<class E >
bool check_ok (const Bin_Tree< E > &T)
 Usa T.ok() para verificar la invariante de Bin_Tree<E>
template<class E >
void orderedInsert (Bin_Tree< E > &T, const E &val)
 Agrega una copia de "val" al árbol binario ordenado "T".
template<class E >
void orderedInsert_Recursive (Bin_Tree< E > &T, const E &val)
 Agrega una copia de "val" al árbol binario ordenado "T".
template<class E >
bool homomorfo (const Bin_Tree< E > &T1, const Bin_Tree< E > &T2)
template<class E >
void mirror (Bin_Tree< E > T)
 Convierte a "T" en su sub-árbol espejo.
template<class E >
void IPD (std::ostream &COUT, const Bin_Tree< E > &T)
template<class E >
Bin_Tree< E > rotateWithLeftChild (Bin_Tree< E > K2)
 Rota la raíz del arbol binario "K2" con su hijo izquierdo.
template<class E >
Bin_Tree< E > rotateWithRightChild (Bin_Tree< E > K1)
 Rota la raíz del arbol binario "K1" con su hijo derecho.
template<class E >
Bin_Tree< E > doubleWithLeftChild (Bin_Tree< E > K3)
 Hace una rotacion doble con el hijo izquierda para el arbol binario "K3".
template<class E >
Bin_Tree< E > doubleWithRightChild (Bin_Tree< E > K1)
 Hace una rotacion doble con el hijo de la derecha para el arbol binario "K1".
template<class E >
void insertAVL (Bin_Tree< E > &T, const E &val)
 Inserta el valor "val" en el árbol "T".
template<class E >
void deleteAVL (Bin_Tree< E > &T, const E &val)
 Elimina el valor "val" del árbol "T".
template<class E >
void balanceAVL (Bin_Tree< E > &T)
 Balancea el árbol ordenado "T" si está desbalanceado.
template<class E >
bool isAscending (const Bin_Tree< E > &T)
 Verifica que "T" es un árbol ordendao ascendentemente.
template<class E >
bool isAVL (const Bin_Tree< E > &T)
 Verifica que "T" es un árbol balanceado AVL ascendente.

Detailed Description

Funciones de apoyo para la clase Bin_Tree<E>.

Author:
Adolfo Di Mare <adolfo@di-mare.com>
Date:
2007

Definition in file Bin_Tree_Lib.h.

Function Documentation

template<class E >
int depth ( const Bin_Tree< E > &  T)

Retorna la longitud del camino desde "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 ]

Definition at line 24 of file Bin_Tree_Lib.h.

template<class E >
void height_recurse ( Bin_Tree< E >  T,
int &  max,
int  actual 
)

Calcula la altura de sub-árbol.

  • Esta función es el paso recursivo necesario para implementar height().
  • Recorre recursivamente el árbol y recuerda la máxima profundidad encontrada en "max".
  • "actual" es la profundidad del nodo actual.

Definition at line 42 of file Bin_Tree_Lib.h.

template<class E >
int height ( Bin_Tree< E >  T) [inline]

Retorna la altura de "T" o -1 si el árbol está vacío.

  • La altura es la distanca desde "T" hasta la hoja más profunda en el sub-árbol formado por todos los descendientes de "T".
  • La altura de un nodo hoja siempre es cero.
  • [ T.isLeaf() == true ] ==> [ height(T) == 0 ]
  • [ T.isEmpty() == true ] ==> [ height(T) == -1 ] 
                                     [ 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]

Definition at line 76 of file Bin_Tree_Lib.h.

template<class E >
void copyDeep ( Bin_Tree< E > &  T,
const Bin_Tree< E > &  other 
)

Copia profunda de "other".

  • Copia todo el valor de "other" sobre "T", de forma que el nuevo valor de "*this" sea un duplicado exacto del valor de "other".
  • El valor anterior de "T" se pierde.
  • El objeto "other" mantiene su valor anterior.
  • Luego de la copia, cuando el valor de "other" cambia, el de "*this" no cambiará, y viceversa, pues la copia es una copia profunda; no es superficial.
  • Si "T" es "other" entonces su valor no cambia.
  • Después de esta operación siempre ocurre que T == other .
    Complejidad:
    O( T.count() ) + O( other.count() ).
    See also:
    http://www.di-mare.com/adolfo/binder/c04.htm#sc05

Definition at line 110 of file Bin_Tree_Lib.h.

template<class E >
bool comp ( const Bin_Tree< E > &  p,
const Bin_Tree< E > &  q 
)

Compara recursivamente los árboles "p" y "q".

Definition at line 141 of file Bin_Tree_Lib.h.

template<class E >
std::ostream& operator<< ( std::ostream &  COUT,
const Bin_Tree< E > &  T 
)

Graba el valor del árbol como hilera Lisp: (a (b (f) (h)) (e (i) (k (l) (m (n) (o))))).

Definition at line 163 of file Bin_Tree_Lib.h.

template<class E >
bool operator== ( const Bin_Tree< E > &  p,
const Bin_Tree< E > &  q 
) [inline]

Definition at line 182 of file Bin_Tree_Lib.h.

template<class E >
bool operator!= ( const Bin_Tree< E > &  p,
const Bin_Tree< E > &  q 
) [inline]

Definition at line 185 of file Bin_Tree_Lib.h.

template<class E >
int sizeStrong ( const Bin_Tree< E > &  T,
std::set< E * > &  S 
)

Cuenta la cantidad de valores almacenados en el árbol.

  • Cuenta conrrectamente aún si el árbol tiene ciclos.
  • El conjunto "S" registra cuáles sub-árboles fueron ya contados.
  • Lo usual es invocar S.clear() antes de invocar esta función.
    {{  // test::sizeStrong()
        Bin_Tree<E> Paco = E();      // Paco    Lola //
        Bin_Tree<E> Lola = E();      //              //
        Bin_Tree<E> Bebe;            //   E()   E()  //
        Lola.makeLeftChild( E() );   //     \\ /     //
        Bebe = Lola.left();          //     Bebe     //
        Bebe.makeLeftChild(  E() );  //     // \\    //
        Bebe.makeRightChild( E() );  //   E()   E()  //
        Paco.makeRightChild( Bebe );

        assertTrue( 4 == Paco.size() );             // Paco    Lola //
        assertTrue( 4 == Lola.size() );             //              //
        assertTrue( 3 == Bebe.size() );             //   E()   E()  //
        Paco.right().left().makeLeftChild(  Paco ); //  /  \\ /  \  //
        Lola.left().right().makeRightChild( Lola ); //  |  Bebe  |  //
        assertTrue( Paco == Bebe.left().left()  );  //  \  // \\ /  //
        assertTrue( Lola == Bebe.right().right() ); //   E()   E()  //

        std::set< E* > S; // hay que vaciarlo antes de incocar "sizeStrong()"
        S.clear(); assertTrue( 5 == sizeStrong( Paco, S ) );
        S.clear(); assertTrue( 5 == sizeStrong( Lola, S ) );

        // Como "S" no está vacío, "sizeStrong()" usa el valor actual
        const int ZERO = 0;
        assertTrue( ZERO == sizeStrong( Bebe, S ) );
    }}

See also:
test_Bin_Tree<E>::test_sizeStrong()

Definition at line 199 of file Bin_Tree_Lib.h.

template<class E >
bool check_ok ( const Bin_Tree< E > &  T) [inline]

Usa T.ok() para verificar la invariante de Bin_Tree<E>

Definition at line 214 of file Bin_Tree_Lib.h.

template<class E >
void orderedInsert ( Bin_Tree< E > &  T,
const E &  val 
)

Agrega una copia de "val" al árbol binario ordenado "T".

  • No agrega duplicados.

Definition at line 221 of file Bin_Tree_Lib.h.

template<class E >
void orderedInsert_Recursive ( Bin_Tree< E > &  T,
const E &  val 
)

Agrega una copia de "val" al árbol binario ordenado "T".

  • No agrega duplicados.
Author:
Carlos Andres Gonzalez Vargas <cagv26@gmail.com>

Definition at line 260 of file Bin_Tree_Lib.h.

template<class E >
bool homomorfo ( const Bin_Tree< E > &  T1,
const Bin_Tree< E > &  T2 
)

Definition at line 305 of file Bin_Tree_Lib.h.

template<class E >
void mirror ( Bin_Tree< E >  T)

Convierte a "T" en su sub-árbol espejo.

  • Recursivamente, sus hijos quedan en orden inverso del orden en el que aparecían originalmente en "T".
           a                  a
          / \                / \
         /   \              /   \
        b     e            e     b
       / \   / \          / \   / \
      f   h i   k        k   i h   f
               / \      / \
              l  m      m   l
                / \    / \
               n   o  o   n

Definition at line 359 of file Bin_Tree_Lib.h.

template<class E >
void IPD ( std::ostream &  COUT,
const Bin_Tree< E > &  T 
)

Definition at line 374 of file Bin_Tree_Lib.h.

template<class E >
Bin_Tree<E> rotateWithLeftChild ( Bin_Tree< E >  K2)

Rota la raíz del arbol binario "K2" con su hijo izquierdo.

Author:
Jorge Arturo Cordero Vargas <corderazo00@hotmail.com>
Mark Allen Weiss 
              [ K2 ]                 [ K1 ]
             /      \     ====\     /      \
            /        \    ====/    /        \
      [ K1 ]         /\           /\         [ K2 ]
     /      \       /  \         /  \       /      \
    /        \     /  Z \       / X  \     /        \
   /\        /\   /______\     /______\   /\        /\
  /  \      /  \                         /  \      /  \
 / X  \    /  Y \                       / Y  \    /  Z \
/______\  /______\                     /______\  /______\

Definition at line 400 of file Bin_Tree_Lib.h.

template<class E >
Bin_Tree<E> rotateWithRightChild ( Bin_Tree< E >  K1)

Rota la raíz del arbol binario "K1" con su hijo derecho.

Author:
Jorge Arturo Cordero Vargas <corderazo00@hotmail.com>
Mark Allen Weiss 
      [ K1 ]                                 [ K2 ]
     /      \             ====\             /      \
    /        \            ====/            /        \
   /\         [ K2 ]                 [ K1 ]         /\
  /  \       /      \               /      \       /  \
 / X  \     /        \             /        \     /  Z \
/______\   /\        /\           /\        /\   /______\
          /  \      /  \         /  \      /  \
         / Y  \    /  Z \       / X  \    /  Y \
        /______\  /______\     /______\  /______\

Definition at line 424 of file Bin_Tree_Lib.h.

template<class E >
Bin_Tree<E> doubleWithLeftChild ( Bin_Tree< E >  K3)

Hace una rotacion doble con el hijo izquierda para el arbol binario "K3".

  • Primero rota el hijo izquierdo con su hijo derecho.
  • Luego "K3" con el nuevo hijo izquierdo.
Author:
Jorge Arturo Cordero Vargas <corderazo00@hotmail.com>
Mark Allen Weiss
              [ K3 ]                            [ K2 ]
             /      \                          /      \
            /        \                       /          \
      [ K1 ]         /\                    /              \
     /      \       /  \  ====\      [ K1 ]                [ K3 ]
    /        \     /  D \ ====/     /      \              /      \
   /\      [ K2 ] /______\         /        \            /        \
  /  \      /  \                  /\        /\          /\        /\
 / A  \    /    \                /  \      /  \        /  \      /  \
/______\  /      \              / A  \    /  B \      / C  \    /  D \
         /\      /\            /______\  /______\    /______\  /______\
        /  \    /  \
       / B  \  /  C \
      /______\/______\         K1 <= K2 <= K3

Definition at line 456 of file Bin_Tree_Lib.h.

template<class E >
Bin_Tree<E> doubleWithRightChild ( Bin_Tree< E >  K1)

Hace una rotacion doble con el hijo de la derecha para el arbol binario "K1".

  • Primero rota el hijo derecho con su hijo izquierdo.
  • Luego "K3" con el nuevo hijo derecho.
Author:
Jorge Arturo Cordero Vargas <corderazo00@hotmail.com>
Mark Allen Weiss
      [ K1 ]                                    [ K2 ]
     /      \                                  /      \
    /        \                               /          \
   /\         [ K3 ]                       /              \
  /  \       /      \     ====\      [ K1 ]                [ K3 ]
 / A  \     /        \    ====/     /      \              /      \
/______\ [ K2 ]      /\            /        \            /        \
          /  \      /  \          /\        /\          /\        /\
         /    \    /  D \        /  \      /  \        /  \      /  \
        /      \  /______\      / A  \    /  B \      / C  \    /  D \
       /\      /\              /______\  /______\    /______\  /______\
      /  \    /  \
     / B  \  /  C \
    /______\/______\           K1 <= K2 <= K3

Definition at line 488 of file Bin_Tree_Lib.h.

template<class E >
void insertAVL ( Bin_Tree< E > &  T,
const E &  val 
)

Inserta el valor "val" en el árbol "T".

  • No agrega duplicados.
  • Usa inserción AVL para mantener a "T" balanceado.
Author:
Jorge Arturo Cordero Vargas <corderazo00@hotmail.com>
Mark Allen Weiss
Date:
2007
See also:
http://www.cs.fiu.edu/~weiss/dsaajava/code/DataStructures/AvlTree.java

Definition at line 505 of file Bin_Tree_Lib.h.

template<class E >
template< class E > void deleteAVL ( Bin_Tree< E > &  T,
const E &  val 
)

Elimina el valor "val" del árbol "T".

  • Usa borrado AVL para mantener a "T" balanceado.
template<class E >
template< class E > void balanceAVL ( Bin_Tree< E > &  T)

Balancea el árbol ordenado "T" si está desbalanceado.

template<class E >
bool isAscending ( const Bin_Tree< E > &  T)

Verifica que "T" es un árbol ordendao ascendentemente.

Definition at line 581 of file Bin_Tree_Lib.h.

template<class E >
bool isAVL ( const Bin_Tree< E > &  T)

Verifica que "T" es un árbol balanceado AVL ascendente.

Definition at line 607 of file Bin_Tree_Lib.h.

 All Classes Namespaces Files Functions Variables Typedefs Friends Defines
Generated on Mon Jun 20 2011 09:59:13 for lkptr - simple reference LinKed PoinTeR: by  doxygen 1.7.4