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

Definiciones

• Un árbol vacio es un árbol binario de búsqueda de altura balanceada. Si T no es un árbol binario de búsqueda vacio y tiene un subárbol isquierdo Tl y un subárbol derecho Tr, T es un árbol binario de búsqueda de altura balanceada sí y solo sí Tl y Tr son árboles binarios de búsqueda de altura balanceada y el valor absoluto de hl - hr es menor o igual a 1, donde hl y hr son las alturas de Tl y Tr respectivamente.
• El factor de balance, BF(T), de un nodo T en un árbol binario es definido ser hl - hr, donde hl y hr son las alturas de los subárboles isquierdo y derecho de T.
• Los árboles binarios de búsqueda de altura balanceada se los conoce también como AVL trees, en honor a los que propusieron su algorítmo de construcción, Adelson, Velskii y Landis en 1962.
• En cualquier nodo de un AVL tree, el factor de balance BF(T), debe ser -1, 0 ó 1.

Balanceo

   *---*
   | 0 |
   |Mar|
   *---*

   *---*
   |-1 |
   |Mar|
   *---*
      |
      +----+
           |
         *---*
         | 0 |
         |May|
         *---*

   *---*                     *---*
   |-2 |                     | 0 |
   |Mar|                     |May|
   *---*                     *---*
      |                       | |
      +----+             +----+ +----+
           |             |           |
         *---*         *---*       *---*
         |-1 |         | 0 |       | 0 |
         |May|         |Mar|       |Nov|
         *---*         *---*       *---*
           |
           +----+
                |
              *---*
              | 0 |
              |Nov|
              *---*

               *---*
               |+1 |
               |May|
               *---*
                | |
           +----+ +----+
           |           |
         *---*       *---*
         |+1 |       | 0 |
         |Mar|       |Nov|
         *---*       *---*
          |
     +----+
     |
   *---*
   | 0 |
   |Aug|
   *---*

                      *---*                               *---*
                      |+2 |                               |+1 |
                      |May|                               |May|
                      *---*                               *---*
                       | |                                 | |
                  +----+ +----+                       +----+ +----+
                  |           |                       |           |
                *---*       *---*                   *---*       *---*
                |+2 |       | 0 |                   | 0 |       | 0 |
                |Mar|       |Nov|                   |Aug|       |Nov|
                *---*       *---*                   *---*       *---*
                 |                                   | |
            +----+                              +----+ +----+
            |                                   |           |
          *---*                               *---*       *---*
          |+1 |                               | 0 |       | 0 |
          |Aug|                               |Apr|       |Mar|
          *---*                               *---*       *---*
            |
       +----+
       |
     *---*
     | 0 |
     |Apr|
     *---*

                 *---*                                    *---*
                 |+2 |                                    | 0 |
                 |May|                                    |Mar|
                 *---*                                    *---*
                  | |                                      | |
             +----+ +----+                            +----+ +----+
             |           |                            |           |
           *---*       *---*                        *---*       *---*
           |-1 |       | 0 |                        | 0 |       |-1 |
           |Aug|       |Nov|                        |Aug|       |May|
           *---*       *---*                        *---*       *---*
            | |                                      | |          |
       +----+ +----+                            +----+ +----+     +----+
       |           |                            |           |          |
     *---*       *---*                        *---*       *---*      *---*
     | 0 |       |+1 |                        | 0 |       | 0 |      | 0 |
     |Apr|       |Mar|                        |Apr|       |Jan|      |Nov|
     *---*       *---*                        *---*       *---*      *---*
                   |
              +----+
              |
            *---*
            | 0 |
            |Jan|
            *---*

               *---*
               |+1 |
               |Mar|
               *---*
                | |
           +----+ +----+
           |           |
         *---*       *---*
         |-1 |       |-1 |
         |Aug|       |May|
         *---*       *---*
          | |          |
     +----+ +----+     +----+
     |           |          |
   *---*       *---*      *---*
   | 0 |       |+1 |      | 0 |
   |Apr|       |Jan|      |Nov|
   *---*       *---*      *---*
                 |
            +----+
            |
          *---*
          | 0 |
          |Dec|
          *---*

               *---*
               |+1 |
               |Mar|
               *---*
                | |
           +----+ +----+
           |           |
         *---*       *---*
         |-1 |       |-1 |
         |Aug|       |May|
         *---*       *---*
          | |          |
     +----+ +----+     +----+
     |           |          |
   *---*       *---*      *---*
   | 0 |       | 0 |      | 0 |
   |Apr|       |Jan|      |Nov|
   *---*       *---*      *---*
                | |
           +----+ +----+
           |           |
         *---*       *---*
         | 0 |       | 0 |
         |Dec|       |Jul|
         *---*       *---*

               *---*                                  *---*
               |+2 |                                  |+1 |
               |Mar|                                  |Mar|
               *---*                                  *---*
                | |                                    | |
           +----+ +----+                          +----+ +----+
           |           |                          |           |
         *---*       *---*                      *---*       *---*
         |-2 |       |-1 |                      | 0 |       |-1 |
         |Aug|       |May|                      |Dec|       |May|
         *---*       *---*                      *---*       *---*
          | |          |                         | |          |
     +----+ +----+     +----+               +----+ +----+     +----+
     |           |          |               |           |          |
   *---*       *---*      *---*           *---*       *---*      *---*
   | 0 |       |+1 |      | 0 |           |+1 |       | 0 |      | 0 |
   |Apr|       |Jan|      |Nov|           |Aug|       |Jan|      |Nov|
   *---*       *---*      *---*           *---*       *---*      *---*
                | |                         |          | |
           +----+ +----+               +----+     +----+ +----+
           |           |               |          |           |
         *---*       *---*           *---*      *---*       *---*
         |-1 |       | 0 |           | 0 |      | 0 |       | 0 |
         |Dec|       |Jul|           |Apr|      |Feb|       |Jul|
         *---*       *---*           *---*      *---*       *---*
           |
           +----+
                |
              *---*
              | 0 |
              |Feb|
              *---*

                    *---*                                              *---*
                    |+2 |                                              | 0 |
                    |Mar|                                              |Jan|
                    *---*                                              *---*
                     | |                                                | |
                +----+ +----+                                  +--------+ +--------+
                |           |                                  |                   |
              *---*       *---*                              *---*               *---*
              |-1 |       |-1 |                              |+1 |               | 0 |
              |Dec|       |May|                              |Dec|               |Mar|
              *---*       *---*                              *---*               *---*
               | |          |                                 | |                 | |
          +----+ +----+     +----+                       +----+ +----+       +----+ +----+
          |           |          |                       |           |       |           |
        *---*       *---*      *---*                   *---*       *---*   *---*       *---*
        |+1 |       |-1 |      | 0 |                   |+1 |       | 0 |   |-1 |       |-1 |
        |Aug|       |Jan|      |Nov|                   |Aug|       |Feb|   |Jul|       |May|
        *---*       *---*      *---*                   *---*       *---*   *---*       *---*
          |          | |                                 |                   |           |
     +----+     +----+ +----+                       +----+                   +----+      +----+
     |          |           |                       |                             |           |
   *---*      *---*       *---*                   *---*                         *---*       *---*
   | 0 |      | 0 |       |-1 |                   | 0 |                         | 0 |       | 0 |
   |Apr|      |Feb|       |Jul|                   |Apr|                         |Jun|       |Nov|
   *---*      *---*       *---*                   *---*                         *---*       *---*
                            |
                            +----+
                                 |
                               *---*
                               | 0 |
                               |Jun|
                               *---*

                        *---*                                                             *---*
                        |-1 |                                                             | 0 |
                        |Jan|                                                             |Jan|
                        *---*                                                             *---*
                         | |                                                               | |
                +--------+ +--------+                                            +---------+ +---------+
                |                   |                                            |                     |
              *---*               *---*                                        *---*                 *---*
              |+1 |               |-1 |                                        |+1 |                 | 0 |
              |Dec|               |Mar|                                        |Dec|                 |Mar|
              *---*               *---*                                        *---*                 *---*
               | |                 | |                                          | |                   | |
          +----+ +----+       +----+ +----+                                +----+ +----+      +-------+ +-------+
          |           |       |           |                                |           |      |                 |
        *---*       *---*   *---*       *---*                            *---*       *---*  *---*             *---*
        |+1 |       | 0 |   |-1 |       |-2 |                            |+1 |       |+1 |  |-1 |             | 0 |
        |Aug|       |Feb|   |Jul|       |May|                            |Aug|       |Feb|  |Jul|             |Nov|
        *---*       *---*   *---*       *---*                            *---*       *---*  *---*             *---*
          |                   |           |                                |                  |                | |
     +----+                   +----+      +----+                      +----+                  +----+      +----+ +----+
     |                             |           |                      |                            |      |           |
   *---*                         *---*       *---*                  *---*                        *---*  *---*       *---*
   | 0 |                         | 0 |       |-1 |                  | 0 |                        | 0 |  | 0 |       | 0 |
   |Apr|                         |Jun|       |Nov|                  |Apr|                        |Jun|  |May|       |Oct|
   *---*                         *---*       *---*                  *---*                        *---*  *---*       *---*
                                               |
                                               +----+
                                                    |
                                                  *---*
                                                  | 0 |
                                                  |Oct|
                                                  *---*

                         *---*
                         |-1 |
                         |Jan|
                         *---*
                          | |
                +---------+ +---------+
                |                     |
              *---*                 *---*
              |+1 |                 |-1 |
              |Dec|                 |Mar|
              *---*                 *---*
               | |                   | |
          +----+ +----+      +-------+ +-------+
          |           |      |                 |
        *---*       *---*  *---*             *---*
        |+1 |       | 0 |  |-1 |             |-1 |
        |Aug|       |Feb|  |Jul|             |Nov|
        *---*       *---*  *---*             *---*
          |                  |                | |
     +----+                  +----+      +----+ +----+
     |                            |      |           |
   *---*                        *---*  *---*       *---*
   | 0 |                        | 0 |  | 0 |       |-1 |
   |Apr|                        |Jun|  |May|       |Oct|
   *---*                        *---*  *---*       *---*
                                                     |
                                                     +----+
                                                          |
                                                        *---*
                                                        | 0 |
                                                        |Sep|
                                                        *---*
        *-------------*
        | Mes |       |
        *-------------*
        | Jan |   1   |
        | Feb |   3   |
        | Mar |   2   |
        | Apr |   4   |
        | May |   4   |
        | Jun |   4   |
        | Jul |   3   |
        | Aug |   3   |
        | Sep |   5   |
        | Oct |   4   |
        | Nov |   3   |
        | Dec |   2   |
        *-------------*
        | Tot |  38   |
        *-------------*
        | Pro |   3,1 |
        *-------------*