PDF de programación - TEMA 3 - El tipo árbol

DLSI (Univ. Alicante)

TEMA 3

El tipo árbol

PROGRAMACIÓN Y ESTRUCTURAS DE

DATOS

DLSI (Univ. Alicante)

Tema 3. Tipo árbol

Tipo árbol

1. Definiciones generales
2. Árboles binarios
3. Árboles de búsqueda

3.1. Árboles binarios de búsqueda
3.2. Árboles AVL
3.3. Árboles 2-3
3.4. Árboles 2-3-4
3.5. Árboles rojos-negros
3.6. Árboles B

2

DLSI (Univ. Alicante)

Tema 3. Tipo árbol

1. Definiciones generales (I)

La estructura de datos árbol aparece porque los elementos que lo constituyen
mantienen una estructura jerárquica, obtenida a partir de estructuras lineales, al
eliminar el requisito de que cada elemento tiene como máximo un sucesor:

A

B

C

D

X

TIPO LINEAL

ÁRBOL

Y

Z

Los elementos de los árboles se llaman nodos

DLSI (Univ. Alicante)

Tema 3. Tipo árbol

1. Definiciones generales (II)

Raíz

Definición inductiva de árbol:

un único nodo es un árbol (raíz)
dados n árboles a1, ..., an se puede
construir uno nuevo como resultado de
enraizar un nuevo nodo con los n árboles.
Los árboles ai pasan a ser subárboles
del nuevo árbol y el nuevo nodo se
convierte en raíz del nuevo árbol

Árbol vacío o nulo ⇒ 0 nodos

a1

a2

a3

3

4

DLSI (Univ. Alicante)

Tema 3. Tipo árbol

1. Definiciones generales (III)

El proceso de enraizar puede involucrar:

un nº indeterminado de subárboles (árboles generales)
o bien, un nº máximo n de subárboles (árboles n-arios)

Árbol general

Árbol n-ario

DLSI (Univ. Alicante)

Tema 3. Tipo árbol

1. Definiciones generales (IV)

Un árbol n-ario con n = 2 se denomina árbol binario
La información almacenada en los nodos del árbol se denomina etiqueta
Las hojas son árboles con un solo nodo (árboles binarios: árbol compuesto
por una raíz y 2 subárboles vacíos)
Grado de un árbol es el número máximo de hijos
que pueden tener sus subárboles (si el árbol
es n-ario, el grado es n)

Hojas

5

6

DLSI (Univ. Alicante)

Tema 3. Tipo árbol

1. Definiciones generales (V)
a1

Camino:

es una secuencia a1, ..., as de
árboles tal que, ∀ i ∈ {1... s - 1 },
ai+1 es subárbol de ai
el número de subárboles de la
secuencia menos uno, se
denomina longitud del camino
(Consideraremos que existe un camino de
longitud 0 de todo subárbol a sí mismo)

a2

a3

a4

a5

∀ i ∈ {1... 4} ai+1es
subárbol de ai
Longitud = 5 - 1 = 4

7

DLSI (Univ. Alicante)

Tema 3. Tipo árbol

1. Definiciones generales (VI)

a1 es ascendiente de a2 (y a2 es
descendiente de a1 ) si existe un camino
a1, ..., a2

(Según la definición de camino, todo subárbol
es ascendiente/descendiente de sí mismo)

Los ascendientes (descendientes) de un
árbol, excluido el propio árbol, se
denominan ascendientes (descendientes)
propios

a1

a2

8

DLSI (Univ. Alicante)

Tema 3. Tipo árbol

1. Definiciones generales (VII)

Padre

Hijo

Hijo

Padre es el primer ascendiente propio,
si existe, de un árbol
Hijos son los primeros descendientes
propios, si existen, de un árbol
Hermanos son subárboles con el
mismo padre
Profundidad de un subárbol es la
longitud del único camino desde la
raíz a dicho subárbol

9

DLSI (Univ. Alicante)

Tema 3. Tipo árbol

1. Definiciones generales (VIII)

Nivel de un nodo:

el nivel de un árbol vacío es 0
el nivel de la raíz es 1
si un nodo está en el nivel i, sus hijos
están en el nivel i + 1

Altura (profundidad) de un árbol:

es el máximo nivel de los nodos de un
árbol

Nivel 1

Nivel 2

Niv 3

Nivel 4

Altura del árbol = 5

