El factor de balance (FB) de un nodo es la diferencia de alturas entre la rama izquierda menos la derecha, para que el árbol esté balanceado este valor solo pueden ser -1, 0 ó 1.
FB= altura(arbol.izq)-altura(arbol.der)
Para lograr el balance adecuado, debemos ubicar al nodo hijo en la posición correcta antes de hacer cualquier rotación.
Cuando la rotación se hace con nodos externos hablamos de rotación sencilla, mientras que si se trata de nodos internos o que requieran un cambio de dirección del nodo, se refiere a una rotación doble.
Ejemplos de Auto-balanceo
1. En este ejemplo iniciamos con un árbol balanceado, pero en el paso 2 vamos a insertar el nodo 16 en el nodo hoja número 17, esta inserción des-balancea el árbol especialmente al nodo 13, por lo tanto con este nodo es que haremos una rotación doble izquierda-derecha.
2. Ahora queremos insertar 2 en el nodo hoja 3, esto des-balancea el árbol en el nodo interno 4, por lo tanto hacemos una rotación sencilla a la derecha y finalmente logramos balancear el árbol
3.Insertamos 3 en el nodo hoja 2, el nodo de des-balance es 4, así que hacemos una rotación doble derecha-izquierda
4. Insertamos 7 en el nodo hoja 8, el nodo de des-balance es 6, así que hacemos una rotación doble derecha (7-8)-izquierda.
5. Insertamos 9 en el nodo hoja 8, el des.balance se genera en el nodo interno 5, desplazamos el nodo 7 hacia arriba, esta es una rotación simple a la izquierda (solo interactuan los nodos 4, 5 y 7 en la rotación) , el nodo hoja 6 ahora depende de 5.
6. Este era el punto del examen :) así que tiene truco, Esta es una rotación doble izquierda-derecha usando los nodos 6 en la raiz, 9 y 7.
Si tienes información adicional sobre este tema, tus comentarios, dudas o enlaces de referencia serán bienvenidos, .
3 comments:
Muy buena tu Explicacion, nadamas me gustaria que agregaras los tipos en que rotan los nodos, por ejemplo he leido algo como giro doble a la derecha.. algo asi
Muy buen post, buenas explicaciones, coincido con "Angel" estaría bueno que en los ejemplos menciones que tipo de rotación realizas( simple derecha, simple izquierda, doble derecha-izquierda, doble izquierda-derecha ).
Saludos
Sus deseos son odrdenes ;), ya agregé sus requerimientos. Gracias por sus comentarios y sus consejos.
Post a Comment