|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectuoc.ei.tads.ArbreBinariEncadenatImpl.NodeArbre<EN>
uoc.ei.tads.ArbreAVL.NodeAVL<EN>
protected static class ArbreAVL.NodeAVL<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.
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 |
---|
protected int altura
Constructor Detail |
---|
public ArbreAVL.NodeAVL(EN elem)
elem
- valor de l'element que ha d'anar al nodeMethod Detail |
---|
public void setAltura(int altura)
altura
- nou valor de l'alturapublic int getAltura()
public void ajustarAltura()
public int balanceig()
public void equilibrar()
protected void rotarDD()
A B / \ / \ / \ / \ T0 B ----------> A T2 / \ / \ / \ / \ T1 T2 T0 T1L'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.
protected void rotarDE()
A -----> A / \ / \ / \ / \ T0 B T0 C -----> C / \ / \ / \ / \ / \ / \ C T3 T1 B A B / \ / \ / \ / \ / \ / \ / \ / \ T1 T2 T2 T3 T0 T1 T2 T3Per 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.
rotarEE()
,
rotarDD()
protected void rotarEE()
A B / \ / \ / \ / \ B T0 ----------> T2 A / \ / \ / \ / \ T2 T1 T1 T0
rotarDD()
protected void rotarED()
A -----> A / \ / \ / \ / \ B T0 C T0 -----> C / \ / \ / \ / \ / \ / \ T3 C B T1 B A / \ / \ / \ / \ / \ / \ / \ / \ T2 T1 T3 T2 T3 T2 T1 T0
rotarDE()
|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |