Calculo

ARBOLES BALANCEADOS
La búsqueda más eficiente se efectúa en un árbol binario balanceado.
Desafortunadamente, la función Inserta no asegura que el árbol permanezca balanceado, el
grado de balance depende del orden del orden en que son insertados los nodos en el árbol.
La altura de un árbol binario es el nivel máximo de sus hojas (profundidad). La
altura del árbol nulo se define como –1. Unárbol binario balanceado es un árbol binario en
el cual las alturas de los dos subárboles de todo nodo difiere a lo sumo en 1. El balance de
un nodo en un árbol binario se define como la altura de su subárbol izquierdo menos la
altura de su subárbol derecho. Cada nodo en un árbol binario balanceado tiene balance
igual a 1, -1 o 0, dependiendo de si la altura de su subárbol izquierdo es mayor que,menor
que o igual a la altura de su subárbol derecho.
Supóngase que tenemos un árbol binario balanceado, y usamos la función para
insertar un nodo en dicho árbol. Entonces el árbol resultante puede o no permanecer
balanceado.
Es fácil ver que el árbol se vuelve desbalanceado si y solo si el nodo recién
insertado es un descendiente izquierdo de un nodo que tenia de manera previa balance de1,
o si es un hijo derecho descendiente de un nodo que tenia de manera previa balance –1.
Para que el árbol se mantenga balanceado es necesario realizar una transformación
en el mismo de manera que:
1. El recorrido en orden del árbol transformado sea el mismo que para el árbol original (es
decir, que el árbol transformado siga siendo un árbol de búsqueda binaria).
2. El árbol transformadoesté balanceado.
A
B

C

F

D

a) Árbol original

C

B

D

b) Rotación derecha

F

B

C

F

G

A

A

E

Figura 1

G

E

G

D

E
c) Rotación izquierda

El árbol de la figura 1b es una rotación derecha del árbol con raíz en A de manera
similar, el árbol de la figura 1c se dice que es una rotación izquierda del árbol con raíz en
A.
Un algoritmo paraimplantar una rotación izquierda de un subárbol con raíz en p es
el siguiente:
q= right(p);
hold=left(q);
left(q)=p;
right(p)=hold;
Llamemos a esta operación leftrotation(p). Rightrotation(P), puede definirse de
manera similar. Por supuesto, en cualquier rotación debe cambiarse el valor de la raíz del
subárbol que está siendo rotado para que apunte a la nueva raíz. (En el caso de la rotaciónizquierda anterior, esta nueva raíz es q). Obsérvese que el orden de los nodos en un
recorrido en orden se preserva en ambas rotaciones: izquierda y derecha. Por consiguiente,
se deduce que cualquier número de rotaciones (izquierda o derecha) pueden ejecutarse en
un árbol desbalanceado para obtener uno balanceado, sin perturbar el orden de los nodos en
un recorrido en orden.
Supóngase quese realiza una rotación derecha en el subárbol con raíz en A de la
figura 2 a. El árbol resultante se muestra en la figura 3 a. Obsérvese que el árbol de la
figura 3 a produce el mismo recorrido en orden que el de la figura 2 a y también está
balanceado. También, como la altura del subárbol de la figura 2 a era n+2 antes de la
inserción y la altura del subárbol de la figura 3 a es n+2 con elnodo insertado, el balance de
cada ancestro del nodo A no se altera. Así, reemplazando el subárbol de la figura 2ª por su
rotación derecha de la figura 3ª, garantizamos que se mantenga como árbol de búsqueda
binaria balanceado.
En la figura 2b donde el nodo recién creado se inserta en el subárbol derecho del B.
Sea C el hijo derecho de B. (Hay tres casos: C puede ser el nodo recién insertado encuyo
caso n=-1, o el nodo recién insertado puede estar en el subárbol derecho o izquierdo de C.
La figura 2b ilustra el caso en que está en el subárbol izquierdo; el análisis de los otros
casos es análogo). Supóngase que una rotación izquierda del subárbol con raíz en B precede
a una rotación derecha del subárbol con raíz en A. La figura 3b ilustra el árbol resultante.
El siguiente...