Niv 5

10

DLSI (Univ. Alicante)

Tema 3. Tipo árbol

1. Definiciones generales (IX)

Árbol lleno es un árbol en el que todos sus
subárboles tienen n hijos (siendo n el grado del
árbol) y todas sus hojas tienen la misma
profundidad

1

2

3

4

5

6

7

Árbol completo es un árbol cuyos nodos
corresponden a los nodos numerados (la
numeración se realiza desde la raíz hacia las
hojas y, en cada nivel, de izquierda a derecha) de
1 a n en el árbol lleno del mismo grado. Todo
árbol lleno es completo

4

1

2

3

DLSI (Univ. Alicante)

Tema 3. Tipo árbol

2. Árboles binarios

Definición de árbol binario y propiedades
Especificación algebraica
Recorridos
Enriquecimiento de la especificación
Representación secuencial y enlazada
Otras operaciones interesantes
Ejercicios

11

12

DLSI (Univ. Alicante)

2. Árboles binarios

DEFINICIÓN

Tema 3. Tipo árbol

Un árbol binario es un conjunto de elementos del mismo tipo tal que:
o bien es el conjunto vacío, en cuyo caso se denomina árbol vacío o
nulo
o bien no es vacío, y por tanto existe un elemento distinguido llamado
raíz, y el resto de los elementos se distribuyen en dos subconjuntos
disjuntos, cada uno de los cuales es un árbol binario llamados,
respectivamente subárbol izquierdo y subárbol derecho del árbol
original

DLSI (Univ. Alicante)

2. Árboles binarios

PROPIEDADES (I)

Tema 3. Tipo árbol

Propiedades:

El máximo número de nodos en un nivel i de un árbol binario es
N(i) = 2i - 1 , i ≥1
Demostración
Base inducción
nivel 1 (raíz): N(1) = 21 - 1 = 20 = 1 (se cumple)

Paso inductivo
Se desea probar N(i-1) ⇒ N(i), es decir, a partir de la suposición
“temporal” de que N es cierta para i-1 debemos probar que es
cierta para i

nivel i - 1: N(i-1) = 2( i - 1 ) - 1 = 2i - 2 (suponemos cierto)
nivel i : N(i) = N(i-1) * 2 = 2 i - 2 * 2 = 2i - 2 + 1 = 2i - 1

13

14

DLSI (Univ. Alicante)

2. Árboles binarios

PROPIEDADES (II)

Tema 3. Tipo árbol

El máximo número de nodos en un árbol binario de altura k es
N(k) = 2k - 1, k ≥1
Demostración
nivel 1: 21 - 1 = 1 nodo
nivel 2: 22 - 1 = 2 nodos
nivel 3: 23 - 1 = 4 nodos Altura k = 21 - 1 + 22 - 1 + ... + 2k - 1 =
. . . S.P.G. ( r = 2, a1 = 20, n = k)
nivel k: 2k - 1 nodos

= 1 (2k - 1) / 2 - 1 = 2k - 1

DLSI (Univ. Alicante)

2. Árboles binarios

ESPECIFICACIÓN ALGEBRAICA (I)

Tema 3. Tipo árbol

MODULO ARBOLES_BINARIOS

USA BOOL, NATURAL

PARAMETRO TIPO item

OPERACIONES

error_item( ) item

FPARAMETRO
TIPO arbin
OPERACIONES

crea_arbin( ) arbin
enraizar( arbin, item, arbin ) arbin
raiz( arbin ) item
esvacio( arbin ) bool
hijoiz, hijode( arbin ) arbin
altura( arbin ) natural

VAR i, d: arbin; x: item;
ECUACIONES
raiz( crea_arbin( ) ) = error_item( )
raiz( enraizar( i, x, d ) ) = x
hijoiz( crea_arbin( ) ) = crea_arbin( )
hijoiz( enraizar( i, x, d ) ) = i
hijode( crea_arbin( ) ) = crea_arbin( )
hijode( enraizar( i, x, d )) = d
esvacio( crea_arbin( ) ) = CIERTO
esvacio( enraizar( i, x, d ) ) = FALSO
altura( crea_arbin( ) ) = 0
altura( enraizar( i, x, d ) ) =

1 + max ( altura( i ), altura( d ) )

FMODULO

15

16

DLSI (Univ. Alicante)

2. Árboles binarios

