uoc.ei.tads
Class ArbreAVL.NodeAVL<EN>

java.lang.Object
  extended by uoc.ei.tads.ArbreBinariEncadenatImpl.NodeArbre<EN>
      extended by uoc.ei.tads.ArbreAVL.NodeAVL<EN>
All Implemented Interfaces:
java.io.Serializable, Posicio<EN>
Enclosing class:
ArbreAVL<E>

protected static class ArbreAVL.NodeAVL<EN>
extends ArbreBinariEncadenatImpl.NodeArbre<EN>

Classe que estén NodeArbre per a incorporar un atribut d'altura que permet comprovar i mantenir l'equilibri d'un arbre de nodes AVL.

See Also:
Serialized Form

Field Summary
protected  int altura
          Altura del node dins de l'arbre.
 
Fields inherited from class uoc.ei.tads.ArbreBinariEncadenatImpl.NodeArbre
element, fillDret, fillEsquerre
 
Constructor Summary
ArbreAVL.NodeAVL(EN elem)
          Constructor amb un paràmetre.
 
Method Summary
 void ajustarAltura()
          Mètode que actualitza l'altura del node.
 int balanceig()
          Mètode que comprova l'equilibri de l'arbre de nodes.
 void equilibrar()
          Mètode que restaura, si cal, l'equilibri de l'arbre de nodes després de cada inserció o supressió.
 int getAltura()
          Accessor de lectura de l'altura continguda al node.
protected  void rotarDD()
          Mètode que corregeix el desequilibri DD (dreta dreta).
protected  void rotarDE()
          Mètode protegit que corregeix el desequilibri DE (dreta esquerra).
protected  void rotarED()
          Mètode protegit que corregeix el desequilibri ED (esquerra dreta).
protected  void rotarEE()
          Mètode que corregeix el desequilibri EE (esquerra esquerra).
 void setAltura(int altura)
          Accessor d'escriptura de l'altura continguda al node.
 
Methods inherited from class uoc.ei.tads.ArbreBinariEncadenatImpl.NodeArbre
getElem, getFillDret, getFillEsquerre, nombreNodes, setElem, setFillDret, setFillEsquerre, 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 node dins de l'arbre. Per defecte val u (fulla).

Constructor Detail

ArbreAVL.NodeAVL

public ArbreAVL.NodeAVL(EN elem)
Constructor amb un paràmetre. Assigna el valor rebut a l'element del node pare i dóna valor null a les posicions filles. Delega en la superclasse. L'altura per defecte val u (fulla).

Parameters:
elem - valor de l'element que ha d'anar al node
Method Detail

setAltura

public void setAltura(int altura)
Accessor d'escriptura de l'altura continguda al node.

Parameters:
altura - nou valor de l'altura

getAltura

public int getAltura()
Accessor de lectura de l'altura continguda al node.

Returns:
altura del node

ajustarAltura

public void ajustarAltura()
Mètode que actualitza l'altura del node. Suma u (node pare) al valor de l'altura del seu fill més alt.


balanceig

public int balanceig()
Mètode que comprova l'equilibri de l'arbre de nodes.

Returns:
zero si els seus fills tenen la mateixa altura; negatiu si penja cap a la dreta; i positiu si el subarbre esquerre és el més alt

equilibrar

public void equilibrar()
Mètode que restaura, si cal, l'equilibri de l'arbre de nodes després de cada inserció o supressió. El factor d'equilibri ha d'estar entre -1 i 1. Es poden donar quatre tipus de desequilibri (EE, ED, DD i DE) segons el balanceig (a l'esquerra o a la dreta) de l'arbre i del subarbre corresponent.


rotarDD

protected void rotarDD()
Mètode que corregeix el desequilibri DD (dreta dreta). El node s'ha inserit en el subarbre dret del subarbre dret, o bé s'ha suprimit un node del subarbre esquerre en les mateixes circumstàncies (en un arbre balancejat cap a la dreta). És a dir, l'arbre ha crescut per (T2) o ha minvat per (T0). L'arrel B del subarbre dret passa a ser la nova arrel i conserva el seu fill dret, que amb aquest moviment queda a un nivell més a prop de l'arrel de l'arbre.
      A                                  B
    /   \                              /   \
  /       \                          /       \
 T0        B       ---------->      A        T2
         /   \                    /   \
       /       \                /       \
      T1       T2              T0       T1
 
L'antiga arrel A esdevé fill esquerre de B i conserva el seu subarbre esquerre. Finalment, l'anterior subarbre esquerre de B esdevé subarbre dret de l'antiga arrel A per a conservar la propietat d'ordenació dels arbres de cerca.


rotarDE

protected void rotarDE()
Mètode protegit que corregeix el desequilibri DE (dreta esquerra). El node s'ha inserit en el subarbre esquerre del subarbre dret, o bé s'ha suprimit un node del subarbre esquerra en les mateixes circumstàncies (en un arbre balancejat cap a la dreta). És a dir, l'arbre ha crescut per (C) o ha minvat per (T0).
      A       ----->        A
    /   \                 /   \
  /       \             /       \
 T0        B           T0        C        ----->        C
         /   \                 /   \                  /   \
       /       \             /       \              /       \
      C        T3           T1        B            A         B
     / \                             / \          / \       / \
    /   \                           /   \        /   \     /   \
   T1   T2                         T2   T3      T0   T1   T2   T3
 
Per a restaurar l'equilibri calen dues rotacions: primer es corregeix el desequilibri EE del subarbre dret i, a continuació, el desequilibri DD de l'arbre.

See Also:
rotarEE(), rotarDD()

rotarEE

protected void rotarEE()
Mètode que corregeix el desequilibri EE (esquerra esquerra). El procediment és simètric al cas del desequilibri DD.
            A                                  B
          /   \                              /   \
        /       \                          /       \
       B        T0       ---------->      T2        A
     /   \                                        /   \
   /       \                                    /       \
  T2       T1                                  T1       T0
 

See Also:
rotarDD()

rotarED

protected void rotarED()
Mètode protegit que corregeix el desequilibri ED (esquerra dreta). El procediment és simètric al cas del desequilibri 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()