3.4 Árboles de búsqueda

3- Árboles 3.4 Árboles de búsqueda Reequilibrado de árboles AVL
Cuando se pierde la propiedad AVL podemos reequilibrar el árbol mediante una de las siguientes cuatro rotaciones: Rotación simple a derecha (rotSD): A es el nodo sobre el que se realiza la rotación. Esta rotación se realiza cuando A está desequilibrado a la izquierda (el subárbol izquierdo es 2 más alto que el derecho) y B es pesado-a-izda (el subárbol izdo de B es 1 más alto que el subárbol derecho de B). T1, T2 y T3 representan subárboles (se ha añadido un nodo a T1 por lo que B es pesado-a-izda y A está desequilibrado). A rotSD(A) B / \ ----------> / \ B T3 T1 A / \ / \ T1 T2 T2 T3 Rotación simple a izquierda (rotSI): A es el nodo sobre el que se realiza la rotación. Esta rotación se realiza cuando A está desequilibrado a la derecha (el subárbol derecho es 2 más alto que el izquierdo) y B es pesado-a-dcha (el subárbol dcho de B es 1 más alto que el subárbol izquierdo de B). T1, T2 y T3 representan subárboles (se ha añadido un nodo a T3 por lo que B es pesado-a-dcha y A está desequilibrado). A rotSI(A) B / \ ----------> / \ T1 B A T3 / \ / \ T2 T3 T1 T2 Rotación doble a izquierda (rotDI): C es el nodo sobre el que se realiza la rotación. Esta rotación se realiza cuando C está desequilibrado a la izda (el subárbol izdo es 2 más alto que el dcho), A es pesado-a-dcha (el subárbol dcho de A es 1 más alto que el subárbol izquierdo de A) y B es pesado. T1, T2, T3 y T4 representan subárboles (se ha añadido un nodo a T2 ó a T3 por lo que B es pesado, A es pesado-a-dcha y C está desequilibrado). Esta rotación consiste en una rotSI(A) seguida de una rotSD(C). C rotSI(A) C rotSD(C) B / \ ----------> / \ ---------> / \ A T4 B T4 A C / \ / \ / \ / \ T1 B A T3 T1 T2 T3 T4 / \ / \ T2 T3 T1 T2 Es decir, rotDI = rotSI + rotSD Rotación doble a derecha (rotDD): A es el nodo sobre el que se realiza la rotación. Esta rotación se realiza cuando A está desequilibrado a la dcha (el subárbol dcho es 2 más alto que el izdo), C es pesado-a-izda (el subárbol izdo de C es 1 más alto que el subárbol dcho de C) y B es pesado. T1, T2, T3 y T4 representan subárboles (se ha añadido un nodo a T2 ó a T3 por lo que B es pesado, C es pesado-a-izda y A está desequilibrado). Esta rotación consiste en una rotSD(C) seguida de una rotSI(A). A rotSD(C) A rotSI(A) B / \ ----------> / \ ----------> / \ T1 C T1 B A C / \ / \ / \ / \ B T4 T2 C T1 T2 T3 T4 / \ / \ T2 T3 T3 T4 Es decir, rotDD = rotSD + rotSI

E.Mayordomo y K. Urzelai elvira at posta.unizar.es karmelo at posta.unizar.es Fecha de actualización: 5-9-01