Estructura de Datos : Arboles Binarios Extendidos - Fundamentos

Definiciones

• Un árbol binario extendido es un árbol binario al que se le han agregado nodos terminales donde existian enlaces nulos.
• Un nodo de un árbol binario extendido puede tener 0 o 2 hijos. Si tiene 0 hijos es un nodo externo. Si tiene 2 hijos es un nodo interno.
• Un nodo interno de un árbol binario extendido puede tener por hijos, 2 nodos internos, 1 nodo interno y 1 nodo externo o 2 nodos externos. Un nodo externo de un árbol binario extendido no tiene hijos.

Terminología

1. Nodo Interno ( Internal Node ) Los n nodos originales del árbol binario.
2. Nodo Externo ( External Node ) Los n + 1 nodos agregados y que no son parte del árbol binario original. Estos nodos reciben también el nombre de Nodo de Falla.
3. Paso Interno ( Internal Path ) El paso que va desde el nodo raíz al nodo interno específico.
4. Paso Externo ( External Path ) El paso que va desde el nodo raíz al nodo externo específico.
5. Longitud Paso Interno ( Internal Path Length ) La cantidad de enlaces transitados en un paso interno específico.
6. Longitud Paso Externo ( External Path Length ) La cantidad de enlaces transitados en un paso externo específico.
7. Longitud Pasos Internos ( Internals Paths Length ) La sumatoria de todas las longitudes de los pasos internos del árbol binario extendido.
8. Longitud Pasos Externos ( Externals Paths Length ) La sumatoria de todas las longitudes de los pasos externos del árbol binario extendido.
9. Longitud Pasos Internos Máxima ( Maximum Internals Paths Length ) La longitud pasos internos de un árbol binario extendido sesgado.
10. Longitud Pasos Externos Máxima ( Maximum Externals Paths Length ) La longitud pasos externos de un árbol binario extendido sesgado.
11. Longitud Pasos Internos Mínima ( Minimum Internals Paths Length ) La longitud pasos internos de un árbol binario extendido completo o lleno.
12. Longitud Pasos Externos Mínima ( Minimum Externals Paths Length ) La longitud pasos externos de un árbol binario extendido completo o lleno.

Ejemplos

                    *---*                                                  *---*
                    |   |                                                  |   |
                    *---*                                                  *---*
                     | |                                                    | |
              +------+ +------+                                    +--------+ +--------+
              |               |                                    |                   |
            *---*           *---*                                *---*               *---*
            |   |           |   |                                |   |               |   |
            *---*           *---*                                *---*               *---*
             | |             | |                                  | |                 | |
          +--+ +--+       +--+ +--+                            +--+ +--+       +------+ +------+
          |       |       |       |                            |       |       |               |
        *****   *****   *---*   *****                        *****   *****   *---*           *---*
        *   *   *   *   |   |   *   *                        *   *   *   *   |   |           |   |
        *****   *****   *---*   *****                        *****   *****   *---*           *---*
                         | |                                                  | |             | |
                      +--+ +--+                                            +--+ +--+       +--+ +--+
                      |       |                                            |       |       |       |
                    *---*   *****                                        *****   *****   *****   *****
                    |   |   *   *                                        *   *   *   *   *   *   *   *
                    *---*   *****                                        *****   *****   *****   *****
                     | |
                  +--+ +--+
                  |       |
                *****   *****
                *   *   *   *
                *****   *****

          Arbol Binario Extendido 1                                  Arbol Binario Extendido 2


         IPL = 0 + 1 + 1 + 2 + 3 = 7                                 IPL = 0 + 1 + 1 + 2 + 2 = 6

      EPL = 2 + 2 + 4 + 4 + 3 + 2 = 17                            EPL = 2 + 2 + 3 + 3 + 3 + 3 = 16

Nodos

La misma representación de nodos usada para árboles binarios es válida para árboles binarios extendidos y no es necesario un campo que indique si se trata de un nodo interno o externo, ya que los enlaces de los nodos internos son no nulos y los enlaces de los nodos externos son nulos, oficiando de indicador del tipo de nodo.

                 Nodo Interno                              Nodo Externo

          *------------------------*                *------------------------*
          | LCHILD | DATA | RCHILD |                |    0   | DATA |   0    |
          *------------------------*                *------------------------*

              1 Nodo - 3 Campos                         1 Nodo - 3 Campos

Relaciones

1. Siempre EPL = IPL + 2 * n
2. Siempre IPL y EPL son máximo y mínimo simultaneamente
3. Imax es la sumatoria de i = 0 hasta n-1, 0 + 1 + 2 + ... + i + ... + (n-1), lo que es igual a n(n-1)/2, lo que corresponde a un árbol sesgado.
4. Imin se obtiene cuando los nodos están lo más cerca del nodo raíz, o sea, árboles completos o llenos, donde IPL es 1 * 0 + 2 * 1 + 4 * 2 + 8 * 3 + ..., lo que permite ser resumido como la sumatoria de i <= k hasta k <= n del piso de log2 k, lo que lleva a una relación O(n log2 n).

Valores y Rangos

                                       q1=-20    q2=+60                       q1=+320
- infinito <-----------------------------*---------*----------------------------*---------------> + infinito
                                         |         |                            |
           <---------------------------->|<------->|<-------------------------->|<-------------->
                        rango            |  rango  |            rango           |      rango
                         de              |   de    |             de             |       de
                   -infinito a -21       |-19 a +59|          +61 a +319        |+321 a +infinito
                                         |         |                            |
                                         V         V                            V
                                       valor     valor                        valor
                                        -20       +60                         +320