ESTRUCTURAS

JERÁRQUICAS Y ÁRBOLES
BINARIOS DE BÚSQUEDA
Lic. Wilber Ramos Lovón
UNSA
Estructuras Jerárquicas - Definición
 Se denominan comúnmente árboles
 Su característica principal es que mantiene
una relación uno a muchos

Figura 1

Esta estructura puede representar: Un árbol genealógico, un organigrama,

los directorios de un sistema operativo, etc.
Terminología básica en las estructuras
jerárquicas o árboles
 Nodo raíz: primer elemento de un árbol binario
 Nodo padre: tiene al menos un hijo (izq. o der.)
 Hijo derecho: se encuentra al lado derecho de otro
nodo
 Hijo izquierdo: se encuentra al lado izquierdo de otro
nodo
 Nodo hoja: no tiene hijos
 Nodo hermano: nodos que tiene a un mismos padre
 Ancestros: nodo padre de un nodo o el padre de algún
nodo ancestro (nodo raíz, ancestro de todos)
Terminología básica en las estructuras
jerárquicas o árboles
 Nodo descendiente: hijo de un nodo o hijo de algún
otro descendiente (todo nodo es descendiente de la raíz)
 Subárbol izquierdo: todo descendiente por la izquierda
de un nodo forman un subárbol izquierdo, cuya raíz es el hijo
izquierdo de ese nodo
 Subárbol derecho: todo descendiente por la derecha
de un nodo forman un subárbol derecho, cuya raíz es el hijo
derecho de ese nodo
 Nivel de un nodo: Distancia desde la raíz, la raíz esta a
nivel cero (El numero máximo de nodos en el nivel n es 2n)
Terminología básica - Ejemplo:
 Nodo raíz: 5
5  Hijo derecho de 5: 8
 Hijo izquierdo de 5: 3
3 8  Nodo padre de 2 y 4: 3
 Nodos hermanos: 2 y 4
2 4 6 9  Ancestros de 7: 6, 8, 5
 Descendientes de 8: 6, 7, 9, 10
10  Subárbol izquierdo de 5: el
1 7 quiete raíz 3
 Subárbol derecho de 5: el que
tiene raíz 8
 Nodos de nivel 1: 3 y 8
Figura 2  Nodos de nivel 2: 2, 4, 6, 9
 Nodos de nivele 3: 1, 7, 10
Árbol Binario de Búsqueda (ABB)

 Es una estructura
jerárquica 5
 No guarda información 3 8
repetida
 Relación de 1 a dos 2 4 6 9
 Cumple un
ordenamiento: 1 7 10
elementos menores a
la izquierda y mayores Figura 3
a la derecha
Árbol Binario de Búsqueda - Ejemplo

Árboles binarios de búsqueda Árboles que no son binarios

de búsqueda
Figura 4
Búsqueda en un ABB

1. Coloque un apuntador auxiliar en la raíz del nodo

2. Mientras no se haya encontrado el valor que se
busca y el apuntador auxiliar no este vacío (fuera
del árbol):
 Verifique si la información del nodo señalado por el
puntador auxiliar, es mayor, menor o igual al nodo
buscado.
 Si es mayor, mueva el apuntador auxiliar al nodo hijo
derecho; si e menor, mueva el apuntador auxiliar al nodo
hijo izquierdo. Si son iguales, ha encontrado el nodo y el
apuntador auxiliar lo señala
Búsqueda en un ABB - Ejemplo
a b

c d

Movimiento de apuntadores para buscar el elemento 13

Figura 5
Eficiencia en la búsqueda en un ABB

Si un ABB tiene distribuido sus elementos en forma

balanceada, se obtendrá el mayor beneficio, ya que
el peor caso de una búsqueda en un ABB está
determinado por la altura del árbol, y por lo tanto,
entre menor altura tenga el ABB, es decir entre mas
balanceado esté, se obtendrá mejores resultados.
Inserción de un elemento en un ABB
1. Se crea un nuevo nodo por medio de un apuntador auxiliar 1. Se llena con la
información que se va a insertar en el árbol y se colocan sus apuntadores como
nodo hoja.
2. Se coloca un apuntador auxiliar 2 en la raíz del árbol y un apuntador auxiliar 3 en
vacío. El apuntador auxiliar 3 siempre señalará al nodo padre del nodo al que
señala el apuntador auxiliar 2.
3. Mientras el apuntador auxiliar 2 no sea vacío (fuera del árbol) se realiza lo
siguiente:
 Se coloca el apuntador auxiliar 3 en el nodo que marca el apuntador auxiliar 2.
 Mueve el apuntador auxiliar 2 al nodo izquierdo si la información que se va a insertar es
