Estructura de Datos : Arboles Binarios de Búsqueda - Fundamentos

Definiciones

Un árbol binario de búsqueda T es un árbol binario, que está vacio o cada nodo del árbol contiene un identificador tal que :

Todos los identificadores en el subárbol isquierdo de T son menores que el identificador en el nodo raíz de T.
Todos los identificadores en el subárbol derecho de T son mayores que el identificador en el nodo raíz de T.
El subárbol isquierdo de T y el subárbol derecho de T son también árboles binarios de búsqueda.

                                                 *-------*
     T --->                               T ---> |   X   | nodo raiz
                                                 *-------*
                                                    * *
                                                   /| |\            X = Identificador
                                                  / | | \
                                                 /  | |  \
                             subarbol isquierdo /   | |   \ subarbol derecho
                                               /    | |    \
                                              /     | |     \
                                             /      | |      \
                                            /       | |       \
                                           *--------* *--------*

Terminología

Arbol Binario de Búsqueda ( Binary Search Tree ) Ver las definiciones. Usaremos la notación abreviada BST para referirnos a un árbol binario de búsqueda.

Identificador ( Identifier ) Los nodos de un BST pueden contener varios campos de datos, pero uno de ellos es designado como identificador y es usado para determinar la posición del nodo en el BST.

Númericamente Mayor o Menor ( Numerically Less or Greater ) La determinación de cúal es el mayor o menor es el órden numérico.

Alfabeticamente Mayor o Menor ( Alphabetically Less or Greater ) La determinación de cúal es el mayor o menor es el órden alfabético.

Comparablemente Mayor o Menor ( Comparablelly Less or Greater ) La determinación de cúal es el mayor o menor es establecida por un algoritmo.

Ejemplos

            *-------*                            *-------*                                     *-------*
     T ---> |  if   |                     T ---> |  if   |                              T ---> |  if   |
            *-------*                            *-------*                                     *-------*
               | |                                  | |                                           | |
     +---------+ +---------+              +---------+ +---------+                           +-----+ +-----+
     |                     |              |                     |                           |             |
 *-------*             *-------*      *-------*             *-------*                   *-------*     *-------*
 |  for  |             | while |      |  for  |             |repeat |                   |  do   |     | stop  |
 *-------*             *-------*      *-------*             *-------*                   *-------*     *-------*
                           |                                   | |
                       +---+                             +-----+ +-----+
                       |                                 |             |
                   *-------*                         *-------*     *-------*
                   |repeat |                         | loop  |     | while |
                   *-------*                         *-------*     *-------*
                      |
                  +---+
                  |
              *-------*
              | loop  |
              *-------*

              BST 1                                BST 2                                         BST 3


                                    *-------*
                             T ---> |  33   |
                                    *-------*
                                       | |
                    +------------------+ +------------------+
                    |                                       |
                *-------*                               *-------*
                |  15   |                               |  44   |
                *-------*                               *-------*
                   | |                                     | |
          +--------+ +--------+                   +--------+ +--------+
          |                   |                   |                   |
      *-------*           *-------*           *-------*           *-------*
      |  10   |           |  22   |           |  36   |           |  80   |
      *-------*           *-------*           *-------*           *-------*
         | |                 | |                 | |                 | |
     +---+ +---+         +---+ +---+         +---+ +---+         +---+ +---+
     |         |         |         |         |         |         |         |
 *-------* *-------* *-------* *-------* *-------* *-------* *-------* *-------*
 |   7   | |  13   | |  19   | |  29   | |  35   | |  37   | |  67   | |  103  |
 *-------* *-------* *-------* *-------* *-------* *-------* *-------* *-------*

                                      BST 4

Observar que para un determinado conjunto de identificadores existen varios BST posibles, como lo muestran los BST 1 y BST 2. Los BST 1, BST 2 y BST 3 se basan en el órden alfabético y el BST 4 sigue el órden numérico.

Procedimientos de Búsqueda

