|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectuoc.ei.tads.ArbolBinarioEncadenadoImpl.NodoArbol<EN>
uoc.ei.tads.ArbolAVL.NodoAVL<EN>
protected static class ArbolAVL.NodoAVL<EN>
Clase que extiende NodoArbol para incorporar un atributo de altura que permite comprobar y mantener el equilibrio de un arbol de nodos AVL.
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 |
---|
protected int altura
Constructor Detail |
---|
public ArbolAVL.NodoAVL(EN elem)
elem
- valor del elemento que debe ir al nodoMethod Detail |
---|
public void setAltura(int altura)
altura
- nuevo valor de la alturapublic int getAltura()
public void ajustarAltura()
public int balanceo()
public void equilibrar()
protected void rotarDD()
A B / \ / \ / \ / \ T0 B ----------> A T2 / \ / \ / \ / \ T1 T2 T0 T1La 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.
protected void rotarDE()
A -----> A / \ / \ / \ / \ T0 B T0 C -----> C / \ / \ / \ / \ / \ / \ C T3 T1 B A B / \ / \ / \ / \ / \ / \ / \ / \ T1 T2 T2 T3 T0 T1 T2 T3Para 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.
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 |