Download Árboles

Estructuras de datos y algoritmos
Oscar Bedoya.
[email protected]
http://eisc.univalle.edu.co/~oscarbed/Estructuras/
Edificio 331, 2º piso, E.I.S.C.
Arboles
Nodo
La anatomía de un nodo en un árbol binario es la siguiente:
A
Puntero al
subarbol
izquierdo
Puntero al
subarbol
derecho
Árboles
A
B
H
Árbol con 8 nodos
D
C
E
G
F
Arboles
Raiz
Es el nodo que no es apuntado por ningún otro nodo
A
D
B
H
C
E
G
F
Arboles
Padre
X es el padre de Y si X apunta a Y
A
A es el padre de B y de D
D
B
H
C
E
G
B es el padre de H y C
F
H no es padre de nadie
A no es el padre de H!
Arboles
Hijo
Y es el hijo de X si X apunta a Y
A
B y D son hijos de A
D
B
H
C
E
G
H y C son hijos de B
F
H no es un hijo de A
Arboles
Hoja
Una hoja es un nodo que no tiene hijos
A
D
B
H
C
E
G
F
Arboles
Nodo no terminal
Es un nodo que no es hoja
A
D
B
H
C
E
G
F
Arboles
Camino
Es el conjunto de nodos que se deben visitar con el propósito de
llegar a un nodo especifico
Un árbol siempre se examina hacia abajo
Los apuntadores derecho e izquierdo de cualquier nodo apuntan
al árbol derecho o izquierdo que siguen a ese nodo. Nunca
apuntan a los nodos precedentes
Árboles
A
El camino A->D->F se
presenta en el árbol
D
B
C
F
E
G
El camino
G->E->D->A->B->C no
se da en el camino
Arboles
Longitud
Es el número de nodos que se deben recorrer para pasar de un
nodo a otro
Árboles
A
D
B
C
F
E
G
La longitud entre A y G es 3
La longitud entre A y A es 0
La longitud entre D y F es 1
Arboles
Ancestro
Un nodo X es ancestro de Y si existe una camino ente X y Y
Árboles
A
D
B
C
F
E
G
Es G un ancestro de B?
Es B un ancestro de E?
Es A un ancestro de F?
Arboles
Nivel
Cada nodo tiene un nivel dentro de un árbol binario. Por definición
el nodo raíz tiene un nivel 0 y los demás nodos tiene el nivel de su
padre más 1
Árboles
Nivel 0
A
Nivel 1
D
B
C
F
E
G
Nivel 2
Nivel 3
Arboles
Grado de un nodo
Es el número de hijos
El grado de un nodo terminal siempre es 0
En un árbol binario el grado de cada nodo varia entre 0 y 2
Árboles
A
D
B
C
F
E
G
El grado de A es 2
El grado de D es 2
El grado de E es 1
El grado de C, G y F es 0
Arboles
Altura de un árbol
Es el nivel de la hoja o de las hojas que están más distantes de la
raíz
Árboles
A
La altura del árbol es 3
D
B
C
F
E
G
Árboles
A
D
B
C
I
J
K
F
E
H
G
Cuántos nodos tiene
Cuál es el nodo raíz
Cuáles son los nodos no terminales
Cuáles son las hojas
Cuál es el grado del nodo E
Cuál es el nivel del nodo I
Cuál es la longitud entre A y K
Se presente el camino B-A-D-F
Cuál es la altura del árbol
Arboles
Árbol binario
Un árbol binario es un conjunto finito de elementos que está vacío o
dividido en tres subconjuntos separados.
El primer subconjunto contiene un elemento único llamado raíz del
árbol. Los otros dos subconjuntos son por si mismos árboles binarios y
se les conoce como subárboles izquierdo y derecho del árbol original.
Un subárbol izquierdo o derecho puede estar vacío. Cada elemento de
un árbol binario se denomina nodo del árbol
Árboles
A
E
C
J
Es este un árbol binario?
D
B
F
G
Arboles
Árbol estrictamente binario
Si cada nodo que no es una hoja en un árbol binario tiene subárboles
izquierdo y derecho que no están vacíos, se clasifica como árbol
estrictamente binario
Árboles
A
Es este un árbol
estrictamente binario?
D
B
E
J
F
G
Árboles
A
Es este un árbol
estrictamente binario?
D
B
E
H
J
F
G
Arboles
Árbol binario completo
Un árbol que es estrictamente binario y tiene todas sus hojas en el nivel
d, donde d es la profundad del árbol, es un árbol binario completo
Árboles
A
Es este un árbol binario
completo?
D
B
E
J
F
G
Árboles
A
H
Es este un árbol binario
completo?
D
B
G
E
F
Arboles
Árbol binario completo
Un árbol binario completo tiene 2l nodos en cada nivel l, donde l varia
entre 0 y d
totalNodos =
20
+
21
+
22
+...+
2d
= j 0 2 j = 2d+1 -1
d
•Cuántos nodos no terminales tiene un árbol binario completo?
•Cuál es la profundidad de un árbol binario completo con T nodos?
Arboles
Árbol de búsqueda binaria
Un árbol binario en el que los elementos del subárbol
izquierdo de un nodo n son menores que el contenido
de n, y que todos los elementos en el subárbol derecho
de n son mayores o iguales que el contenido de n se
denomina árbol de búsqueda binaria
Si un árbol de búsqueda binaria se recorre en orden
(izquierdo, raíz, derecho), los números se imprimen en
orden ascendente
Árboles
20
Es este un árbol de
búsqueda binaria?
30
1
24
21
34
26
Arboles
Árbol balanceado
Un árbol binario balanceado o AVL, es aquel en el que
las alturas de los dos subárboles de cada nodo nunca
difieren en más de 1.
El balance de un nodo en un árbol binario se define
como la altura de su subárbol izquierdo menos la
altura de su subárbol derecho
Arboles
Árbol balanceado
Un árbol binario balanceado o AVL, es aquel en el que
el balance para cada nodo es -1, 0 ó 1
Árboles
A
-1
1
B
0
B
D
-1
E
Se indican los balances para
cada nodo
1
F
0
G
0
Árboles
A
D
B
B
Indique los balances de cada
nodo, y determine si el árbol
es o no, AVL
E
F
G
Árboles
-1
A
-2
0
D
B
0
0
B
E
-1
F
0
G
Árboles
A
D
B
B
Indique los balances de cada
nodo, y determine si el árbol
es o no, AVL
F
E
G
Árboles
A
-1
1
1
D
B
0
-1
B
E
0
F
0
G
Árboles
A
D
B
B
F
E
E
E
Indique los balances de cada
nodo, y determine si el árbol
es o no, AVL
G
G
Árboles
-2
A
0
1
B
D
0
+2
C
E
1
H
0
I
1
F
0
F
1
G
0
J
Árboles
Formas de recorrer un árbol
•Preorden
•Inorden
•posorden
Árboles
Preorden
Examinar el dato del nodo raíz
Recorrer el árbol izquierdo en preorden
Recorrer el árbol derecho en preorden
Árboles
A
Recorrer el árbol en preorden
C
B
D
E
F
G
Árboles
A
ABDECFG
C
B
D
E
F
G
Árboles
Recorrer el árbol en preorden
10
15
5
3
1
4
17
14
7
9
16
20
Árboles
10
15
5
3
1
17
14
7
4
10-5-3-1-4-7-915-14-17-16-20
9
16
20
Árboles
Inorden
Recorrer el árbol izquierdo en inorden
Examinar el dato del nodo raíz
Recorrer el árbol derecho en inorden
Árboles
Recorrer el árbol en inorden
10
12
5
3
7
11
15
Árboles
10
3-5-7-10-11-12-15
12
5
3
7
11
15
Árboles
A
C
B
D
H
I
G
F
E
J
K
L
Árboles
A
HDIBEAJFCKGL
C
B
D
H
I
G
F
E
J
K
L
Árboles
Posorden
Recorrer el árbol izquierdo en posorden
Recorrer el árbol derecho en posorden
Examinar el dato del nodo raíz
Árboles
A
C
B
D
H
G
F
E
I
-Recorrer el árbol en
posorden
J
K
L
Árboles
A
HIDEBJFKLGCA
C
B
D
H
I
G
F
E
J
K
L
Árboles
A
Muestre el resultado de
recorrer el árbol en
preorden, inorden y
posorden
C
B
E
D
F
G
I
J
Árboles
A
Preorden
C
B
ABCDFGEIJ
E
D
F
G
I
J
Árboles
A
Inorden
C
B
BAFDGCIEJ
E
D
F
G
I
J
Árboles
A
Posorden
C
B
BFGDIJECA
E
D
F
G
I
J