Construido un árbol binario de búsqueda según la definición dada, el algoritmo más importante es el que determina si un determinado identificador está o nó en el árbol. En caso afirmativo el algoritmo retorna el nodo donde está alojado el identificador que se busca. En caso negativo devuelve un cero.

El procedimiento que sigue buscará en el árbol binario de búsqueda T por el identificador X, y retorna i = 0 si X no está en el árbol de búsqueda T, y si X está en el árbol de búsqueda T retorna el nodo donde el identificador existe. Observar que T y X son argumentos de entrada mientras que i es un argumento de salida.

SEARCH(T, X, i)

Empezar
i <---- T
Mientras i sea distinto de cero ...
- El en caso de ...
  - X sea menor que el identificador de i, X < IDENT(i) ...
    - i <---- LCHILD(i) ( Continua la búsqueda en la rama isquierda )
  - X sea igual que el identificador de i, X = IDENT(i) ...
    - Terminar ( El identificador fué hallado y retorna en i el nodo donde existe X )
  - X sea mayor que el identificador de i, X > IDENT(i) ...
    - i <---- RCHILD(i) ( Continua la búsqueda en la rama derecha )
Terminar ( El identificador no fué hallado y retorna en i 0, ya que se llegó a un enlace sin hijo, fin de la búsqueda )

Procedimientos de Inserción

El procedimiento que sigue insertará el identificador X en el árbol binario de búsqueda T. Si X existe en T, no se modifica el árbol de búsqueda T y en j se retorna el nodo donde existe X. Si X no existe en T, se crea un nodo, se le almacena el identificador X y se inserta en el árbol de búsqueda T en el lugar apropiado, retornando el nodo creado o insertado. Observar que T y X son argumentos de entrada mientras que j es un argumento de salida.

BST(T, X, j)

Empezar
p <---- 0 ( p seguirá a j a lo largo del algoritmo, un nivel más alto )
j <---- T
Mientras j sea distinto de cero ...
- El en caso de ...
  - X sea menor que el identificador de j, X < IDENT(j) ...
    - p <---- j ( p queda en el nivel superior a j )
    - j <---- LCHILD(j) ( Continua la búsqueda en la rama isquierda )
  - X sea igual que el identificador de j, X = IDENT(j) ...
    - Terminar ( El identificador fue hallado y retorna en j el nodo donde existe )
  - X sea mayor que el identificador de j, X > IDENT(j) ...
    - p <---- j ( p queda en el nivel superior a j )
    - j <---- RCHILD(j) ( Continua la búsqueda en la rama derecha )
( Si se llego a este punto, X no existe en T, j tiene un 0 y p se quedó en el último nodo visitado )
Obtener un nodo libre
j <---- nodo libre
IDENT(j) <---- X
LCHILD(j) <---- 0
RCHILD(j) <---- 0
El en caso de ...
- T = 0
- X < IDENT(p)
  - LCHILD(p) <---- j ( Lo inserto como hijo isquierdo del último nodo visitado )
- X > IDENT(p)
  - RCHILD(p) <---- j ( Lo inserto como hijo derecho del último nodo visitado )
Terminar ( Retorna en j el nodo creado e insertado )

Veamos ahora como este algoritmo crea BSTs distintos, según el órden de inserción en el BST de los identificadores. Tomemos, por ejemplo, los meses del año e insertémoslos según los siguientes órdenes :

