Estructura de Datos : Arboles Binarios - Fundamentos

Definiciones

Un árbol binario es un conjunto finito de nodos, el que puede ser, un conjunto vacio o un conjunto que contine un nodo raíz y dos árboles binarios disjuntos, llamados subárbol isquierdo y subárbol derecho.

Cada nodo de un árbol binario puede tener, a lo sumo dos ramas, por lo que el grado máximo de un nodo de un árbol binario es dos. Así, un nodo de un árbol binario, puede tener 0, 1 ó 2 hijos.

Un árbol binario puede no tener nodo alguno.

Ejemplos

        *---*    *---*                        *---*                    *---*
        | A |    | A |                        | A |                    | A |                ......... Nivel 1
        *---*    *---*                        *---*                    *---*
         |          |                          |                        | |
      +--+          +--+                    +--+                 +------+ +------+
      |                |                    |                    |               |
    *---*            *---*                *---*                *---*           *---*
    | B |            | B |                | B |                | B |           | C |        ......... Nivel 2
    *---*            *---*                *---*                *---*           *---*
                                           |                    | |             | |
                                        +--+                 +--+ +--+       +--+ +--+
                                        |                    |       |       |       |
                                      *---*                *---*   *---*   *---*   *---*
                                      | C |                | D |   | E |   | F |   | G |    ......... Nivel 3
                                      *---*                *---*   *---*   *---*   *---*
                                       |                    | |
                                    +--+                 +--+ +--+
                                    |                    |       |
                                  *---*                *---*   *---*
                                  | D |                | H |   | I |                        ......... Nivel 4
                                  *---*                *---*   *---*
                                   |
                                +--+
                                |
                              *---*
                              | E |                                                         ......... Nivel 5
                              *---*

     Arbol 1      Arbol 2            Arbol 3                          Arbol 4
                                                                                                Profundidad   Nodos por Nivel   Nodos a Profundidad
                                          *---*
                            comenzar .....| 1 |...................>......                            1          2**(1-0)=1          (2**1)-1=1
                                          *---*                         .
                                           | |                          .
                            +--------------+ +--------------+           .
             .....<.........|...............<...............|.....<......
             .            *---*                           *---*
             .....>.......| 2 |.............>.............| 3 |...>................                  2          2**(2-0)=2          (2**2)-1=3
                          *---*                           *---*                   .
                           | |                             | |                    .
                    +------+ +------+               +------+ +------+             .
      ......<.......|...............|.......<.......|...............|.......<......
      .           *---*           *---*           *---*           *---*
      ......>.....| 4 |...........| 5 |.....>.....| 6 |...........| 7 |.....>..........              3          2**(3-0)=4          (2**3)-1=7
                  *---*           *---*           *---*           *---*               .
                   | |             | |             | |             | |                .
                +--+ +--+       +--+ +--+       +--+ +--+       +--+ +--+             .
  ......<.......|.......|.......|.......|...<...|.......|.......|.......|.......<......
  .           *---*   *---*   *---*   *---*   *---*   *---*   *---*   *---*
  ......>.....| 8 |...| 9 |...|1 0|...|1 1|.>.|1 2|...|1 3|...|1 4|...|1 5|..... terminar            4          2**(4-0)=8          (2**4)-1=1
              *---*   *---*   *---*   *---*   *---*   *---*   *---*   *---*
                                                                                                     .
                                         Arbol 5                                                     .
                                                                                                     .

                                                                                                     k          2**(k-0)=n          (2**k)-1=m

El Arbol 1 y el Arbol 2 son árboles binarios distintos, ya que si bien tienen los mismos nodos su disposición es diferente, árboles binarios que si fueran árboles comunes, serían el mismo árbol común. El Arbol 3 es un árbol binario sesgado. El Arbol 4 es un árbol completo. El Arbol 5 es un árbol lleno. Los nodos de un árbol pueden enumerarse, como puede verse en el Arbol 5, numerándolos nivel a nivel, de isquierda a derecha.

