Arboles balanceados

1. República Bolivariana de Venezuela
Decanato de Ingeniería
Universidad Fermín Toro
Cabudare –Edo Lara
MAPA CONCEPTUAL
TECNICAS DE ROTACION EN ARBOLES
BALANCEADOS
Presentado por:
Lourdes Barrios
C.I. 19.954.486
Asignatura: Análisis de Algoritmo
Prof. Ing. Diosmary Marrón
Febrero -2013

2. Árboles Balanceados
Ungrafosedefinedelasiguientemanera:Ungrafoconsistedeun
númerodenodos(puntosovértices)yungrupodearcosqueunenparejasde
nodos.Atodoslosparesdenodosunidosporunarcoselesllamanodos
adyacentes.Losarcospuedentenerunadireccióndeterminada,generandoasí
ungrafodirigido,elcualdelocontrarioseríano-dirigido.(Tambiénexistenlos
grafosmixtos).Porconvenciónalosnodosdeungrafoselerepresentacon
círculosylosarcosquelosconectancomolíneas(no-dirigido)oflechas
(dirigido).
definición
Elfactordeequilibrioesladiferenciaentrelasalturas
delárbolderechoyelizquierdo:
FE=alturasubárbolderecho-alturasubárbolizquierdo;
Pordefinición,paraunárbolAVL,estevalordebeser-1,0
ó1
Sielfactordeequilibriodeunnodoes:
0->elnodoestáequilibradoysussubárbolestienen
exactamentelamismaaltura.
1->elnodoestádesequilibradoysusubárbolderechoesun
nivelmásalto.
-1->elnodoestádesequilibradoysusubárbolizquierdoesun
nivelmásalto.
Factor de Equilibrio
características:
-Árbolbalanceadoporaltura:endóndetodos
loshijosonodoshojaseintentanmantenerala
mismadistanciadelaraíz.
-Árbolbalanceadoporpeso:endóndelos
nodosmásvisitadosoutilizadossemantienena
pocadistanciadelaraíz.
ARBOLESAVL:esunárbolbinarioenelcualcadanodocumpleconquetodoslosnodosdesusubárbol
izquierdosonmenoresquelaraízytodoslosnodosdelsubárbolderechosonmayoresquelaraíz.
Rotación Simple
a la Derecha:
Rotación Simple
a la Izquierda:
oprotIzq: AVL{X} -> [AVL{X}] .
eqrotIzq(arbolBin(R1, I, arbolBin(R2, I2, D2))) ==
arbolBin(R2, arbolBin(R1, I, I2), D2) .
oprotDer:AVL{X}->[AVL{X}].
eqrotDer(arbolBin(R1,arbolBin(R2,I2,D2),D1))==
arbolBin(R2,I2,arbolBin(R1,D2,D)).

3. Insertar
Usamoslamismatécnicaparainsertarunnodo
enunABBordenadotrazamosunaruta
desdeelnodoraizhastaunnodohoja
(dondehacemoslainserción).
Insertamoselnodonuevo.
Volvemosatrazarlarutaderegresoalnodoraíz,
ajustandoelequilibrioalolargodeella.
Sielequilibriodeunnodollegaaser+-2,
volvemosaajustarlossubárbolesdelos
nodosparaquesuequilibriosemantenga
acordeconloslineamientosAVL(queson
+-1)
Eliminar
AleliminarunnodoenunárbolAVLpuede
afectarelequilibriodesusnodos.Entonceshay
quehacerrotacionessimplesodobles.
Eliminasunnodocomolohacemosenunárbol
binarioordenado.Allocalizarelnodoque
queremoseliminarseguimosesteprocedimiento:
-Sielnodoesunnodohoja,simplementelo
eliminamos.
-Sielnodosolotieneunhijo,lo
sustituimosconsuhijo.
-Sielnodoeliminadotienedoshijos,lo
sustituimosporelhijoderechoy
colocamoselhijoizquierdoenelsubárbol
izquierdodelhijoderecho.
Rotación Doble a la Derecha
LaRotacióndoblealaDerechasondosrotacionessimples,
primerorotaciónsimpleizquierdayluegorotaciónsimplederecha.
Rotación Doble a la Izquierda
LaRotacióndoblealaIzquierdasondosrotacionessimples,
primerorotaciónsimplederechayluegorotaciónsimpleizquierda