Estructura de Datos : Arboles Binarios Extendidos Ponderados

Definiciones

Un árbol binario extendido ponderado es un árbol binario extendido donde a cada nodo terminal se le ha asignado un peso determinado.

Terminología

Peso Nodo Externo ( Weight External Node ) El identificador asociado al nodo externo.

Longitud Paso Externo Ponderado ( Weighted External Path Length ) Es la sumatoria sobre los nodos externos, de la longitud del paso desde el nodo raíz a cada nodo externo, multiplicado por el peso del nodo externo. Sintetizaremos su nombre como WEPL.

Peso Nodo Interno ( Weight Internal Node ) No existe. Los nodos internos no se ponderan.

Ejemplos

                            *---*                                                    *---*
                            |   |                                                    |   |
                            *---*                                                    *---*
                             | |                                                      | |
                          +--+ +--+                                            +------+ +------+
                          |       |                                            |               |
                        *---*   *****                                        *---*           *---*
                        |   |   *15 *                                        |   |           |   |
                        *---*   *****                                        *---*           *---*
                         | |                                                  | |             | |
                      +--+ +--+                                            +--+ +--+       +--+ +--+
                      |       |                                            |       |       |       |
                    *---*   *****                                        *****   *****   *****   *****
                    |   |   * 5 *                                        * 2 *   * 4 *   * 5 *   *15 *
                    *---*   *****                                        *****   *****   *****   *****
                     | |
                  +--+ +--+
                  |       |
                *****   *****
                * 2 *   * 4 *
                *****   *****

          Arbol Binario Extendido Ponderado 1                          Arbol Binario Extendido Ponderado 2


      WEPL = 2 * 3 + 4 * 3 + 5 * 2 + 15 * 1 = 43                    WEPL = 2 * 2 + 4 * 2 + 5 * 2 + 15 * 2 = 52

Relaciones

Nodos

Los nodos se componen de tres campos :

    Nodo Interno                                 Nodo Externo

    *-------------------------*                  *-------------------------*
    | LCHILD | DATOS | RCHILD |                  | LCHILD | WEIGH | RCHILD |
    *-------------------------*                  *-------------------------*

Arbol Binario Extendido Ponderado de Mínima Longitud Paso Externo Ponderado

El algoritmo que nos lleva a la Mínima Longitud Paso Externo Ponderado es debido a D. Huffman, y lleva su nombre, y trabaja sobre un Arbol Binario Extendido Ponderado. Dado un conjunto de pesos q1, q2, ..., qn+1, hallar el árbol binario ponderado que haga mínimo el WEPL.

Veamos construcciones prelimares para el algoritmo :

Lista de arboles binarios extendidos ponderados
Es una lista que alberga, inicialmente, un conjunto de arboles binarios extendidos ponderados, de un solo nodo, nodo que lleva el peso de uno de los nodos externos. Luego, esta lista, se renueva por la eliminación de árboles y por el agregado de nuevos árboles, por accion del algoritmo.

Función para determinar el árbol binario extendido ponderado de mínimo peso en la lista
Esta función devuelve el árbol extendido binario ponderado de mínimo identificador en su nodo raiz, de todos los que estan almacenados en la lista.

Función de inserción de un árbol binario extendido ponderado en la lista
Esta función inserta un árbol binario extendido ponderado en la lista.

Entonces el algoritmo luce como sigue :

HUFFMAN(L, n)
- A partir de los identificadores ponderados construir la lista de nodos simples
- Ejecutar desde i = 1, hasta i = n - 1, haciendo i = i + 1 cada vuelta
  - Obtener un nodo
  - T apunta al nodo obtenido
  - LCHILD(T) <---- LEAST(L)
  - RCHILD(T) <---- LEAST(L)
  - WEIGHT(T) <---- WEIGHT(LCHILD(T)) + WEIGHT(RCHILD(T))
  - INSERT(L,T)
Terminar

