Download Arbol ABB.

ÁRBOLES
Prof. Nibaldo Rodriguez A.
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
ÁRBOLES
Un árbol A es un conjunto finito de uno o más nodos tal que:
1. Existe un nodo especial denominado RAIZ(V1) del árbol.
2. Los nodos restantes (V2 ,...Vn) se dividen en m>=0 conjuntos disjuntos
denominados A1, A2, A3,...Am, cada uno de los cuales es, a su vez, un árbol.
Estos árboles se llaman Subárboles de la RAIZ.
A
B
E
C
D
F
G
K
H
I
J
L
1
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
ÁRBOLES
A
Raíz: Nodo que no tiene antecesores
Nodo: Vértices o elementos del árbol
B
C
Nodo Terminal u hoja: Vértices o elementos
del árbol que no contienen subárboles.
E
F
Hermanos: Nodos de un mismo padre.
Nodos Interiores: Nodos que no son hoja ni raíz.
Bosque: Colección de dos o más árboles.
K
Arista: Enlace entre dos nodos consecutivos.
Camino: Secuencia de aristas consecutivas.
Rama: Camino que termina en hoja.
Nivel: longitud del camino desde la raíz al nodo específico.
D
G
H
I
J
L
Altura o profundidad: el número máximo de nodos de una
rama. Equivale al nivel más alto de los nodos más uno.
Peso: es el número de nodos terminales.
Grado: el número de hijos que salen de un nodo
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Arboles Binarios
Un Árbol binario es un conjunto finito de cero o más nodos tal que:
1. Existe un nodo denominado raíz del árbol
2. Cada nodo tiene 0, 1 o 2 subárboles,
•Llamado Subárbol Izquierdo y Subárbol Derecho.
Dos Árboles Binarios son Similares si tienen la misma estructura
A
B
A
C
R
E
3
4
E
2
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Arboles Binarios
A
Se dice que dos Árboles Binarios son
equivalentes si tienen la misma
estructura
y
además
la misma
información
A
B
C
B
C
E
D
D
E
Se dice que un Árbol Binario es EQUILIBRADO si las alturas de los dos
Subárboles de cada nodo del árbol se diferencian en una unidad como máximo.
A
A
B
T
C
N
D
F
B
E
T
S
F
C
N
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Arboles Binarios
A
Un árbol binario es Completo si todos sus
nodos, excepto las hojas, tienen
exactamente dos subárboles.
B
T
C
N
E
D
F
S
A
Un árbol binario es lleno si todas sus
hojas están al mismo nivel y todos sus
nodos interiores tienen cada uno 2 hijos.
B
T
C
N
D
E
3
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Arboles Binarios
Un árbol binario es degenerado si todos sus nodos excepto el último tienen
sólo un subárbol
A
A
B
B
N
T
C
D
PROPIEDAD
• Dado un árbol de grado
g y altura h, el número
máximo de nodo es
igual a:
h −1
N nodo = ∑ g
i
i =0
• Determinar el número
de nodos para el caso
g=2 (árbol binarios )
4
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Estructuras de Datos para Arboles Binarios
Data
A
B
A
IZQ
C
B
DER
C
E
T
T
E
S
S
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
DCLARACIÓN EN LENGUAJE C
typedef struct nodo {
int data;
struct nodo *izq, *der;
} Arbol;
5
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Recorrido de árboles binarios
Se denomina recorrido de un árbol al proceso que permite acceder una sola
vez a cada uno de los nodos del árbol. Cuando un árbol se recorre, el
conjunto completo de nodos se examina.
Recorrido pre-orden
1. Visitar nodo raíz
2. Recorrer el subárbol izquierdo en modo pre-orden
3. Recorrer el subárbol derecho en modo pre-orden
Recorrido in-orden
1. Recorrer el subárbol izquierdo en modo in-orden
2. Visitar nodo raíz
3. Recorrer el subárbol derecho en modo in-orden
Recorrido post-orden
1. Recorrer el subárbol izquierdo en modo post-orden
2. Recorrer el subárbol derecho en modo post-orden
3. Visitar nodo raíz
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Recorrido Pre-Orden
Recorrido Pre-Orden
1. Visitar nodo raíz
2. Recorrer el subárbol izquierdo en modo pre-orden
3. Recorrer el subárbol derecho en modo pre-orden
ABDHIEJKCFLMGNO
A
B
D
H
I
C
E
J
G
F
K
L
M
N
O
6
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Recorrido in-orden
Recorrido In-Orden
1. Recorrer el subárbol izquierdo en modo in-orden
2. Visitar nodo raíz
3. Recorrer el subárbol derecho en modo in-orden
HDIBJEKALFMCNGO
A
B
D
H
I
C
E
J
G
F
L
K
M
N
O
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Recorrido post-orden
Recorrido Post-Orden
1. Recorrer el subárbol izquierdo en modo post-orden
2. Recorrer el subárbol derecho en modo post-orden
3. Visitar nodo raíz
HIDJKEBLMFNOGCA
A
B
D
H
I
C
E
J
G
F
K
L
M
N
O
7
EJERCICIOS
• Dado un árbol binario de datos entero.
Implementar las siguientes funciones
Iterativas:
• Recorrido:
– Preorden, Inorden, Postorden
• Recorrido:
– Anchura Izquierdo-derecho
– Anchura Derecho-Izquierdo
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Arboles binarios de búsqueda
Un árbol de búsqueda es un TDA árbol en el que para cada nodo todas las claves
de cada subarbol satisfacen una y solo una condición de un conjunto de
Condiciones mutuamente excluyentes
Un árbol binario de búsqueda, es un árbol binario en el que dadas dos
Condiciones mutuamente exluyentes, para cada nodo, todas las claves
de su subárbol izquierdo satisfacen una condición y todas las de su subárbol
Derecho la otra.
Ki
EJEMPLO DE NÚMEROS ENTEROS:
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.
Siempre existen 2
excluyentes (< ; >)
relaciones
<Ki
>Ki
mutuamente
8
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
Escuela de Ingeniería Informática
Arboles binarios de búsqueda
Ki
<Ki
>Ki
H
D
B
A
C
L
F
E
N
J
G
I
K
M
PONTIFICIA
UNIVERSIDAD CATOLICA DE VALPARAISO
O
Escuela de Ingeniería Informática
DECLARACIÓN EN LENGUAJE C
typedef struct nodo {
int dato;
struct nodo *izq,*der;
} Arbol;
9
IMPLEMENTACIÓN ITERATIVA
ABB
¾INSERATAR
¾ELIMINAR DATO usando criterio del menor de
los mayores
10