rboles
Carlos Delgado Kloos M Carmen Fernndez Panadero Raquel M. Crespo
Garca Ingeniera Telemtica Univ. Carlos III de [email protected]
Java: rboles / 1
ndice ConceptoDefinicin no recursiva Definicin recursiva
Ejemplos
ImplementacinBasada en secuencias Basada en estructuras
enlazadasOperaciones bsicas Recorridos
TerminologaConceptos bsicos Propiedades
Casos especialesrboles de bsqueda binarios Montculos
binariosJava: rboles / 2
[email protected]
Cita "The structure of concepts is formally called a
hierarchy and since ancient times has been a basic structure for
all western knowledge. Kingdoms, empires, churches, armies have all
been structured into hierarchies. Tables of contents of reference
material are so structured, mechanical assemblies, computer
software, all scientific and technical knowledge is so
structured..." -- Robert M. Pirsig: Zen and the Art of Motorcycle
[email protected] Java: rboles / 3
rboles
Qu son?. Caractersticas
Un rbol es una estructura de datos no lineal que almacena los
elementos jerrquicamente Se puede definir de dos formas:Definicin
no-recursiva Definicin recursivaf T1 b g i
ae
T2
j k
Definicin [email protected] rboles 4
Definicin no recursivaUn rbol consiste en un conjunto de nodos y
un conjunto de aristas, de forma que:Se distingue un nodo llamado
raz A cada nodo h, excepto la raz, le llega una arista de otro nodo
p (p padre de h, h uno de los hijos de p) Para cada nodo hay un
camino (secuencia de aristas) nico desde la [email protected]
Java: rboles / 5
EjemploRaz (sin padre) El padre de h Un hijo de p
p h
hermano de h
Hojas Hojas (sin (sin hijos) hijos)[email protected]
Hojas Hojas (sin(sin hijos) hijos)Java: rboles / 6
EjemploRaz (sin padre) El padre de h Un hijo de p
p h
hermano de h
Hojas Hojas (sin (sin hijos) hijos)[email protected]
Hojas (sin(sin hijos) hijos)Java: rboles / 7
rboles
Definicin recursiva
a
b
c
d
e
f
g
h
i
j
k
[email protected]
Java: rboles/
8
rboles
Definicin recursiva
a
b
c
d
e
f
g
h
i
j
k
[email protected]
Java: rboles/
9
rboles
Definicin recursiva
a
b
c
d
e
f
g
h
i
j
k
[email protected]
Java: rboles/
10
rboles
Definicin recursiva
a
b
c
d
e
f
g
h
i
j
k
[email protected]
Java: rboles/
11
rboles
Definicin recursiva
a
b
c
d
e
f
g
h
i
j
k
[email protected]
Java: rboles/
12
Definicin recursiva (1)Un rbol esUn nodo o un nodo y subrboles
conectados con el nodo por medio de una arista a su raz
No incluye al rbol [email protected] Java: rboles / 13
Definicin recursiva (2)Un rbol esvaco o un nodo y cero o ms
subrboles no vacos conectados con el nodo por medio de una arista a
su raz
[email protected]
Java: rboles /
14
EjemplosSistema de ficheros Estructura de un libro o de un
documento rbol de decisin Expresiones aritmticas
[email protected]
Java: rboles /
15
EjemploExpresiones
()
() ()
() ()
()
(()(()())())[email protected] Java: rboles/ 16
TerminologaUn nodo es externo, si no tiene hijos (es hoja) Un
nodo es interno, si tiene uno o ms hijos Un nodo es ascendiente de
otro, si es padre de l o ascendiente de su padre. Un nodo es
descendiente de otro, si este es ascendiente del primero Los
descendientes de un nodo determinan un subrbol en el que ese nodo
hace el papel de [email protected] Java: rboles / 17
TerminologaUn camino de un nodo a otro, es una secuencia de
aristas consecutivas que llevan del primero al segundo.Su longitud
es el nmero de aristas que tiene.
La profundidad de un nodo es la longitud del camino de la raz a
ese nodo. La altura de un rbol es la profundidad del nodo ms
profundo. El tamao de un rbol es el nmero de nodos que
[email protected] Java: rboles / 18
Ejemploab f g c
Terminologa y propiedadesNodo Altura Profundidad Tamao Interno /
Externo Interno Interno
d h i
e j k
a b
3 1
0 1
11 3
cd e f
01 2 0
11 1 2
12 4 1
ExternoInterno Interno Externo Externo Externo Externo Interno
Externo
Tamao del rbol: 11 Altura del rbol: 3
gh i j k
00 0 1 0
22 2 2 3
11 1 2 1Java: Trees /
[email protected]
19
Terminologarbol ordenado
a b c c
ab
Un rbol es ordenado, si para cada nodo existe un orden lineal
para todos sus [email protected] Java: Trees / 20
Terminologarbol binario
Un rbol binario es un rbol ordenado, en el que cada nodo tiene
0, 1 2 hijos (el hijo izquierdo y el derecho).
[email protected]
Java: rboles /
21
Algoritmos bsicosTamao (nmero de nodos) Profundidad de un nodo
Altura RecorridosEuler Pre-, in- y post-orden
Suponemos rboles binarios para
[email protected]
Java: rboles /
22
ImplementacionesBasada en estructura enlazada Basada en
secuencia
[email protected]
Java: rboles /
23
Implementacin basada en enlaces
1
24 5 6
37
[email protected]
Java: rboles /
24
Implementacin basada en secuencia12 4 1 5 2 3 4 6 5 6 3p(raiz)=1
p(x.izq)=2*p(x) p(x.der)=2*p(x)+1
7 7Java: rboles / 25
[email protected]
Clase rbol binariopublic class BTree { protected BNode root;
BTree() { root = null; } BTree(Object info){ root = new
Bnode(info); }[email protected] Java: rboles/ 26
Clase rbol binariopublic int size() { int size = 0; if (root !=
null) size=root.size(); return size; } public int height(){ int h =
-1; if (root != null) h=root.height(); return h; }
[email protected]
Java: rboles/
27
... Clase rbol binariopublic void preorder() { if (root!=null)
root.preorder(); } public void inorder() { if (root!=null)
root.inorder(); } public void postorder() { if (root!=null)
root.postorder(); } }[email protected] Java: rboles/ 28
Clase nodo binario...class BNode { private Object info; private
BNode left; private BNode right; BNode() { this(null); }
BNode(Object info) { this(info,null,null); } BNode(Object info,
BNode l, BNode r) { this.info=info; left=l; right=r;
}[email protected] Java: Trees /
29
... Clase nodo binario...int size (){...;} int height (){...;}
void preorder (){...;} void inorder (){...;} void postorder
(){...;} }
[email protected]
Java: rboles/
30
Clase BNode: Sizeint size (){ int size = 1; if (left != null)
size += left.size(); if (right != null) size += right.size();
return size; }[email protected] Java: rboles/ 31
Clase BNode: Heightint height() { int hl = -1; int hr = -1; if
(left !=null) hl = left.height(); if (right !=null) hr =
right.height(); return 1 + Math.max(hl, hr); }[email protected]
Java: rboles/ 32
Recorrido de Euler
[email protected]
Java: rboles /
33
Recorrido preorden1
2Primero el nodo Despus sus hijos
(recursivamente)[email protected]
34 5 7Java: rboles / 34
6
Recorrido postorden7
1Primero sus hijos (recursivamente) Despus el
[email protected]
63 2 4Java: rboles / 35
5
Recorrido inorden (simtrico)2 1 Primero el hijo izquierdo
(recursivamente) Despus el nodo Primero el hijo derecho
(recursivamente)[email protected]
5 3 7
4
6Java: rboles / 36
(A+B)*(CD)*
+A B C
D
[email protected]
Java: rboles /
37
EjemploInfijo A+BA+BC (A+B)*(CD)[email protected]
Prefijo +AB+ABC *+ABCD
Posfijo AB+AB+C AB+CD*Java: rboles / 38
Actividad
Visualizacin de expresiones como rboles
http://www.cs.jhu.edu/~goodrich /dsa/05trees/Demo1/
[email protected]
Java: rboles /
39
Notacin postfijoCalculadoras HP Pila para almacenar operandos
Ej.: 3 5 + 6 2 *
2 5 4 6 32 8 [email protected] Java: rboles / 40
Clase BNode: preordervoid preorder (){ System.out.println(info);
if (left != null) left.preorder(); if (right != null)
right.preorder(); }[email protected] Java: rboles / 41
Clase BNode: postordervoid postorder (){ if (left != null)
left.postorder(); if (right != null) right.postorder();
System.out.println(info); }[email protected] Java: rboles / 42
Clase BNode: inordervoid inorder (){ if (left != null)
left.inorder(); System.out.println(info); if (right != null)
right.inorder(); }[email protected] Java: rboles / 43
Propiedades de rboles binariosSea E=Nmero de nodos externos
I=Nmero de nodos internos N=Tamao=E+I H=Altura
Se cumple E=I+1 H+1E2H HI2H-1
log2(N+1)-1H(N-1)/[email protected]
2*H+1N2H+1-1
Java: rboles /
44
rboles binarios de bsquedaUn rbol binario de bsqueda es un rbol
binario en el que para cada nodo n, todas las claves de los nodos
del subrbol izquierdo son menores que la clave de n (o iguales) y
todas las del subrbol derecho mayores (o iguales).
[email protected]
Java: rboles /
45
Ejemplo42 1 3 6 5 7Java: rboles / 46
1
82
93
[email protected]
Ejemplo81
6
9
42 [email protected]
75
2 3 4
3Java: rboles /
47
OperacionesBsqueda Insercin Eliminacin
[email protected]
Java: rboles /
48
BsquedaBuscamos el 3: 32: Subrbol derecho 3=3: Elemento
encontrado
4
21http://www.cosc.canterbury.ac.nz/
mukundan/dsal/[email protected]
83 5 6 7Java: rboles / 49
9
InsercinInsertar 6: 62: Subrbol derecho Hueco libre:
insertar
7
21 [email protected]
95 6Java: Trees / 50
Eliminacin (1)Eliminar 5: si es una hoja: eliminar si es un nodo
degenerado: reemplazar por el hijo
7
21 [email protected]
95 3
Java: Trees /
51
Eliminacin (2)Eliminar 2: si el nodo tiene 2 hijos: reemplazar
por el mayor del subrbol izquierdo, o el menor del subrbol
derecho
7
2 31 [email protected]
95
Java: Trees /
52
ActividadVer animacin de rboles binarios de
bsquedahttp://www.ibr.cs. tu-bs.de/courses/ ss98/audii/applets/
BST/BST-Example.html
[email protected]
Java: rboles /
53
Montculos (Heaps)Un montculo es un rbol binario en el que para
cada nodo n (excepto para el raz), su clave es mayor o igual que la
de su padre. Aplicaciones:Colas con prioridad Ordenacin
[email protected]
Java: rboles /
54
Ejemplo12 3 5 [email protected]
4 6 7Java: rboles / 55
9
Montculo completo12 3 [email protected]
4 5 6 9
7Java: rboles / 56
Implementacin basada en secuencias12 4 1 5 2 3 4 6 5 6
3p(root)=1 p(x.left)=2*p(x) p(x.right)=2*p(x)+1
7 7Java: Trees / 57
[email protected]
Insertar45 15 16 25 14 9 7 12 11 8Java: rboles / 58
6 20
[email protected]
Insertar45 15 16 25 14 9 7 12 11 8 2Java: rboles / 59
6 20
[email protected]
Insertar45 15 16 25 14 9 7 12 11 8 20Java: rboles / 60
6 2
[email protected]
Insertar45 15 16 25 14 9 7 12 11 8 20Java: rboles / 61
2 6
[email protected]
Insertar25 15 16 25 14 9 7 12 11 8 20Java: rboles / 62
4 6
[email protected]
Eliminar45 15 16 25 14 9 7 12 11 8Java: rboles / 63
6 20
[email protected]
Eliminar85 15 16 25 14 9 7 12 11Java: rboles / 64
6 20
[email protected]
Eliminar58 15 16 25 14 9 7 12 11Java: rboles / 65
6 20
[email protected]
ActividadProbar el formulario
dehttp://www.csse.monash.edu.au/~lloyd /tildeAlgDS/Priority-Q/
[email protected]
Java: rboles /
66
ActividadProbar el applet dehttp://www.cosc.canterbury.ac.nz/
mukundan/dsal/MinHeapAppl.html
[email protected]
Java: rboles /
67
