Download Árboles binarios - Pontificia Universidad Católica de Valparaíso

Árboles binarios
Franco Guidi Polanco
Escuela de Ingeniería Industrial
Pontificia Universidad Católica de Valparaíso, Chile
[email protected]
Árbol: definición
v Árbol (del latín arbor –oris):
§  Planta perenne, de tronco leñoso y elevado, que se
ramifica a cierta altura del suelo.
§  (otras, ver Real Academia Española…)
Franco Guidi Polanco
2
Árbol: definición (cont.)
v Árbol:
§  Grafo conexo, no orientado y acíclico.
C
E
A
B
D
H
Franco Guidi Polanco
3
Árbol: definición (cont.)
v Árbol:
§  Una estructura de datos accesada desde un nodo raíz.
Cada nodo es ya sea una hoja o un nodo interno. Un
nodo interno tiene uno o más nodos hijos, y se le llama
padre de sus nodos hijos.
§  Un árbol es, ya sea:
•  un conjunto vacío, o
•  una raíz con cero
o más árboles
Franco Guidi Polanco
4
Hojas y nodos internos
v Una hoja es cualquier nodo que tiene sus hijos
vacíos.
v Un nodo interno es cualquier nodo con al menos
un hijo no vacío.
a
b
d
Hojas
Franco Guidi Polanco
Nodos internos
c
e
f
g
h
5
Representación de un árbol
raíz
a
subárbol
b
f
g
c
h
d
j
i
l
e
subárbol
m
k
subárbol
subárbol
Franco Guidi Polanco
6
Representación de un árbol (cont.)
a
b
f
g
c
h
d
j
i
l
e
k
m
subárbol de nodo e
subárboles de
nodo b
subárboles de
nodo c
Franco Guidi Polanco
7
Nodos padres e hijos
v Las raíces de los subárboles de un árbol son hijos
de la raíz del árbol.
v Existe un arco desde cada nodo a cada uno de sus
hijos, y se dice que este nodo es padre de sus
hijos.
Franco Guidi Polanco
8
Ruta y largo de una ruta
v Si n1, n2,... nk es una secuencia de nodos en un
árbol, de modo que ni es padre de ni + 1, para
1<=i<=k, entonces esta secuencia se llama ruta
desde n1 a nk.
v El largo de esta ruta es k.
a
b
d
n1
c
e
f
g
Franco Guidi Polanco
n2
n3
h
9
Ancestros y descendientes
v Si existe una ruta desde un nodo A a un nodo B,
entonces A es ancestro de B y B es
descendiente de A.
v Luego, todos los nodos de un árbol son
descendientes de la raíz del árbol, mientras que la
raíz es el ancestro de todos los nodos.
Franco Guidi Polanco
10
Altura
v La altura de un nodo M de un árbol corresponde
al número de nodos en la ruta desde la raíz hasta
M.
v La altura de un árbol corresponde a la altura del
nodo más profundo.
a
b
c
Altura del
nodo=2
Altura del árbol=4
d
e
f
g
Franco Guidi Polanco
h
11
Niveles
v Todos los nodos de altura d están en el nivel d en
el árbol.
v La raíz está en el nivel 1, y su altura es 1.
a
Nivel 1
b
Nivel 2
Nivel 3
Nivel 4
Franco Guidi Polanco
d
c
e
f
g
h
12
Árboles binarios
v Un A.B. está constituido por un conjunto finito de
elementos llamados nodos.
v Un árbol binario:
§  no tiene nodos (está vacío); o
§  tiene un nodo llamado raíz, junto con otros dos árboles
binarios llamados subárboles derecho e izquierdo
de la raíz.
Nota: Una parte importante del material presentado en esta sección
fue elaborado por Marcelo Silva F.
Franco Guidi Polanco
13
Representación de un árbol binario (I)
raíz
subárbol izquierdo
a
b
d
subárbol derecho
c
e
f
g
Franco Guidi Polanco
h
14
Representación de un árbol binario (II)
raíz
a
b
d
subárbol izquierdo
Franco Guidi Polanco
subárbol derecho
c
e
f
g
h
15
Igualdad de árboles binarios
v Para ser iguales, dos árboles deben tener tanto la
misma estructura, como el mismo contenido.
a
b
Franco Guidi Polanco
≠
a
b
16
Árboles binarios llenos
v Un árbol binario lleno es aquel en que cada nodo
es un nodo interno con dos hijos no vacíos, o una
hoja.
a
b
d
a
c
e
f
g
No es A.B. lleno
Franco Guidi Polanco
b
c
e
h
f
g
h
Es A.B. lleno
17
Árboles binarios completos
v Un árbol binario completo tiene una forma
restringida, que se obtiene al ser llenado de
izquierda a derecha. En un A.B. Completo de altura
d, todos los niveles, excepto posiblemente el nivel
d están completamente llenos.
a
b
Es un A.B. completo
pero no es un A.B. lleno
d
Franco Guidi Polanco
c
e
f
18
Número de nodos en un árbol binario
v El máximo número de nodos en el nivel i de un
árbol binario es 2(i-1).
v El máximo número de nodos en un árbol binario
de altura K es 2(K)-1.
Franco Guidi Polanco
19
Representación de árboles binarios mediante
nodos y referencias
a
b
c
d
e
f
Franco Guidi Polanco
20
Diagrama de clases de un árbol binario
v Diagrama de clases árbol binario de enteros:
ABB
insert(i:int)
find(d:Data):boolean
delete(i:int)
ABBNode
1..1 data:int
root
left
Franco Guidi Polanco
setData(i:int)
getData():int
setLeft(n:ABBNode)
getLeft():ABBNode
setRight(n:ABBNode)
getRight():ABBNode
isLeaf():boolean
right
21
Diagrama de objetos de un árbol binario
:ABB
root:ABBNode
data:20
:ABBNode
:ABBNode
data:32
data:7
:ABBNode
data:2
Franco Guidi Polanco
:ABBNode
data:15
:ABBNode
data:40
22
Representación de árboles binarios mediante
arreglos
v Si la raíz de un subárbol se almacena en A[i], su
hijo izquierdo se almacena en A[2*i], y su hijo
derecho en A[2*i+1].
a
b
c
d
e
f
g
1
2
3
4
a b c d
Franco Guidi Polanco
5
6
7
e f
8
9
10
h
11
12
13
14
15
16
g h
23
Recorrido de árboles binarios
v Un recorrido es cualquier proceso destinado a
visitar los nodos de un árbol binario en un
determinado orden.
v Cualquier recorrido que visite cada nodo
exactamente una vez, se denomina una
enumeración de los nodos del árbol.
v Recorridos de enumeración a analizar:
§  Preorden
§  Inorden
§  Postorden
Franco Guidi Polanco
24
Recorrido en Preorden
Dado un árbol binario:
1) Visitar su raíz.
2) Recorrer en preorden su subárbol izquierdo.
3) Recorrer en preorden su subárbol derecho.
1
2
Franco Guidi Polanco
3
25
Código para recorrido Preorden
void preorder(BinNode rt) // rt es la raíz del subarbol
{
if (rt==null)
return;
// subarbol vacío
visit(rt)
// hace algo con el nodo
preorder(rt.left());
preorder(rt.right());
}
Franco Guidi Polanco
26
Ejemplo de recorrido en Preorden
a
1
2
b
3
d
c
e
f
g
h
i
j
k
a b d c e f g i j k h
Franco Guidi Polanco
27
Recorrido en Inorden
Dado un árbol binario:
1) Recorrer en inorden su subárbol izquierdo.
2) Visitar su raíz.
3) Recorrer en inorden su subárbol derecho.
2
1
Franco Guidi Polanco
3
28
Código para recorrido Inorden
void inorder(BinNode rt) // rt es la raíz del subarbol
{
if (rt==null)
return;
inorder(rt.left());
visit(rt)
inorder(rt.right());
// subarbol vacío
// hace algo con el nodo
}
Franco Guidi Polanco
29
Ejemplo de recorrido en Inorden
a
2
1
b
3
d
c
e
f
g
h
i
j
k
d b a e c g j i k f h
Franco Guidi Polanco
30
Recorrido en Postorden
Dado un árbol binario:
1) Recorrer en postorden su subárbol izquierdo.
2) Recorrer en postorden su subárbol derecho.
3) Visitar su raíz.
3
1
Franco Guidi Polanco
2
31
Código para recorrido Postorden
void postorder(BinNode rt) // rt es la raíz del subarbol
{
if (rt==null)
return; // subarbol vacío
postorder(rt.left());
postorder(rt.right());
visit(rt) // hace algo con el nodo
}
Franco Guidi Polanco
32
Ejemplo de recorrido en Postorden
a
3
1
b
2
d
c
e
f
g
h
i
j
k
d b e j k i g hf c a
Franco Guidi Polanco
33
Árbol binario de búsqueda
v Supongamos que tenemos un conjunto de n
elementos que pueden ser ordenados por alguna
clave.
v En un árbol binario de búsqueda (ABB), todos
los nodos almacenados en el subárbol izquierdo de
un nodo cuyo valor clave es C tienen claves
menores que C, mientras que todos los nodos
ubicados en el subárbol derecho tienen claves
mayores que C.
Franco Guidi Polanco
34
Ejemplos de árboles binarios de búsqueda
a
b
c
<c
d
>c
c
e
f
No es ABB
c
Definición de ABB
b
a
e
d
f
Es ABB
Franco Guidi Polanco
35
Ingreso de elementos a un ABB
{ 10, 5, 7, 15, 14, 12, 18 }
{ 15, 18, 14, 5, 10, 12, 7 }
15
10
14
5
15
7
14
12
Franco Guidi Polanco
18
5
18
10
7
12
36
ABB de referencia
ABB
insert(e:Element)
find(key:int):Element
delete(i:int):Element
Element
ABBNode
1
root
left
Franco Guidi Polanco
setData(e:Element)
getData():Element
setLeft(n:ABBNode)
getLeft():ABBNode
setRight(n:ABBNode)
getRight():ABBNode
isLeaf():boolean
1
data
{interface}
getKey():int
right
37
Ingreso de elementos a un ABB (cont.)
private BinNode insert (BinNode rt, Element val)
{
if (rt == null)
return new BinNode(val);
Element it = (Element)rt.element();
if (it.key() > val.key())
rt.setLeft(insert(rt.left(), val));
else
rt.setRight(insert(rt.right(), val));
return rt;
}
Franco Guidi Polanco
38
Características del ingreso de elementos a un ABB
v Los elementos agregados a un ABB siempre son
incorporados inicialmente como hojas.
v Un conjunto de elementos dado puede generar
diversos ABB, dependiendo del orden en que son
ingresados.
Franco Guidi Polanco
39
Recorrido Inorden en ABB
15
10
14
5
15
7
14
5
18
10
12
5
7
Franco Guidi Polanco
18
10 12 14 15 18
7
5
12
7
10 12 14 15 18
40
Características del recorrido Inorden de un ABB
v Si bien existen muchos ABBs posibles para un
mismo conjunto de elementos, el recorrido
Inorden de todos estos árboles siempre entrega el
conjunto ordenado de menor a mayor.
Franco Guidi Polanco
41
Búsqueda en ABB
Para hallar un elemento con clave C, en un
árbol A:
v Si la raíz del árbol A almacena C, la búsqueda
termina exitosamente.
v Si C es menor que el valor de la raíz de A, buscar
en el subárbol izquierdo. Si C es mayor que el
valor de la raíz, buscar en el subárbol derecho.
v La búsqueda termina al hallar el valor C, o al
pretender buscar en un subárbol vacío.
Franco Guidi Polanco
42
Búsqueda en ABB (cont.)
Elem find(BinNode rt, int key) {
if (rt == null)
return null;
Element it = (Element)rt.element();
if ((int)it.key() > key)
return find(rt.left(), key);
else if (it.key() == key)
return it;
else
return find(rt.right(), key);
}
Franco Guidi Polanco
43
Ejemplo de búsqueda en ABB
10
10
5
5
15
7
14
18
12
Buscar 12
Búsqueda exitosa
Franco Guidi Polanco
15
7
14
18
12
Buscar 16
Búsqueda infructuosa
44
Eliminación de elementos de un ABB
Se pueden presentar tres casos:
v El elemento no existe.
v El elemento es una hoja o tiene a lo más un hijo.
v El elemento tiene dos hijos.
Franco Guidi Polanco
45
Eliminar nodo que es una hoja o tiene a lo más un
hijo
10
10
5
15
7
14
12
Franco Guidi Polanco
7
15
18
14
18
12
46
Ejemplo eliminación de nodo con dos hijos
10
10
5
15
7
14
5
18
16
7
16
18
17
17
Franco Guidi Polanco
14
El menor de los
elementos
mayores
(Nodo más a la
izquierda del
subárbol derecho)
47
Eliminar nodo con dos hijos
1.  Hallar el nodo que contiene el menor de los
elementos mayores del nodo a eliminar (el
elemento más a la izquierda de su subárbol
derecho)
2.  Reemplazar los datos del nodo eliminar con
los del nodo hallado.
3.  Eliminar el nodo hallado, que tiene a lo más
un hijo, con el procedimiento descrito
previamente.
Franco Guidi Polanco
48
Utilidad de los árboles binarios de búsqueda
v Al buscar, el ABB permite descartar a priori un
subconjunto de elementos, en forma análoga a la
búsqueda binaria en arreglos ordenados.
v El ABB presenta además la ventaja de poder ser
implementado con punteros (estructura dinámica).
v La incorporación y eliminación de elementos al
ABB es mas rápida que en arreglos ordenados.
Franco Guidi Polanco
49
Importancia de una estructura balanceada en los
ABB
v La estructura de un ABB es importante al
momento de realizar búsquedas en él.
18
10
15
5
3
15
7
14
14
En el peor de los casos se
hacen 3 iteraciones para
una búsqueda.
Franco Guidi Polanco
10
18
7
5
3
En el peor de los
casos se hacen 7
iteraciones para
una búsqueda.
50