Interfases

structure BTREE

declare
- CREATE() ---> btree
- ISMTBT(btree) ---> boolean
- MAKEBT(btree, item, btree) ---> btree
- LCHILD(btree) ---> btree
- DATA(btree) ---> item
- RCHILD(btree) ---> btree
for all p, r perteneciente a btree y d perteneciente a item let
- ISMTBT(CREATE()) :: = true
- ISMTBT(MAKEBT(p,d,r)) :: = false
- LCHILD(MAKEBT(p,d,r)) :: = p; LCHILD(CREATE) :: = error
- DATA(MAKEBT(p,d,r)) :: = d; DATA(CREATE) :: = error
- RCHILD(MAKEBT(p,d,r)) :: = r; RCHILD(CREATE) :: = error
end

end BTREE

Observar que MAKEBT() lleva a armar el árbol desde abajo hacia arriba, desde los nodos hojas hacia el nodo raíz.

Terminología

Arbol Binario ( BTree )

Arbol Binario Sesgado ( Skewed BTree ) En inglés skew significa sego, sesgar, torcerse.

Arbol Binario Completo ( Completed BTree )

Arbol Binario Lleno ( Full BTree )

Subárbol Isquierdo ( Left Subtree )

Subárbol Derecho ( Right Sbutree )

Nodo ( Node ) También llamado vértice o elemento del árbol. Es el contenedor de los datos y los enlaces a sus hijos y a su padre.

Nodo Raíz ( Root Node ) Es el nodo donde comienza el árbol. Cada árbol tiene solamente un nodo raíz, desde el cual cuelgan todos sus descendientes.

Nodo Rama ( Branch Node ) También llamado nodo interior o interno. Es un nodo cualquiera que puede tener hijos, aunque en este preciso momento no los tenga.

Nodos de Grado Cero ( n0 )

Nodos de Grado Uno ( n1 )

Nodos de Grado Dos ( n2 )

Lemas

El máximo número de nodos en un nivel i de un árbol binario es 2 ** ( i - 1 ), para i >= 1.

El máximo número de nodos en un árbol binario de profundidad k es ( 2 ** k ) - 1, para k >= 1.

Para cualquier árbol binario no vacio, si n0 es el número de nodos terminales y n2 es el número de nodos de grado 2, luego n0 = n2 + 1.

La profundidad de un árbol binario completo es el entero piso de log2 n, más 1.

Para cualquier árbol binario completo con n nodos que es representado secuencialmente, para cualquier nodo de índice i, para 1 =< i <= n, se tiene :

PARENT(i) está en el índice entero piso de i / 2, si i es distinto de 1, y si i es igual a 1, es el nodo raíz y no tiene padre.
LCHILD(i) está en el índice 2 * i, si 2 * i es menor que n, y si 2 * i es mayor que n, no tiene hijo isquierdo.
RCHILD(i) está en el índice ( 2 * i ) + 1, si ( 2 * i ) + 1 es menor que n, y si ( 2 * i ) + 1 es mayor que n, no tiene hijo derecho.

Representaciones

Representaciones Secuenciales

                    *-----*                     *-----*
               (1)  |  A  |                (1)  |  A  |
                    |-----|                     |-----|
               (2)  |  B  |                (2)  |  B  |
                    |-----|                     |-----|
               (3)  |     |                (3)  |  C  |
                    |-----|                     |-----|
               (4)  |  C  |                (4)  |  D  |
                    |-----|                     |-----|
               (5)  |     |                (5)  |  E  |
                    |-----|                     |-----|
               (6)  |     |                (6)  |  F  |
                    |-----|                     |-----|
               (7)  |     |                (7)  |  G  |
                    |-----|                     |-----|
               (8)  |  D  |                (8)  |  H  |
                    |-----|                     |-----|
               (9)  |     |                (9)  |  I  |
                    |-----|                     *-----*
                .      .
                .      .
                .      .
                    |-----|
              (16)  |  E  |
                    *-----*

                    Arbol 3                     Arbol 4