ESPECIFICACIÓN ALGEBRAICA (II)

Tema 3. Tipo árbol

altura(crea_arbin( )) = 0
altura = 1 + max(altura(hijoiz), altura(hijode))

ALTURA= 1 +
= 3

2

altura = 1 + 0

altura = 1 +
= 2

1

altura = 1 + 0

altura = 1 + 0

DLSI (Univ. Alicante)

2. Árboles binarios

RECORRIDOS

Tema 3. Tipo árbol

Recorrer un árbol es visitar cada nodo del árbol una sola
vez
Recorrido de un árbol es la lista de etiquetas del árbol
ordenadas según se visitan los nodos
Se distinguen dos categorías básicas de recorrido:

recorridos en profundidad
recorridos en anchura o por niveles

17

18

DLSI (Univ. Alicante)

2. Árboles binarios

RECORRIDOS EN PROFUNDIDAD (I)

Tema 3. Tipo árbol

Si representamos por I: ir hacia la izquierda, R: visitar o escribir el
item, D: ir hacia la derecha, existen 6 posibles formas de recorrido en
profundidad: RID, IRD, IDR, RDI, DRI y DIR. Si sólo queremos
hacer los recorridos de izquierda a derecha quedan 3 formas de
recorrido:

1. RID o preorden (orden previo)
2. IRD o inorden (orden simétrico)
3. IDR o postorden (orden posterior)
(El recorrido en postorden es el inverso especular del recorrido preorden, es
decir, se recorre el árbol en preorden, visitando primero el subárbol derecho
antes que el izquierdo, y se considera la lista resultante como el inverso de la
solución)

19

DLSI (Univ. Alicante)

2. Árboles binarios

RECORRIDOS EN PROFUNDIDAD (II)

Tema 3. Tipo árbol

algoritmo preorden ( a : arbin )
algoritmo preorden ( a : arbin )
algoritmo preorden ( a : arbin )
algoritmo preorden ( a : arbin )
algoritmo preorden ( a : arbin )
algoritmo preorden ( a : arbin )
algoritmo preorden ( a : arbin )
algoritmo preorden ( a : arbin )
algoritmo preorden ( a : arbin )
algoritmo preorden ( a : arbin )
algoritmo preorden ( a : arbin )
algoritmo preorden ( a : arbin )
algoritmo preorden ( a : arbin )
algoritmo preorden ( a : arbin )

si ( no esvacio( a ) ) entonces
si ( no esvacio( a ) ) entonces
si ( no esvacio( a ) ) entonces
si ( no esvacio( a ) ) entonces
si ( no esvacio( a ) ) entonces
si ( no esvacio( a ) ) entonces
si ( no esvacio( a ) ) entonces
si ( no esvacio( a ) ) entonces
si ( no esvacio( a ) ) entonces
si ( no esvacio( a ) ) entonces
si ( no esvacio( a ) ) entonces
si ( no esvacio( a ) ) entonces
si ( no esvacio( a ) ) entonces
si ( no esvacio( a ) ) entonces

escribe ( raiz ( a ) )
escribe ( raiz ( a ) )
escribe ( raiz ( a ) )
escribe ( raiz ( a ) )
escribe ( raiz ( a ) )
escribe ( raiz ( a ) )
escribe ( raiz ( a ) )
escribe ( raiz ( a ) )
escribe ( raiz ( a ) )
escribe ( raiz ( a ) )
escribe ( raiz ( a ) )
escribe ( raiz ( a ) )
escribe ( raiz ( a ) )
escribe ( raiz ( a ) )
preorden ( hijoiz ( a ) )
preorden ( hijoiz ( a ) )
preorden ( hijoiz ( a ) )
preorden ( hijoiz ( a ) )
preorden ( hijoiz ( a ) )
preorden ( hijoiz ( a ) )
preorden ( hijoiz ( a ) )
preorden ( hijoiz ( a ) )
preorden ( hijoiz ( a ) )
preorden ( hijoiz ( a ) )
preorden ( hijoiz ( a ) )
preorden ( hijoiz ( a ) )
preorden ( hijoiz ( a ) )
preorden ( hijoiz ( a ) )
preorden ( hijode ( a ) )
preorden ( hijode ( a ) )
preorden ( hijode ( a ) )
preorden ( hijode ( a ) )
preorden ( hijode ( a ) )
preorden ( hijod