Download Arboles AVL
Document related concepts
Transcript
Arboles AVL • Introducción • Arboles AVL (Adel’son-Vel’skii and Landis 1 Arbol AVL • Los árboles AVL son balanceados. • Un árbol AVL es un árbol binario de búsqueda tal que para cada nodo v de T, las alturas de los hijos de v difieren como mucho en 1. 44 4 2 17 78 1 3 2 32 88 50 1 48 62 1 Ejemplo de árbol AVL donde las alturas se muestran junto a los nodos 2 1 Altura de un árbol AVL • Proposición: La altura de un árbol AVL T que almacena n llaves es O(log n). • Justificación: .... 3 Inserción inserta(54) -> desbalanceado... 44 2 5 z 17 32 3 1 1 1 48 7 78 2y 1 50 2 1 64 3 4 62 88 x 5 T3 54 T0 T2 44 2 ...balanceado 4 3 17 32 1 1 1 48 2 z 6 62 2y 50 4 x 3 1 5 78 54 2 7 88 T2 T0 T1 4 T3 1 Restructuración • Hay cuatro formas de rotar nodos en un árbol AVL: - Rotación simple: a=z b=y single rotation b=y a=z c=x T0 T1 T3 T2 c =z T0 single rotation b=y c=x T1 T2 T3 b=y a=x c =z a=x T0 T1 T2 T3 T3 T2 T1 T0 5 Restructuración (cont.) • Rotaciones dobles: double rotation a=z c= y b=x a=z c= y b=x T0 T3 T2 T1 T0 T1 double rotation c=z a=y T2 T3 b=x a=y c=z b=x T3 T2 T0 T1 T3 T2 T1 T0 6 Eliminación • eliminar(32) 7