uoc.ei.tads
Class ArbolAVL.NodoAVL<EN>

java.lang.Object
  extended by uoc.ei.tads.ArbolBinarioEncadenadoImpl.NodoArbol<EN>
      extended by uoc.ei.tads.ArbolAVL.NodoAVL<EN>
All Implemented Interfaces:
java.io.Serializable, Posicion<EN>
Enclosing class:
ArbolAVL<E>

protected static class ArbolAVL.NodoAVL<EN>
extends ArbolBinarioEncadenadoImpl.NodoArbol<EN>

Clase que extiende NodoArbol para incorporar un atributo de altura que permite comprobar y mantener el equilibrio de un arbol de nodos AVL.

See Also:
Serialized Form

Field Summary
protected  int altura
          Altura del nodo dentro de del arbol.
 
Fields inherited from class uoc.ei.tads.ArbolBinarioEncadenadoImpl.NodoArbol
elemento, hijoDerecho, hijoIzquierdo
 
Constructor Summary
ArbolAVL.NodoAVL(EN elem)
          Constructor con un parámetro.
 
Method Summary
 void ajustarAltura()
          Método que actualiza la altura del nodo.
 int balanceo()
          Método que comprueba el equilibrio del arbol de nodos.
 void equilibrar()
          Método que restaura, si es preciso, el equilibrio del arbol de nodos después de cada inserción o supresión.
 int getAltura()
          Accesor de lectura de la altura contenida al nodo.
protected  void rotarDD()
          Método que corrige el desequilibrio DD (derecha derecha).
protected  void rotarDE()
          Método protegido que corrige el desequilibrio DE (derecha izquierda).
protected  void rotarED()
          Método protegido que corrige el desequilibrio ED (izquierda derecha).
protected  void rotarEE()
          Método que corrige el desequilibrio EE (izquierda izquierda).
 void setAltura(int altura)
          Accesor de escritura de la altura contenida en el nodo.
 
Methods inherited from class uoc.ei.tads.ArbolBinarioEncadenadoImpl.NodoArbol
getElem, getHijoDerecho, getHijoIzquierdo, numNodos, setElem, setHijoDerecho, setHijoIzquierdo, toString
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

altura

protected int altura
Altura del nodo dentro de del arbol. Por defecto vale uno (hoja).

Constructor Detail

ArbolAVL.NodoAVL

public ArbolAVL.NodoAVL(EN elem)
Constructor con un parámetro. Asigna el valor recibo al elemento del nodo padre y da valor null a las posiciones hijas. Delega en la superclase. La altura por defecto vale uno (hoja).

Parameters:
elem - valor del elemento que debe ir al nodo
Method Detail

setAltura

public void setAltura(int altura)
Accesor de escritura de la altura contenida en el nodo.

Parameters:
altura - nuevo valor de la altura

getAltura

public int getAltura()
Accesor de lectura de la altura contenida al nodo.

Returns:
altura del nodo

ajustarAltura

public void ajustarAltura()
Método que actualiza la altura del nodo. Suma uno (nodo padre) al valor de la altura de su hijo más alto.


balanceo

public int balanceo()
Método que comprueba el equilibrio del arbol de nodos.

Returns:
cero si sus hijos tienen la misma altura; negativo si cuelga hacia la derecha; y positivo si el subárbol izquierdo es el más alto

equilibrar

public void equilibrar()
Método que restaura, si es preciso, el equilibrio del arbol de nodos después de cada inserción o supresión. El factor de equilibrio ha de estar entre -1 y 1. Se pueden dar cuatro tipo de desequilibrio (EE, ED, DD y DE) según el balanceo (a la izquierda o a la derecha) del arbol y del subárbol correspondiente.


rotarDD

protected void rotarDD()
Método que corrige el desequilibrio DD (derecha derecha). El nodo se ha insertado en el subárbol derecho del subárbol derecho, o bien se ha suprimido un nodo del subárbol izquierdo en las mismas circunstancias (en un arbol balanceado hacia la derecha). Es decir, el arbol ha crecido por (T2) o ha menguado por (T0). La raíz B del subárbol derecho pasa a ser la nueva raíz y conserva su hijo derecho, que con este movimiento queda en un nivel más cerca de la raíz del arbol.
      A                                  B
    /   \                              /   \
  /       \                          /       \
 T0        B       ---------->      A        T2
         /   \                    /   \
       /       \                /       \
      T1       T2              T0       T1
 
La antigua raíz A pasa a ser hijo izquierdo de B y conserva su subárbol izquierdo. Finalmente, el anterior subárbol izquierdo de B paso a ser subárbol derecho de la antigua raíz A para conservar la propiedad de ordenación de los árboles de busqueda.


rotarDE

protected void rotarDE()
Método protegido que corrige el desequilibrio DE (derecha izquierda). El nodo se ha insertado en el subárbol izquierdo del subárbol derecho, o bien se ha suprimido un nodo del subárbol izquierdo en las mismas circunstancias (en un arbol balanceado hacia la derecha). Es decir, el arbol ha crecido por (C) o ha menguado por (T0).
      A       ----->        A
    /   \                 /   \
  /       \             /       \
 T0        B           T0        C        ----->        C
         /   \                 /   \                  /   \
       /       \             /       \              /       \
      C        T3           T1        B            A         B
     / \                             / \          / \       / \
    /   \                           /   \        /   \     /   \
   T1   T2                         T2   T3      T0   T1   T2   T3
 
Para restaurar el equilibrio se necesitan dos rotaciones: primero se corrige el desequilibrio EE del subárbol derecho y, a continuación, el desequilibrio DD del arbol.

See Also:
rotarEE(), rotarDD()

rotarEE

protected void rotarEE()
Método que corrige el desequilibrio EE (izquierda izquierda). El procedimiento es simétrico al caso del desequilibrio DD.
            A                                  B
          /   \                              /   \
        /       \                          /       \
       B        T0       ---------->      T2        A
     /   \                                        /   \
   /       \                                    /       \
  T2       T1                                  T1       T0
 

See Also:
rotarDD()

rotarED

protected void rotarED()
Método protegido que corrige el desequilibrio ED (izquierda derecha). El procedimiento es simétrico al caso del desequilibrio DE.
            A        ----->        A
          /   \                  /   \
        /       \              /       \
       B        T0            C        T0    ----->     C
     /   \                  /   \                     /   \
   /       \              /       \                 /       \
  T3        C            B        T1               B         A
           / \          / \                       / \       / \
          /   \        /   \                     /   \     /   \
         T2   T1      T3   T2                   T3   T2   T1   T0
 

See Also:
rotarDE()