Observar que esta representación está basada en la enumeración de los nodos y en uno de los lemas vistos en el punto anterior.

Representaciones Enlazadas

          *------------------------*                          *------------------------*
          | LCHILD | DATA | RCHILD |                          |    *   | DATA |   *    |
          *------------------------*                          *----|--------------|----*
                                                                   |              |
              1 Nodo - 3 Campos                            +-------+              +-------+
                                                           |                              |
                                              *------------------------*      *------------------------*
                                              |        | DATA |        |      |        | DATA |        |
                                              *------------------------*      *------------------------*

                                                        LCHILD                          RCHILD


       *---------------------*                                                                *---------------------*
T ---> |   *   |  A  |   0   |                                                         T ---> |   *   |  A  |   *   |
       *---|-----------------*                                                                *---|-------------|---*
           |                                                                   +------------------+             +------------------+
           V                                                                   V                                                   V
       *---------------------*                                      *---------------------*                             *---------------------*
       |   *   |  B  |   0   |                                      |   *   |  B  |   *   |                             |   *   |  C  |   *   |
       *---|-----------------*                                      *---|-------------|---*                             *---|-------------|---*
           |                                                      +-----+             +-----+                         +-----+             +-----+
           V                                                      V                         V                         V                         V
       *---------------------*                         *---------------------*   *---------------------*   *---------------------*   *---------------------*
       |   *   |  C  |   0   |                         |   *   |  D  |   *   |   |   0   |  E  |   0   |   |   0   |  F  |   0   |   |   0   |  G  |   0   |
       *---|-----------------*                         *---|-------------|---*   *---------------------*   *---------------------*   *---------------------*
           |                                         +-----+             +-----+
           V                                         V                         V
       *---------------------*            *---------------------*   *---------------------*
       |   *   |  D  |   0   |            |   0   |  H  |   0   |   |   0   |  I  |   0   |
       *---|-----------------*            *---------------------*   *---------------------*
           |
           V
       *---------------------*
       |       |  E  |       |
       *---------------------*

               Arbol 3                                                                                Arbol 4

Observar que con esta representación solo es posible navegar desde la raíz hacia los hijos, y nunca volver hacia el padre.

Representaciones Orientadas a Objetos

                                                                                                                       Nodo  A
    *---------------------------------------*                                                                     *---------------*
    |                                       |                                                                     |     *---*     |
    |                 *---*                 |                                                                     |     | 0 |     |
    |                 |   |                 |   Padre                                                ............>|     *---*     |<............
    |                 *---*                 |   Campo de enlace                                      .            |   *---*---*   |            .
    |                                       |                               *---*                    .            |   | . | . |   |            .
    |                                       |                               | A |                    .            |   *-.-*-.-*   |            .
    |     *---------- ..... ----------*     |                               *---*                    .            *-----.---.-----*            .
    |     |   |   |           |   |   |     |   Datos                        | |                     .                  .   .                  .     Para simplificar
    |     *---------- ..... ----------*     |   Campos de informacion     +--+ +--+               *--.------------*     .   .     *------------.--*  el dibujo se
    |                                       |                             |       |               |  .  *---*     |     .   .   C |     *---*  .  |  omitieron los
    |                                       |                           *---*   *---*             |  ...... |     |     .   .     |     | ......  |  campos de informacion
    |               *-------*               |                           | B |   | C |             |     *---*     |<.....   .....>|     *---*     |
    |               |   |   |               |   Hijos                   *---*   *---*             |   *---*---*   |               |   *---*---*   |
    |               *-------*               |   Campos de enlaces                                 |   | 0 | 0 |   |               |   | 0 | 0 |   |
    |                                       |                                                     |   *---*---*   |               |   *---*---*   |
    *---------------------------------------*                                                     *---------------*               *---------------*
                                                                           Arbol 6                     Nodo  B         Arbol 6         Nodo  C