Consideremos q1 = 2, q2 = 3, q3 = 5, q4 = 7, q5 = 9 y q6 = 13.

      *---*                      *---*                  *---*                               *---*
      | 5 |                      |10 |                  |16 |                               |23 |
      *---*                      *---*                  *---*                               *---*
       | |                        | |                    | |                                 | |
    +--+ +--+                  +--+ +--+              +--+ +--+                       +------+ +------+
    |       |                  |       |              |       |                       |               |
  *****   *****              *---*   *****          *****   *****                   *---*           *****
  * 2 *   * 3 *              | 5 |   * 5 *          * 7 *   * 9 *                   |10 |           *13 *
  *****   *****              *---*   *****          *****   *****                   *---*           *****
                              | |                                                    | |
                           +--+ +--+                                              +--+ +--+
                           |       |                                              |       |
                         *****   *****                                          +---+   *****
                         * 2 *   * 3 *                                          | 5 |   * 5 *
                         *****   *****                                          +---+   *****
                                                                                 | |
                                                                              +--+ +--+
                                                                              |       |
                                                                            *****   *****
                                                                            * 2 *   * 3 *
                                                                            *****   *****






                  *---*                                                      *---*                                                *---*
                  |39 |                                                      |   |                                                |   |
                  *---*                                                      *---*                                                *---*
                   | |                                                        | |                                                  | |
          +--------+ +--------+                                      +--------+ +--------+                                +--------+ +--------+
          |                   |                                      |                   |                                |                   |
        *---*               *---*                                  *---*               *---*                            *---*               *---*
        |16 |               |23 |                                  |   |               |   |                            |   |               |   |
        *---*               *---*                                  *---*               *---*                            *---*               *---*
         | |                 | |                                    | |                 | |                              | |                 | |
      +--+ +--+           +--+ +--+                              +--+ +--+           +--+ +--+                        +--+ +--+           +--+ +--+
      |       |           |       |                              |       |           |       |                        |       |           |       |
    *****   *****       *---*   *****                          *****   +---+       *---*   *****                    *---*   *****       *****   *---*
    * 7 *   * 9 *       |10 |   *13 *                          * 2 *   |   |       |   |   *13 *                    |   |   * 9 *       *13 *   |   |
    *****   *****       *---*   *****                          *****   +---+       *---*   *****                    *---*   *****       *****   *---*
                         | |                                            | |         | |                              | |                         | |
                      +--+ +--+                                       +-+ +-+     +-+ +-+                          +-+ +-+                     +-+ +-+
                      |       |                                       |     |     |     |                          |     |                     |     |
                    +---+   *****                                   ***** ***** ***** *****                      ***** *****                 ***** *****
                    | 5 |   * 5 *                                   * 3 * * 5 * * 7 * * 9 *                      * 2 * * 3 *                 * 5 * * 7 *
                    +---+   *****                                   ***** ***** ***** *****                      ***** *****                 ***** *****
                     | |
                  +--+ +--+
                  |       |
                *****   *****
                * 2 *   * 3 *
                *****   *****

WEPL = 2*4 + 3*4 + 5*3 + 13*2 + 7*2 + 9*2 =93           WEPL = 2*2 + 3*3 + 5*3 + 7*3 + 9*3 + 13*2 = 112     WEPL = 2*3 + 3*3 + 5*3 + 13*2 + 7*3 + 9*2 = 95

La longitud paso externo ponderado mejor que se puede obtener de un arbol completo o lleno es 95.

Identificadores y Rangos

                       v1=10  v2=30    v3=-45    v4=60         v5=95          v6=180
- infinito <-------------*------*--------*---------*-------------*--------------*---------------> + infinito
                         |      |        |         |             |              |
           <------------>|<---->|<------>|<------->|<----------->|<------------>|<-------------->
                rango    |rango | rango  |  rango  |    rango    |       rango  |      rango
                 r1      | r2   |  r2    |   r3    |     r5      |        r6    |       r7
                         |      |        |         |             |              |
                         V      V        V         V             V              V
                        ide    ide      ide       ide           ide            ide                 t>

Identificadores con probalidades conocidas

Dado n identificadores v1, v2, v3, ..., vi, ..., vn y sus probabilidades de búsqueda p1, p2, p3, ..., pi, ..., pn, en un tiempo suficientemente importante insumen un costo de búsqueda igual a la sumatoria, variando i desde 1 a n de los sumandos

level(vi) * pi

El objetivo debería ser minimizar la expresión del párrafo anterior.

Identificadores y Rangos con probalidades conocidas

Dado n identificadores v1, v2, v3, ..., vi, ..., vn y sus probabilidades de búsqueda p1, p2, p3, ..., pi, ..., pn, y los rangos r1, r2, r3, ..., ri, ..., rn, rn+1 y sus probalidades de falla q1, q2, q3, ..., qi, ..., qn, qn+1, en un tiempo suficientemente importante insumen un costo de búsqueda igual a la sumatoria, variando i desde 1 a n de los sumandos

level(vi) * pi

qi * ( level(ri) - 1 )

El objetivo debería ser minimizar la expresión del párrafo anterior.