Estructura de Datos : Arboles Binarios Hilvanados ( Threaded Binary Trees )

Definiciones

Un árbol binario en su representación enlazada tiene más enlaces nulos que enlaces utilizados o pointers. Si el árbol binario tiene n nodos, existen 2 * n enlaces, de los cuales n + 1 con enlaces nulos y n - 1 son pointers. A. J. Perlis y C. Thornton propusieron una estructura de datos que utiliza los enlaces nulo, a los que llamaron threads, para que apunten a otros nodos del árbol, haciendo el recorrido inorder del árbol más eficiente.

Un árbol binario hilvanado es aquel que tiene reemplazados sus enlaces nulos por threads, tal que :

Si RCHILD(P) es normalmente 0, se reemplaza por un pointer al nodo que sería visitado despues de P, en el recorrido inorder del árbol
Si LCHILD(P) es normalmente 0, se reemplaza por un pointer al nodo que sería visitado antes de P, en el recorrido inorder del árbol

En un árbol binario hilvanado existen dos campos de bits extras, para señalar si los enlaces de un nodo son pointers o threads :

LBIT(P) = 1 si LCHILD(P) is un pointer
LBIT(P) = 0 si LCHILD(P) es una thread
RBIT(P) = 1 si RCHILD(P) is un pointer
RBIT(P) = 0 si RCHILD(P) es una thread

Nodos

   *--------------------------------------*
   | LBIT | LCHILD | DATA | RCHILD | RBIT |
   *--------------------------------------*

              1 Nodo - 5 Campos

Ejemplos

 *---* | A | *---* | | +------+ +------+ |               | *---*           *---* | B |           | C | *---*           *---* | |             | | +--+ +--+       +--+ +--+ |       |       |       | *---*   *---*   *---*   *---* | D |   | E |   | F |   | G | *---*   *---*   *---*   *---* | | +--+ +--+ |       | *---*   *---* | H |   | I | *---*   *---*

Nodos   = 9 Pointer = 8 Nulos   = 10

Arbol 1

El Arbol 1 es un árbol Observar que la thread no apuntan a ningún donde comenzar a navegar la terminación de la navegación. La estructura de datos de un nodo cabecera. *-----* | A | *-----* |A A| +---------+. .+---------+ | . . | *-----* . . *-----* | B | . . | C | A *-----* . . *-----* . |A A| . . |A A| . +---+. .+---+ . . +---+. .+---+ . | . . | . . | . . | . *-----* . . *-----* . . *-----* . . *-----* . A | D | . ..| E |.. ..| F |.. ..| G |..... . *-----* . *-----* *-----* *-----* . |A A| ....... . +---+. .+---+ . . | . . | . . *-----* . . *-----* . .....| H |.. ..| I |.. *-----* *-----* Nodos = 9 Pointer = 8 Threads = 10 Arbol 2 binario y el Arbol 2 es un árbol binario hilvanado. isquierda del nodo H y la thread derecha del nodo G nodo específico. La thread del nodo H indicaría el nodo el árbol inorder y la thread del nodo G indicaría árboles binarios hilvanados se consolida con el uso

Nodo Cabecera

   *--------------------------------------*                           *--------------------------------------*
   | LBIT | LCHILD | DATA | RCHILD | RBIT |                      +--->|   0  |    *   |  --  |   *    |  0   |<---+
   *--------------------------------------*                      |    *-----------|--------------|-----------*    |
                                                                 |                |              |                |
                                                                 +----------------+              +----------------+
                  Nodo Comun                                                       Nodo  Cabecera

Terminología

Arbol Binario Hilvandado ( Threaded BTree )

Hilvan ( Thread )

Puntero ( Pointer )

Enlace Nulo ( Null Link )

Representacion en Memoria de un Arbol Binario Hilvanado

                                                     *---------------------*
                                              T ---> | 1 | * |  -  | * | 1 |
                                                     *-----|---------|-----*<----+
                                                           |         |           |
                                                           +----+    +-----------+
                                                                |
                                                                V
                                                     *---------------------*
                                                     | 1 | * |  A  | * | 1 |
                                                     *-----|---------|-----*
                                      +--------------------+         +--------------------+
                                      V                                                   V
                           *---------------------*                             *---------------------*
                           | 1 | * |  -  | * | 1 |                             | 1 | * |  C  | * | 1 |
                           *---------------|-----*                             *-----|---------|-----*
                         +-----+             +-----+                         +-------+         +-------+
                         V                         V                         V                         V
              *---------------------*   *---------------------*   *---------------------*   *---------------------*
              | 1 | * |  D  | * | 1 |   | 0 | # |  E  | # | 0 |   | 0 | # |  F  | # | 0 |   | 0 | # |  G  | # | 0 |
              *-----|---------|-----*   *-----.---------.-----*   *-----.---------.-----*   *-----.---------.-----*
            +-------+         +-------+       .         .               .         .               .         .
            V                         V
 *---------------------*   *---------------------*
 | 0 | # |  H  | # | 0 |   | 0 | # |  I  | # | 1 |
 *-----.---------.-----*   *-----.---------.-----*
       .         .               .         .

                                                             Arbol 3

Procedimientos de Arboles Binarios Hilvanados

Sucesor de X en un arbol binario hilvanado

INSUC(X)

Empezar
S <--- RCHILD(X)
Si RBIT(X) iguál a uno ...
- Mientras LBIT(S) igual a uno
  - S <--- LCHILD(S)
Retornar S

Travesia en Orden ( Inorder Traversal )

TINORDER(T)

Empezar
HEAD <---- T
Loop para siempre
- T <---- INSUC(T)
- Si T = HEAD Terminar
- Imprimir(DATA(T))
Terminar