menor a la información del nodo que señala el apuntador auxiliar 2; en caso contrario,
debe moverse a la derecha (pues la información por insertar es mayor)
Al salir del ciclo el apuntador auxiliar 2 señalará vacío, pero el apuntador auxiliar 3
estará en el nodo que será el padre del nuevo.
4. Verifique si el apuntador auxiliar 3 es vacío, en cuyo caso, el nuevo nodo será el
primero en el árbol y el apuntador raíz tendrá que señalarlo.
Si el apuntador auxiliar 3 no es vacío, entonces estará señalando al padre del
nuevo nodo. Se debe verificar si la información del nuevo nodo es menor a la del
marcado por la del apuntador auxiliar 3, en cuyo caso deberá encadenarse el
nuevo nodo como un hijo izquierdo del señalado por el apuntador auxiliar 3. Si la
información no es menor entonces será mayor y tendrá que encadenarse como
hijo derecho.
Inserción en un ABB - Ejemplo
a b

Inserción del elemento 15

en el ABB
Figura 6
Eliminación de un elemento en un ABB
Se pueden presentar 3 casos:
1. El nodo que se va a borrar es una hoja. Puesto que no tiene hijos, su
nodo padre apuntara ahora al vacío (figura 7).
2. El nodo por borrar tiene solo un hijo. En este caso el padre del que
se va a borrar puede apuntar directamente al nodo hijo del que se
eliminara (figura 8).
3. El nodo por borrar tiene dos hijos. Puesto que un padre no puede
heredar dos apuntadores, se busca un valor sustituto del valor por
borrar y el nodo no se borra físicamente. Se puede escoger como
sustituto el valor menor (mayor) de todos los mayores (menores), o
bien del subárbol izquierdo (derecho), el nodo mas a la derecha
(izquierda) y se elimina físicamente el nodo donde se encuentre
(figura 9). Se puede asegurar que la baja física del nodo sustituto cae
en alguno de los dos primeros casos.

El algoritmo consta de dos partes, primero localizar el nodo para

borrar y segundo eliminar el nodo correspondiente
Eliminación en un ABB - Ejemplo

Eliminación de un nodo hoja, Eliminación de un nodo con

se elimina el 8 un hijo, se elimina el 21
Figura 7 Figura 8
Eliminación en un ABB - Ejemplo

Eliminación de un nodo con dos

hijos, se elimina el elemento 12

Figura 9
Eliminación de un elemento en un ABB
Primera parte (localizar el nodo por borrar)

1. Se coloca el apuntador auxiliar 1 en la raíz del árbol y un

apuntador auxiliar 2 en vacío. El apuntador auxiliar 2 siempre
señalará al nodo padre del que señala el apuntador auxiliar 1.
2. Mientras no se haya encontrado en nodo por borrar:
1. Se verifica si al información del nodo señalado por el apuntador
auxiliar 1 es la que se desea borrar, en caso de que no sea: a)
se coloca el apuntador auxiliar 2 en el nodo que señala el
apuntador auxiliar 1 y b) se mueve el apuntador auxiliar 1 al
nodo hijo izquierdo si la información que se va a borrar es
menor a la información del nodo que señala el apuntador
auxiliar 1, en caso contrario, debe moverse a la derecha

Al salir del ciclo el apuntador auxiliar 1 estará señalando al

nodo por borrar y el apuntador auxiliar 2 al nodo padre
Eliminación de un elemento en un ABB
Segunda parte (eliminar el nodo correspondiente)

1. Se coloca un apuntador temporal en el nodo que debe borrar.

