Especificación informal del Árbol BinarioEspecificación informal del Árbol Binario  

ArbolBinario tiene las siguientes operaciones crea, vacio, raiz, padre, hijoIzquierdo, hijoDerecho, info, insertaIzquierdo, insertaDerecho, suprimeIzquierdo, suprimeDerecho, modifica, nodoNulo. 

DescripcionDescripcion:

Los objetos de la clase CArbolB son arboles binarios donde cada nodo  contiene un dato  del tipo Cobjeto. Las los nodos en el árbol son del tipo CnodoArb. Los árboles son mutables: insertaIzquierdo, insertaDerecho, suprimeIzqquierdo, suprimeDerecho y modifica añaden, eliminan y modifican respectivamente elementos de un árbol.

 

OPERACIONESOPERACIONES: crea() devuelve (A:CArbolB)

efecto: Devuelve el árbol vacío A.

vacio(A: CArbolB) devuelve (booleano) efecto: Devuelve cierto si A es el árbol vacío, y falso en

caso contrario.

raiz(A: CArbolB) devuelve (CnodoArb) efecto: Devuelve la referencia del nodo raíz en el árbol A.

Si el árbol A está vacío, devuelve nulo  

padre(A: CArbolB; P: CnodoArb) devuelve (CnodoArb) requerimientos: El árbol A es no vacío. El nodo P es no

nulo. efecto: Devuelve la referencia del nodo padre del nodo P

en el árbol A. Si P es la raiz, devuelve nulo.

hijoIzquierdo(A: CArbolB; P: CnodoArb) devuelve (CnodoArb)} requerimientos: El árbol A es no vacío. El nodo P es no

nulo. efecto: Devuelve la referencia del nodo hijo izquierdo del

nodo P en el árbol A. Si el nodo P no tiene hijo izquierdo, devuelve nulo.

OPERACIONESOPERACIONES:

hijoDerecho(A: CArbolB; P: CnodoArb) devuelve (CnodoArb) requerimientos: El árbol A es no vacío. El nodo P es no

nulo. efecto: Devuelve la referencia del nodo hijo derecho

del nodo P en el árbol A. Si el nodo P no tiene hijo derecho, devuelve nulo

info(A: CArbolB; P: CnodoArb) devuelve (E: Cobjeto) requerimientos: El árbol A es no vacío. El nodo P es no

nulo. efecto: Devuelve en E el contenido del nodo P en el

árbol A.

insertaIzquierdo(A: CArbolB; P: CnodoArb; E: Cobjeto) requerimientos: Si el árbol A es no vacío, entonces el

nodo P es no nulo y el nodo hijo izquierdo de P es nulo modifica: A. efecto: Añade un nodo, con contenido E, como hijo

izquierdo del nodo P en el árbol A. Si el árbol A es vacío, entonces añade un nodo con contenido E como raíz del árbol A.

OPERACIONESOPERACIONES insertaDerecho(A: CArbolB; P: CnodoArb; E:

Cobjeto) requerimientos: El árbol A es no vacío. El nodo P

es no nulo. El nodo hijo derecho de P es nulo modifica: A. efecto: Añade un nodo, con contenido E, como

hijo derecho del nodo P en el árbol A.

suprimeIzquierdo(A: CArbolB; P: CnodoArb) requerimientos: El árbol A es no vacío. El nodo P

es no nulo. modifica: A. efecto: Suprime el hijo izquierdo del nodo P en el

árbol A y todos sus descendientes.

suprimeDerecho(A: CArbolB; P: CnodoArb) requerimientos: El árbol A es no vacío. El nodo P

es no nulo. modifica: A. efecto: Suprime el hijo derecho del nodo P en el

árbol A y todos sus descendientes.

OPERACIONESOPERACIONES

modifica(A: CArbolB; P: CnodoArb; E: Cobjeto) requerimientos: El árbol A es no vacío. El nodo P es no

nulo. modifica: A. efecto: Modifica el contenido del nodo P en el árbol A,

cambiándolo por el nuevo contenido E.   nodoNulo(P: CnodoArb) devuelve (booleano)

efecto: Devuelve cierto si P es nulo, y falso en caso contrario.

Como ejemplos de uso de árboles binarios veremos los esquemas de recorrido para estos. Para árboles binarios, se definen los recorridos en preorden, inorden y postorden de la siguiente forma:

Preorden:Preorden:

Si el árbol binario es vacío, entonces la lista vacía es el listado de los nodos del árbol binario en preorden.