Travesías de Arboles Binarios

En inglés este algoritmo se conoce como Binary Tree Traversal. Traversal significa travesía. Existen alternativas de este algoritmo según el órden en que se visite el nodo, entendido como el procesamiento de los datos que contiene el mismo. Si señalamos con :

L si seguimos el hijo isquierdo

R si seguimos el hijo derecho

D si procesamos los datos del nodo

deben considerarse las siguientes alternativas :

LDR ----> Inorder
LRD ----> Postorder
DLR ----> Preorder
DRL
RDL
RLD

donde las alternativas 5, 6 y 7 no se usan, ya que se restringen las travesías, a las que usan seguir el hijo isquierdo en primer instancia, ignorándose las restantes.

Travesia En Orden ( Inorder Traversal )

INORDER(T)

Empezar
Si T no es iguál a cero ...
- Llamar INORDER ( LCHILD(T) )
- Llamar DATA ( T )
- Llamar INORDER ( RCHILD(T) )
Terminar

Travesia Pre Orden ( Preorder Traversal )

PREORDER(T)

Empezar
Si T no es iguál a cero ...
- Llamar DATA ( T )
- Llamar PREORDER ( LCHILD(T) )
- Llamar PREORDER ( RCHILD(T) )
Terminar

Travesia Post Orden ( Postorder Traversal )

POSTORDER(T)

Empezar
Si T no es iguál a cero ...
- Llamar POSTORDER ( LCHILD(T) )
- Llamar POSTORDER ( RCHILD(T) )
- Llamar DATA ( T )
Terminar

Ejemplos

                    *---*
                    | + |
                    *---*
                     | |
              +------+ +------+
              |               |
            *---*           *---*
            | * |           | E |        Inorder   ----> A / B ** C * D + E
            *---*           *---*
             | |
          +--+ +--+
          |       |
        *---*   *---*
        | / |   | D |                    Preorder  ----> + * / A ** B C D E
        *---*   *---*
         | |
      +--+ +--+
      |       |
    *---*   *---*
    | A |   | **|                        Postorder ----> A B C ** / D * E +
    *---*   *---*
             | |
          +--+ +--+
          |       |
        *---*   *---*
        | B |   | C |
        *---*   *---*

                   Arbol 8

Nodos y Enlaces

Observar que en un árbol binario de n nodos, si atendemos solo a los enlaces hacia sus hijos, tenemos :

Enlaces = 2 * n

Enlaces Usados = n - 1

Enlaces Libres = ( 2 * n ) - ( n - 1 ) = 2 * n - n + 1 = n + 1

Clasificaciónes de Arboles Binarios

Arboles Binarios

Según la disposición de los nodos internos
- Arbol Binario Desordenado ( Arbol Binario )
- Arbol Binario Ordenado ( Arbol Binario de Búsqueda )
- Arbol Binario Forestado ( Arbol Binario de Arboledas )
Según la disposición de los nodos externos
- Arbol Binario Expandido ( Arbol Binario Expandido )
- Arbol Binario Ponderado ( Arbol Binario Ponderado )
- Arbol Binario Hilvanado ( Arbol Binario Hilvanado )

Arboles Binarios y Arboledas

Arboles
- Arboles Comunes
- Arboles Transformados
- Arboles Binarios
- Arboles M-Vias
Arboledas
- Arboledas Comunes
- Arboledas Binarias

Arboles Binarios Desordenados

Arboles Binarios Ordenados

Arboles Binarios Ordenados Desbalanceados
Arboles Binarios Ordenados Balanceados

Arboles Binarios Extendidos

Arboles Binarios Extendidos Comunes
Arboles Binarios Extendidos Ponderados