2. Se verifica si el nodo por borrar es hoja o tiene solo un hijo, en
cuyo caso se desencadenara del árbol para darle de baja.
Nodo hoja: Si el nodo apuntado por el auxiliar 1 no tiene hijo
izquierdo ni derecho, debe modificarse el apuntador que lo
conecta con su padre (a través del auxiliar 2) de tal forma que
apunte hacia vacío.
Nodo con un hijo derecho: si el nodo apuntado por el auxiliar 1
no tiene hijo izquierdo, pero si derecho, se modifica el
apuntador que lo conecta con su padre (a través del auxiliar 2)
de tal forma que señale al hijo derecho.
Nodo con un hijo izquierdo: si el nodo apuntado por el auxiliar
1 no tiene hijo derecho, pero si izquierdo, se modifica el
apuntador que lo conecta con su padre (a través del auxiliar 2)
de tal forma que señale al hijo izquierdo.
Eliminación de un elemento en un ABB
Nodo con dos hijos: si el nodo tiene dos hijos se procederá a localizar
su sustituto buscando a su predecesor de la siguiente forma:
1. Se coloca el apuntador temporal en el hijo izquierdo del nodo
señalado por el apuntador auxiliar 1.
2. Se mueve el apuntador auxiliar hacia la derecha lo mas posible es
decir, justo en el nodo antes de que el movimiento a la derecha lo
saque del árbol. El nodo al que se llegue será el nodo sustituto y
se puede asegurar que es nodo hoja o que tiene solo un hijo
izquierdo.
3. Se copia la información del nodo sustituto en el marcado por el
apuntador auxiliar 1.
4. Se desencadena el nodo señalado por el apuntador temporal de la
misma forma en que se hace para un nodo hoja o uno con hijo
izquierdo. En este caso para el movimiento de apuntadores se
tendrá que evaluar si el nodo marcado por el apuntador temporal
es la raíz del subárbol izquierdo del nodo señalado por el
apuntador auxiliar 1 o es el de un nivel inferior.
3. Se libera el nodo señalado por el apuntador temporal
Desventaja de un ABB

El orden de inserción y eliminación

determinan la forma en que se balancea el
árbol y, por lo tanto repercute en las
búsquedas posteriores. En el peor de los
casos un ABB puede degenerar en lista
sobre la que se aplica una búsqueda
secuencial.
Aplicaciones de un ABB

Útil en cualquier aplicación en la que se

requiera administrar un grupo ordenado
de datos en memoria principal, con el
objetivo básico de buscar de manera
eficiente cualquier dato
Representación física de un ABB
Representación de un ABB en
4 memoria, con nodos que contienen
apuntadores a sus hijos izquierdos y
2 7 derechos. El control del árbol esta en el
apuntador principal raíz
1 5 8
Raíz
6
4

2 7

1 5 8

Figura 10
Recorridos en un ABB
Es muy importante pues permite hacer algo en todos
los nodos. Se puede plantear de forma recursiva
 Preorden: Útil para reconstruir un ABB
1. Visite el nodo raíz del a árbol
2. Recorra en preorden el subárbol izquierdo del nodo raíz
3. Recorra el preorden el subárbol derecho del nodo raíz
 Inorden: Útil desplegar en orden la información de
un ABB
1. Recorra en inorden el subárbol izquierdo del nodo raíz
2. Visite el nodo raíz del a árbol
3. Recorra el inorden el subárbol derecho del nodo raíz
Recorridos en un ABB
 Postorden: Útil para implementar el destructor de un
árbol binario
1. Recorra en postorden el subárbol izquierdo del nodo raíz
2. Recorra el postorden el subárbol derecho del nodo raíz
3. Visite el nodo raíz del a árbol
También existen los recorridos conversos en los que
el orden de recorrido se invierte a derecha-izquierda
en vez de izquierda-derecha
Por ultimo el recorrido llamado nivel por nivel:
1. Inserte el apuntador al nodo raíz a una fila
2. Mientras la fila no se vacíe:
 Saque el apuntador de la fila y procese el nodo señalado.
 Inserte en la fila los apuntadores de los hilos del nodo
procesado (si estos existen)
Recorridos en un ABB - Ejemplo

=
 Preorden: =</&?$+
< $
 Inorden: /&<?=+$
/ ? +
 Postorden: &/?<+$=
&  Preorden conserso: =$+<?/&
 Inorden converso: $+=?<&/
Figura 11  Postorden converso: +$?&/<=
 Nivel por nivel: =<$/?+&
ÁRBOLES AVL
Numero máximo de comparaciones en el
peor caso de búsqueda en ABB
 El peor caso de una búsqueda esta determinada por la altura del
un árbol.
 Si un árbol esta balanceado, entonces la altura sería la mínima.
 Un árbol está balanceado cuando todos sus niveles excepto el
ultimo, están integrados a la máxima capacidad de nodos
 La altura mínima en un ABB con n elementos se dará en la
medida en que cada nivel del árbol este integrada a su máxima
capacidad
 En general se tiene que el numero máximo de nodos en el nivel
k en un árbol binario es 2k, entonces el numero máximo de
nodos n en un árbol binario de altura k es de: 2k-1 (n = 2k-1),
despejando se tiene k = log2(n+1), con lo que se concluye que
para el peor caso de una búsqueda en un ABB se cumpla con la
mayor eficiencia posible, el ABB debe estar balanceado.
Nivel y Altura en un ABB

Numero máximo de nodos en el nivel k es 2k

Nivel 0 → 1 elemento
Nivel 1 → 2 elementos
Nivel 2 → 4 elemento
Nivel 3 → 8 elemento
Nivel 4 → 16 elemento