Si el árbol binario no es vacío, el listado en preorden de sus nodos está formado, primero, por la raíz del árbol, seguido por los nodos del subárbol izquierdo en preorden, y finalmente, por los nodos del subárbol derecho en preorden.

InordenInorden::

Si el árbol binario es vacío, entonces la lista vacía es el listado de los nodos del árbol binario en inorden.

Si el árbol binario no es vacío, el listado en inorden de sus nodos está formado, primero, por los nodos del subárbol izquierdo en inorden, seguido por la raíz del árbol, y finalmente, por los nodos del subárbol derecho en inorden.

PostordenPostorden::

Si el árbol binario es vacío, entonces la lista vacía es el listado de los nodos del árbol binario en postorden.

Si el árbol binario no es vacío, el listado en postorden de sus nodos está formado, primero, por los nodos del subárbol izquierdo en postorden, luego por los nodos del subárbol derecho en postorden, y finalmente, por la raíz del árbol.

Un Un árbol binario de búsquedaárbol binario de búsqueda es un árbol binario es un árbol binario formado por elementos en los cuales se asume un formado por elementos en los cuales se asume un orden lineal, y éstos se organizan en el árbol de la orden lineal, y éstos se organizan en el árbol de la forma: forma: todos los elementos almacenados en el subárbol todos los elementos almacenados en el subárbol

izquierdo de cualquier nodo sonizquierdo de cualquier nodo son menores que el menores que el elemento almacenado en dicho nodoelemento almacenado en dicho nodo

todos los elementos almacenados en el subárbol todos los elementos almacenados en el subárbol derecho de cualquier nodo son mayores que el derecho de cualquier nodo son mayores que el elemento almacenado en ese nodo elemento almacenado en ese nodo

Los árboles binarios de búsqueda se utilizan Los árboles binarios de búsqueda se utilizan típicamente como estructura de datos para la típicamente como estructura de datos para la representación de conjuntos con operacionesrepresentación de conjuntos con operaciones:: iinsertanserta,, para insertar un elemento dado en un conjuntopara insertar un elemento dado en un conjunto ssuprimeuprime,, para suprimir un elemento determinado de un para suprimir un elemento determinado de un

conjuntoconjunto mmiembroiembro,, para saber si un elemento dado pertenece o para saber si un elemento dado pertenece o

no a un conjunto.no a un conjunto.

Todas estas operaciones pueden realizarse en un Todas estas operaciones pueden realizarse en un tiempo de ejecución promedio tiempo de ejecución promedio O(O(loglogn)n) para un para un conjunto conjunto de de nn elementos. elementos.

Otras posibles operaciones que puede realizarse con Otras posibles operaciones que puede realizarse con el mismo tiempo de ejecución promedio usando el mismo tiempo de ejecución promedio usando árboles binarios de búsqueda sonárboles binarios de búsqueda son:: mminin,, que devuelve el elemento mínimo de un árbol que devuelve el elemento mínimo de un árbol suprime_minsuprime_min,, que elimina el elemento mínimo de un árbol que elimina el elemento mínimo de un árbol mmaxax,, que devuelve el elemento máximo de un árbol que devuelve el elemento máximo de un árbol suprime_maxsuprime_max,, que elimina el elemento máximo de un que elimina el elemento máximo de un

árbolárbol

Especificación InformalEspecificación Informal

ArbolBinarioBusquedaArbolBinarioBusqueda tienetiene operaciones crea, destruye, operaciones crea, destruye, vacio, inserta, suprime, miembro.vacio, inserta, suprime, miembro.

Descripción:Descripción: Los valores ArbolBinarioBusqueda son árboles binarios Los valores ArbolBinarioBusqueda son árboles binarios

de búsqueda de elementos del tipo de búsqueda de elementos del tipo CobjetoCobjeto.  Los árboles .  Los árboles binarios de búsqueda son mutables: inserta y suprime binarios de búsqueda son mutables: inserta y suprime aaññaden y eliminan elementos en el árbol aden y eliminan elementos en el árbol respectivamente.respectivamente.

OOperacionesperaciones crea() devuelve (A:ArbolBinarioBusqueda)crea() devuelve (A:ArbolBinarioBusqueda)

efecto: Devuelve el árbefecto: Devuelve el árbool binario de búsqueda vacl binario de búsqueda vacíío A. o A.

OOperacionesperaciones

vacio(A:ArbolBinarioBusqueda) devuelve (booleano)vacio(A:ArbolBinarioBusqueda) devuelve (booleano) efecto: Devuelve cierto si A es el árbol vacefecto: Devuelve cierto si A es el árbol vacíío, yo, y falso en caso falso en caso

contrario.contrario.

inserta(A:ArbolBinarioBusqueda; E:inserta(A:ArbolBinarioBusqueda; E:CobjetoCobjeto)) modifica: A.modifica: A. eefecto: Añade el elemento E al árbol binario de búsqueda A.fecto: Añade el elemento E al árbol binario de búsqueda A.

suprime(A:ArbolBinarioBusqueda; E: suprime(A:ArbolBinarioBusqueda; E: CobjetoCobjeto)) modifica: A.modifica: A. efecto: Suprime el elemento E, si existe, del árbol binario de efecto: Suprime el elemento E, si existe, del árbol binario de

búsquedabúsqueda A.A.

miembro(A:ArbolBinarioBusqueda; E: miembro(A:ArbolBinarioBusqueda; E: CobjetoCobjeto) devuelve ) devuelve (booleano)(booleano) efecto: Devuelve cierto si E es un elemento del árbol binario efecto: Devuelve cierto si E es un elemento del árbol binario

de búsqueda A, y falso en caso contrario.de búsqueda A, y falso en caso contrario.

Con el objeto de mejorar el rendimiento en la búsqueda surgen los árboles balanceados. La idea central de estos es la de realizar reacomodó o balanceos después de inserciones o eliminaciones de elementos. Estos árboles también nombrados recientemente AVL en honor a sus inventores, dos matemáticos rusos Adelson-Velskii y Landis.

El Factor de Equilibrio (FE) o de Balance (FB) de un nodo se define como la altura del SAD menos la altura del SAI correspondiente. El Factor de Equilibrio de cada nodo en un árbol balanceado será –1, 1 ó 0. Si FE llegara a tomar los valores de –2 ó 2, entonces debería reestructurarse el árbol.

Factor de Equilibrio

Arbol Balanceado

Reestructuración de Arboles AVL Reestructurar un árbol balanceado significa rotar los nodos del mismo. La rotación puede ser simple o compuesta. En el primer tipo de rotación se involucran dos nodos y en el segundo, se afectan tres. Si la rotación es simple puede realizarse por las ramas derechas (RDD: Rotación Derecha Derecha) o por las ramas izquierdas (RII: Rotación Izquierda Izquierda). Si la rotación es compuesta puede realizarse por las ramas derecha e izquierda (RDI: Rotación Derecha Izquierda) o por las ramas izquierda y derecha (RID: Rotación Izquierda Derecha).

CASO 1. El SAI y el SAD del árbol balanceado tienen la misma altura (hSAD = hSAI):

a) Si se inserta un elemento en SAI entonces hSAD será menor que hSAIb) Si se inserta un elemento en SAD entonces hSAD será mayor que hSAI

Ya sea para a) o para b), no se viola el criterio de equilibrio o balance del árbol.

B C

A

B C

A

B C

A

CASO 1 1.b1.a

DD

CASO 2. El SAI y el SAD del árbol balanceado tienen altura diferente (hSAD ≠ hSAI):

CASO 2.1. Si hSAD > hSAI

a) Si se inserta un elemento en SAI entonces hSAD será igual a hSAI Las ramas tienen la misma altura por lo que se mejora el equilibriob) Si se inserta un elemento en SAD entonces el árbol debe ser reestructurado Las ramas están desequilibradas por lo que se requiere reestructuración

B C

A

D

B C

A

DE

B C

A

DE

CASO 2.1. 2.1.a. 2.1.b.

F

CASO 2.2. Si hSAD < hSAIa) Si se inserta un elemento en SAI entonces el árbol debe ser reestructurado Las ramas están desequilibradas por lo que se requiere reestructuraciónb) Si se inserta un elemento en SAD entonces hSAD será igual a hSAI Las ramas tienen la misma altura por lo que se mejora el equilibrio

Para poder determinar si un árbol está balanceado debe calcularse el FE de cada nodo del árbol.

B C

A

D

CASO 2.2.

B C

A

D

2.2.a.

E

B C

A

ED

2.2.b.

El proceso de inserción en un árbol balanceado consta de los siguientes pasos:

1) Primero debe seguirse el camino de búsqueda del árbol, hasta localizar el lugar donde hay que insertar el elemento.

2) Se calcula su FE, que será cero (pues el elemento recién insertado posee SAI y SAD vacíos). Luego, se regresa por el camino de búsqueda calculando el FE de todos los demás nodos que componen el árbol. Si en alguno de los nodos se viola el criterio de equilibrio entonces debe reestructurarse el árbol. El proceso termina al llegar a la raíz del árbol, o cuando se realiza la reestructuración del mismo, en cuyo caso no es necesario determinar el FE de los nodos restantes.

Ejemplo de Inserción de Nodos con Árboles AVL

Se insertara la siguiente secuencia: 65, 50, 23, 70, 82, 68 y 39

//NODO es de tipo puntero, BO es booleano indica que el árbol a crecido (falso), INFOR es de tipo //entero. OTRO, NODO1, NODO2 son variables auxiliares de tipo puntero

insertaBalanceado(NODO, BO, INFOR){

1. Si NODO≠null

entonces

1.1. Si INFOR < NODO^.INFO

entonces:

1.1.1. Si BO = VERDADERO

entonces:

1.1.1.1. Si NODO^.FE

= 1: Hacer NODO^.FE=0 y BO=falso

=0 : Hacer NODO^.FE = -1

= -1 : Hacer NODO1 = NODO^.IZQ

//{Restructuración del árbol}

1.1.1.1.1. Si NODO1^.FE ≤ 0

entonces: //{Rotacion II} Hacer

NODO^.IZQ =NODO^.DER

NODO1^.DER = NODO

NODO^.FE = 0 y NODO = NODO1

//{ Termina la rotacion II}

si no: Hacer NODO2 = NODO1^.DER

NODO^.IZQ = NODO2^.DER

NODO2^.DER = NODO

NODO1^.DER = NODO2^.IZQ

NODO2^.IZQ =NODO1

1.1.1.1.2.A. Si NODO2^.FE = -1

entonces: Hacer NODO^.FE =1

si no: Hacer NODO^.FE = 0

1.1.1.1.2.B. //{Fin del paso 1.1.1.1.1.A.}

1.1.1.1.2.C. Si NODO2^.FE =1

entonces: Hacer NODO1^.FE = -1

si no : Hacer NODO1^.FE = 0

1.1.1.1.2.D // Fin del paso 1.1.1.1.1.C.

Hacer: NODO = NODO2 //Termina rotacionID

1.1.1.1.2. // Fin del paso 1.1.1.1.1

Hacer NODO^.FE = 0 y BO = falso

1.1.1.2. // Fin del paso 1.1.1.1.

1.1.2. //Fin del paso 1.1.1.

SI NO :

1.1.3. Si INFOR > NODO^.INFO

entonces:

Regresar a InsertarBalanceado con NODO^.DER, BO, e INFOR

1.1.3.1. Si BO = VERDADERO

entonces:

1.1.3.1.1. Si NODO^.FE

= -1: Hacer NODO^.FE = 0 y BO= FALSO

= 0: Hacer NODO^.FE =1

= 1 : Hacer NODO1= NODO^.DER

// restructuracion del arbol

1.1.3.1.1.1. Si NODO^.FE ≥ 0

entonces: //rotacio DD

Hacer:

NODO^.DER = NODO^.IZQ

NODO^.IZQ = NODO

NODO^.FE = 0 y NODO = NODO1

// termina rotacionDI

Si no: //Rotacion DI

Hacer: NODO2 = NODO1^.IZQ

NODO^.DER = NODO2^.IZQ

NODO2^.IZQ = NODO

NODO1^.IZQ = NODO2^.DER

NODO2^.DER = NODO1

1.1.3.1.1.1.A. Si NODO2^.FE = 1

entonces: Hacer NODO^.FE = -1

si no: Hacer NODO^.FE = 0

1.1.3.1.1.1.B // fin del paso 1.1.3.1.1.1.A.

1.1.3.1.1.1C. Si NODO2^.FE = -1

entonces: Hacer NODO1^.FE =1

Si no: Hacer NODO1^.FE = 0

1.1.3.1.1.1.D. //Fin del paso 1.1.3.1.1.1.C.

1.1.3.1.1.2. // fin del paso 1.1.3.1.1.1.

Hacer NODO^.FE = 0 y BO=falso

1.1.3.1.2. // Fin del paso 1.1.3.1.1.

1.1.3.2. // Fin del paso 1.1.3.1.

Si No:

Escribir “ El nodo ya se encuentra en el arbol”

1.1.4 // Fin del paso 1.1.3

1.1.4. // Fin del paso 1.1.3.

1.2. //Fin del paso 1.1.

Si no:

CREAR NODO

HACER NODO^.INFO =INFOR

NODO^.IZQ = NULL

NODO^.DER = NULL

NODO^.FE = 0

BO = VERDADERO

2. // Fin del paso 1

PASOS A SEGUIR PARA ELIMINAR UN NODO, EN UN ARBOL BALANCEADO.

Localizar su posición en el árbol. Eliminarlo siguiendo los criterios

establecidos previamente. Regresar por el camino de búsqueda

calculando el FE de los nodos visitados. Si en alguno de los nodos se viola el criterio

de equilibrio, entonces debe reestructurarse el árbol.

El proceso concluye una vez que se llega hasta la raíz del árbol.

Para hablar sobre Arboles AVL previamente a de haberse conocido el concepto de Árbol Binario de Búsqueda.

El problema de estos tipos de estructuras es pueden producirse Arboles degenerados o parcialmente degenerados, por lo que la búsqueda de un elemento puede llegar a ser de un orden de 0(log n) y en el peor caso llegar a tener un orden de 0(n).

Gracias a los científicos Adelson – Velsky y Landis, quedó resuelto este problema ya que idearon los árboles AVL, nombrados de esta forma en su honor, o balanceados en altura.

Es un árbol binario de búsqueda equilibrado.

Un árbol AVL es un ABB en donde las alturas de los hijos izquierdo y derecho solo pueden diferir a lo máximo en uno.

-Pero si se le agregar 3

- Quedaría así:

El inconveniente que presentan estos árboles, es que al realizar modificaciones sobre él (insertar o borrar) podemos perder el equilibrio, por lo que tendremos que proceder al equilibrado del árbol mediante rotaciones.

Los árboles AVL comparten las mismas operaciones básicas que el ABB,pero precedido o seguido por una o más de las llamadas "rotaciones AVL".

Puesto que las inserciones involucran a un único nodo nuevo, los desequilibrios siempre significan que en uno (o mas) de los nodos del árbol se produce una diferencia de altura entre su subárbol izquierdo y su subárbol derecho que es 2 o −2. Así pues, después de insertar en el árbol, la detección del desequilibrio es fácil, basta con examinar el campo balance. Si el balance es −2, es que hemos insertado un nuevo nodo en el subárbol izquierdo, y si es 2, la inserción tuvo lugar en el subárbol derecho.

Los nodos tienen un Factor de Balance (FB) que está entre –1 y 1.

FB=Altura del subárbol derecho – Altura del subárbol izquierdo

FB = 0 alturas de subárbols iguales.

FB =1 subárbol derecho más grande que izquierdo.

FB = -1 subárbol izquierdo más grande que derecho

Para realizar la inserción, se realiza igual que en un árbol binario y después se verifica el balanceo.

13

21

10 18 2540

33

26

Al agregar el valor 26 el árbol cumple con las reglas de un AVL (el Factor de Balanceo de todos los nodos es 0, 1 ó –1) .

13

21

10 18 25

40

33

26

262627

Al agregar el valor 27 el árbol se DESBALANCEÓ (el Factor de Balanceo para el nodo con el valor 25 ahora es 2). Se requiere una ROTACIÓN.

El reequilibrado se produce de abajo hacia arriba sobre los nodos en los que se produce el desequilibrio. Pueden darse dos casos: rotación simple o rotación doble; a su vez ambos casos pueden ser hacia la derecha o hacia la izquierda.

5

3

2

A

C

B

D

Pívot

Raíz

Realizar la rotación a la izquierda

Baja

Sube

NODO PIVOTE: Es el nodo ancestro más cercano del nodo recién insertado cuyo Factor de Balanceo es diferente de cero.

5

3

2

AC BD

Árbol balanceado

3

5A

C

B

D

Raíz

7

Pívot

Realizar la rotación a la derecha

Baja

Sube

3

5

A CB D

7 Árbol balanceado

4

5

3

A

C

B

D

Pívot

Raíz

2 Rotaciones simples

Baja

Sube

4

5

3

A

CB

D

Pívot

Raíz

Baja

Sube

4

53

ACB D

4

C

B

D

Pívot

Raíz

5

3

A

Baja

Sube

4

5

3

A

C B

D

Pívot

RaízBaja

Sube

4

53

A C BD