12/08/2017

Introducción

— Un árbol A es un conjunto finito de uno o más nodos:

– Existe un nodo especial denominado RAIZ(V1) del árbol.
– Los nodos restantes (V1 ,V2 ,...Vn) se dividen en m>=0 conjuntos disjuntos
denominados A1, A2, A3,...Am, cada uno de los cuales es un árbol. Estos árboles se
llaman subárboles de la RAIZ.

Árboles binarios 2 3

INF2240 – Estructura de datos

Escuela de Ingeniería Informática
Pontificia Universidad Católica de Valparaíso 4 5 6 7

117

Definiciones generales Definiciones generales

— Raíz: Nodo que no tiene antecesores — Camino: Secuencia de aristas consecutivas.

— Nodo: Vértices o elementos del árbol — Rama: Camino que termina en hoja.
— Nodo Terminal u hoja: Vértices o elementos del árbol que no contienen — Nivel: Longitud que se determina por la longitud del camino desde la raíz
subárboles. al nodo específico.
— Hermanos: Nodos de un mismo padre. — Altura o profundidad: el número máximo de nodos de una rama. Equivale al
— Nodos Interiores: Nodos que no son hoja ni raíz. nivel más alto de los nodos más uno.
— Bosque: Colección de dos o más árboles. — Peso: es el número de nodos terminales.
— Arista: Enlace entre dos nodos consecutivos. — Grado: el número de hijos que salen de un nodo.
118 119

1
 12/08/2017

Definiciones generales Árboles binarios

— Un Árbol Binario es un conjunto finito de cero o más nodos tales que:

Nodo raíz
– Existe un nodo denominado raíz del árbol.
Rama – Cada nodo tiene 0, 1 o 2 subárboles, conocidos como subárbol izquierdo y subárbol
derecho.
Nodo Interior

Arista 1
1 1 1

2 0 2 0
Nodo Hoja 2 2 0

3 4 5 3 6 4 5 3 6

Nodos Hermanos
7 8 7
120 121

Árboles binarios Árboles binarios

— Se dice que dos árboles binarios son similares si tienen la misma — Se dice que dos árboles binarios son equivalentes si tienen la misma
estructura. estructura y además la misma información.

1 1

1 1
2 3 7 9

2 3 2 3
5 4 16 4

4 5 4 5

122 123

2
 12/08/2017

Árboles binarios Árboles binarios

— Un árbol binario es equilibrado si las alturas de los dos subárboles de cada — Un árbol binario es degenerado si todos sus nodos 1

nodo del árbol se diferencian en una unidad como máximo. excepto el último tienen sólo un subárbol. 2

— Un árbol binario es completo si todos sus nodos, excepto 3 1

1 1
las hojas, tienen exactamente dos subárboles. 2

2 3 2 3
— Un árbol binario es lleno si todas sus hojas están al mismo 4

4 5 6 7 4 5 nivel y todos sus nodos interiores tienen cada uno 2 hijos. 5

8 9 8
— Un árbol binario de altura h puede tener como máximo 6

✓ Equilibrado ✗ Equilibrado 2h-1 nodos.

124 125

Árboles binarios Representación de árboles binarios

1 Completo  Completo 1 Completo

1
 Lleno  Lleno Lleno
2 3 2 3
2 3

6 7 4 5 6 7
4 5 6 7

8 9

126 127

3
 12/08/2017

Recorrido de árboles binarios Recorrido de árboles binarios

— Se denomina recorrido de un árbol al proceso que permite acceder una — Recorrido in-orden
sola vez a cada uno de los nodos del árbol y el conjunto completo de – Recorrer el subárbol izquierdo en in-orden

nodos se examina. – Visitar nodo raíz

— Recorrido pre-orden – Recorrer el subárbol derecho en in-orden

– Visitar nodo raíz — Recorrido post-orden

– Recorrer el subárbol izquierdo en pre-orden – Recorrer el subárbol izquierdo en post-orden
– Recorrer el subárbol derecho en pre-orden – Recorrer el subárbol derecho en post-orden
– Visitar nodo raíz

128 129

Recorrido de árboles binarios Recorrido de árboles binarios: pre-orden

— Uso de pilas

130 131

4
 12/08/2017

Recorrido de árboles binarios: in-orden Recorrido de árboles binarios: post-orden

132 133

Actividad: árboles Árboles atados

— Recorrido in-orden — Se dice que un árbol binario está atado si

– Rutear el recorrido in-orden y pre-orden. cada nodo del árbol posee un campo A

– Se entrega de forma individual. adicional de tipo puntero al nodo siguiente B C

– Entrega: Mañana. en un determinado recorrido. D E

G H
— Existen distintas formas de atar un árbol
F J K
binario, pero cada una corresponderá al
L
recorrido en cuestión.
— Ejemplo: Atadura Unidireccional
134 135

5
 12/08/2017

Árboles binarios de búsqueda (ABB) Árboles binarios de búsqueda (ABB)

— Supongamos que se tiene n claves distintas en orden ascendente K1, K2,

K3,…,Kn y que se tiene un árbol binario T de n nodos.
Nodos Ri < R Nodos Rk > R
— Se define Ni como el iésimo nodo visitado si se recorre T en In-orden. Nodo R

Luego si se almacena la clave Ki en el nodo Ni, el árbol resultante tiene la

siguiente propiedad:
– Para cada nodo Ni con clave Ki,
– todas las claves en los nodos del subárbol izquierdo son menores que Ki y
– todas las claves en los nodos del subárbol derecho son mayores que Ki.

136 137

Árboles binarios de búsqueda (ABB) Árboles binarios de búsqueda: búsqueda

— Así, se puede observar la diferencia entre un AB y un ABB:

Árbol Binario Árbol Binario de Búsqueda

138 139

6
 12/08/2017

Árboles binarios de búsqueda: insertar Árboles binarios de búsqueda: borrar

140 141

Árboles binarios de búsqueda: borrar ABB: recorridos recursivos

— Preorden
– (1) Nodo raíz  (2) Subárbol izquierdo  (3) Subárbol derecho

— InOrden
– (1) Subárbol izquierdo  (2) Nodo raíz  (3) Subárbol derecho

— PostOrden
– (1) Subárbol izquierdo  (2) Subárbol derecho  (3) Nodo raíz

142 143

7
 12/08/2017

ABB: recorridos recursivos ABB: búsqueda recursiva

144 145

ABB: inserción recursiva ABB: eliminación recursiva

146 147

8
 12/08/2017

Actividad: árboles binarios de búsqueda Actividad: árboles binarios de búsqueda

— Usando como referencia: — Rutear:

– Función borrar iterativa
50
– Funciones de recorrido y eliminación recursivas
20 70 — Investigar:
8 40 60 80
– Desarrolle una función recursiva para eliminar un elementos del árbol. Esta función
puede ser con recursividad directa o indirecta considerando:
• No puede usar la función recursiva entregada por el profesor o ayudante.
5 11 30 45 55 65 75 90
• La actividad es individual y en la prueba/proyecto/controles podrá ser solicitado su uso.

148 149