Numero máximo de nodos en un árbol

binario de altura k es de: 2k-1

Altura 1 → 1 elemento
Altura 2 → 3 elementos
Figura 12 Altura 3 → 7 elemento
Altura 4 → 15 elemento
Altura 5 → 31 elemento
Árboles AVL - definición
Es un ABB que trata de mantenerse lo mas balanceado posible .
Formalmente se debe cumplir el hecho de que para cualquier nodo del
árbol, la diferencia entre las alturas de sus subárboles no exceda a una
unidad

Árboles AVL Árboles que nos AVL

Figura 13
Factor de Balance (FB) de un nodo
 Se colocan en cada nodo del árbol y guardan un valor entre 1 y -
1, este valor representa la diferencia entre las alturas de sus
subárboles.
 FB = 0 cuando las alturas de los subárboles son iguales.
 FB positivo cuando la altura del subárbol derecho es mayor que
la del izquierdo.
 FB negativo cuando la altura del subárbol izquierdo es mayor
que la del derecho.
 La especificación de un AVL es la misma que un ABB solo se
consideran cambios en las operaciones de inserción y
eliminación.
Árboles AVL y FB - Ejemplo

Árbol AVL con sus factores de balance en cada nodo

Figura 14
Inserción de un elemento en un AVL
 Al comienzo igual que un ABB: se busca la posición del
nuevo nodo dentro del árbol., el cual tendrá un FB = 0.
 Después de insertar se verifica si se ha afectado el
balanceo, si no se ha afectado, solo se modifica el FB
de los ancestros.
 Si ha ocurrido desbalanceo, se tendrán que hacer
movimientos de apuntadores y de FB para balancearlo
 Lo primero que hay que hacer es buscar un nodo pivote.
 Un nodo pivote es aquel que tiene un FB diferente de
cero y es el mas cercano a los ancestros del nodo recién
insertado
Inserción de un elemento en un AVL
 Por lo anterior, se pueden detectar los
siguientes casos:
 El árbol AVL carece de nodo pivote

Figura 15
Inserción de un elemento en un AVL
 El árbol AVL tiene nodo pivote y el nuevo se ha insertado en el
subárbol mas pequeño del pivote

Figura 16

 El árbol AVL tiene pivote y en el subárbol mas grande se inserta

un nodo
Balanceo en un AVL

 Se presentan 4 esquemas
 Rotación simple izquierda. (RSI)
 Rotación simple derecha. (RSD)
 Rotación doble izquierda. (RDI)
 Rotación doble derecha. (RDD)
Rotación Simple

Figura 17
Rotación Doble

Figura 18
Inserción - Algoritmo
1. Inserte el nodo como un ABB
2. Busque el nodo pivote, coloque los apuntadores P1, P2, P3 y P4
donde:
 P1=apunta al nodo padre del nodo pivote
 P2=apunta al nodo pivote
 P3=apunta al nodo hijo del nodo pivote (raíz del subárbol mas grande)
 P4=apunta al nodo hijo del nodo apuntado por P3
3. Si no existe nodo pivote (P2 apunta a vacío), entonces modifique los
FB desde la raíz hasta el nuevo nodo. Si el nuevo nodo se inserto en
el subárbol mas pequeño del nodo pivote, entonces modifique los FB
desde el nodo pivote hasta el nuevo. Si no es así verifique el tipo de
rotación.
 Si es rotación simple, entonces modifique apuntadores y FB según
rotación simple
 Si no, modifique apuntadores y B según rotación doble
Inserción - Algoritmo
Algoritmo para la Rotación Simple:
Suponga que los apuntadores P1, P2 y P3 ya están colocados según los
esquemas:
1. Si P1 no apunta a vacío
 Si la información del nuevo nodo es menor que la apuntada por P1
 Hijo izquierdo de P1 = P3
 Si no
 Hijo derecho de P1 = P3
 Si no
 P3 es la nueva raíz del árbol
2. Si la Información del nuevo nodo es menor que la información apuntada por P2
1. Hijo izquierdo de P2 =hijo derecho de P3
 Hijo derecho de P3 = P2
 Modificar el FB desde el hijo izquierdo de P3 hasta el padre del nuevo nodo
Si no
 Hijo derecho de P2 =hijo izquierdo de P3
 Hijo izquierdo de P3 = P2
 Modificar el FB desde el hijo derecho de P3 hasta el padre del nuevo nodo
3. El FB del nodo señalado por P2=0
Inserción - Algoritmo
Algoritmo para la Rotación Doble
1. Si P1 no apunta a vacío
 Si la información del nuevo nodo es menor que la información apuntada por P1
 Hijo izquierdo de P1=P4