BST 5 ------> Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov y Dec
BST 6 ------> Jul, Feb, May, Aug, Dec, Mar, Oct, Apr, Jan, Jun, Sep y Nov
BST 7 ------> Apr, Aug, Dec, Feb, Jan, Jul, Jun, Mar, May, Nov, Oct y Sep

                      *---*                                                  *---*                                                  *---*
               T ---> |Jan|                                           T ---> |Jul|                                           T ---> |Apr|
                      *---*                                                  *---*                                                  *---*
                       | |                                                    | |                                                      |
            +----------+ +----------+                              +----------+ +----------+                                           +--+
            |                       |                              |                       |                                              |
          *---*                   *---*                          *---*                   *---*                                          *---*
          |Feb|                   |Mar|                          |Feb|                   |May|                                          |Aug|
          *---*                   *---*                          *---*                   *---*                                          *---*
           |                       | |                            | |                     | |                                              |
      +----+                  +----+ +----+                  +----+ +----+           +----+ +----+                                         +--+
      |                       |           |                  |           |           |           |                                            |
    *---*                   *---*       *---*              *---*       *---*       *---*       *---*                                        *---*
    |Apr|                   |Jun|       |May|              |Aug|       |Jan|       |Mar|       |Oct|                                        |Dec|
    *---*                   *---*       *---*              *---*       *---*       *---*       *---*                                        *---*
       |                     |             |                | |                     |           | |                                            .
       +-+                 +-+             +-+            +-+ +-+                 +-+         +-+ +-+                                          .
         |                 |                 |            |     |                 |           |     |                                          .
       *---*             *---*             *---*        *---* *---*             *---*       *---* *---*                                        .
       |Aug|             |Jul|             |Sep|        |Apr| |Dec|             |Jun|       |Nov| |Sep|                                        ........
       *---*             *---*             *---*        *---* *---*             *---*       *---* *---*                                               .
          |                                 |                                                                                                         .
          +-+                             +-+                                                                                                         .
            |                             |                                                                                                           .
          *---*                         *---*                                                                                                       *---*
          |Dec|                         |Oct|                                                                                                       |Oct|
          *---*                         *---*                                                                                                       *---*
                                         |                                                                                                             |
                                       +-+                                                                                                             +--+
                                       |                                                                                                                  |
                                     *---*                                                                                                              *---*
                                     |Nov|                                                                                                              |Sep|
                                     *---*                                                                                                              *---*

                      BST 5                                                  BST 6                                                               BST 7

Costo de Búsqueda

Analizaremos el costo de búsqueda como el promedio de buscar todos El costo de búsqueda de un identificador número de comparaciones que deben al nivel del nodo que contiene Consideremos los ejemplos de los

 *-----------------------------* | Mes | BST 5 | BST 6 | BST 7 | *-----------------------------* | Jan |   1   |   3   |   5   | | Feb |   2   |   2   |   4   | | Mar |   2   |   3   |   8   | | Apr |   3   |   4   |   1   | | May |   3   |   2   |   9   | | Jun |   3   |   4   |   7   | | Jul |   4   |   1   |   6   | | Aug |   4   |   3   |   2   | | Sep |   4   |   4   |  12   | | Oct |   5   |   3   |  11   | | Nov |   6   |   4   |  10   | | Dec |   5   |   4   |   3   | *-----------------------------* | Tot |  42   |  37   |  78   | *-----------------------------* | Nod |  12   |  12   |  12   | *-----------------------------* | Pro |   3,5 |   3,0 |   6,5 | *-----------------------------* | Max |   6   |   4   |  12   | *-----------------------------*

Los árboles binarios de búsqueda costo de búsqueda promedio para de un árbol binario de búsqueda T los identificadores presente en T. en particular está dado por el hacerse para hallarlo, y en este caso es igual el identificador. meses del año. *-----------------------------* | Mes | BST 1 | BST 2 | | *-----------------------------* | if | 1 | 1 | | | for | 2 | 2 | | | whi | 2 | 2 | | | rep | 3 | 3 | | | loo | 4 | 3 | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | *-----------------------------* | Tot | 12 | 11 | | *-----------------------------* | Nod | 5 | 5 | | *-----------------------------* | Pro | 2,4 | 2,2 | | *-----------------------------* | Max | 4 | 3 | | *-----------------------------* completos o llenos son los de menor n nodos.

Clasificacion

Observar que en un árbol binario de búsqueda, si se lo recorre in order, devuelve ordenados, clasificados, a los identificadores insertados. El algoritmo in order, aplicado sobre un árbol binario de búsqueda, se convierte en un algoritmo de clasificación ( sorting algoritmo ).