Si no
 Hijo derecho de P1=P4
Si no
 P4 es la nueva raíz del árbol
2. Si la Información del nuevo nodo es menor que la información apuntada por P2
 Hijo derecho de P3 = hijo izquierdo de P4
 Hijo Izquierdo de P2 = hijo derecho de P4
 Hijo Izquierdo de P4 = P3
 Hijo derecho de P4 = P2
 **seguir en 3.a
Si no
 Hijo izquierdo de P3 = hijo derecho de P4
 Hijo derecho de P2 = hijo izquierdo de P4
 Hijo derecho de P4 = P3
 Hijo izquierdo de P4 = P2
 **seguir en 3.b
Inserción - Algoritmo
3.a Si la información del nuevo nodo es menor que la información de P4:
 Modificar FB desde el hijo derecho de P3 hasta el padre del nuevo nodo
 Modificar FB del nodo señalado por P2 (ahora vale +1)
Si no
 Si la información del nuevo nodo es mayor a la información de P4:
 Modificar FB desde el hijo izquierdo de P2 hasta el padre del nuevo
nodo
 Modificar FB del nodo señalado por P3 (ahora vale -1)
 Modificar FB del nodo señalado por P2 (ahora vale 0)
3.b Si la información del nuevo nodo es mayor que la información de P4:
 Modificar FB desde el hijo izquierdo de P3 hasta el padre del nuevo nodo
 Modificar FB del nodo señalado por P2 (ahora vale -1)
Si no
 Si la información del nuevo nodo es menor que la información de P4
 Modificar FB desde el hijo derecho de P2 hasta el padre del nuevo nodo
 Modificar FB del nodo señalado por P3 (ahora vale +1)
 Modificar FB del nodo señalado por P2 (ahora vale 0)
Inserción - Ejemplo

Inserción del elemento 52 sobre el árbol AVL

Figura 19
Inserción - Ejemplo

La inserción inicial se realiza como un ABB

Figura 20
Inserción - Ejemplo

El nodo pivote es 45, y la inserción provoca una rotación simple a la

izquierda, que genera el siguiente árbol
Figura 21
Eliminación de un elemento en un AVL

 Elimine el nodo como en un ABB

 Una vez dado de baja puede ocurrir alguna
de las siguientes situaciones:
1. El nodo que se borro no provocó un desbalanceo
en el árbol, entonces solo se ajustan los FB
2. El nodo que se borro provocó un desbalanceo en
el árbol, entonces se ajustan apuntadores para
hacer las rotaciones y algunos FB.
3. Aquí no se utiliza nodo pivote, pues una baja
puede ocasionar un desbalance total en el árbol y
más de una rotación
Casos de balanceo en la Eliminación
 Se P2 un apuntador del nodo por analizar en el
recorrido, desde el padre del nodo borrado hasta
la raíz. Sea P1 un apuntador a padre del nodo
señalado por P2
1. El nodo señalado por P2 tiene in FB=0, y no hay
desbalanceo. En este caso se ajusta el FB a + o -,
según el nodo eliminado.
2. El nodo señalado por P2 tiene un FB <>0, y el
nodo que se borró es del subárbol mas grande y
no hay desbalanceo.
3. El nodo señalado por P2 tiene un FB <>0, y el
nodo que se borró es del subárbol mas pequeño
por lo que hay desbalanceo. Entonces …
Casos de balanceo en la Eliminación
Sea P3 el apuntador al subárbol mas grande del nodo señalado
por P2.
3.1 El FB del nodo señalado por P3 =0. Se realiza una rotación
simple y se ajusta el FB del nodo apuntado por P3. Puesto que
la altura del árbol apuntado ahora por P3 no cambio. No es
necesario analizar los nodos ancestros.
3.2 El FB del nodo señalado por P2 es igual al FB del nodo
apuntado por P3. Se realiza una rotación simple y se ajusta el
FB del nodos señalado por P3. Puesto que la altura del árbol
señalado pro P3 se redujo. Es necesario seguir analizando los
nodos ancestros, por lo que P2 apunta al nuevo nodo y se
vuelve a analizar en que caso se está ubicado.
3.3 El FB del nodo señalado por P2 es contrario al FB del nodo
apuntado por P3. Se realiza una rotación doble, donde P4 es el
apuntador al subárbol mas grande del nodo señalado por P3 y
se ajusta el FB de los nodos correspondientes. Puesto que la
altura se modifica, se analizan los nodos ancestros.
Casos de balanceo en la Eliminación