Download Árboles Binarios de Búsqueda - Departamento de Ingeniería

Programación de sistemas
Árboles:
Árboles Binarios de
Búsqueda
Departamento de Ingeniería Telemática
1
Contenidos
• Concepto de árbol binario de búsqueda
• Operaciones
– Búsqueda
– Inserción
– Eliminación
2
1
Árboles binarios de búsqueda:
Concepto
• Un árbol binario de búsqueda es un árbol
binario en el que para cada nodo n,
 todas las claves de los nodos del
subárbol izquierdo son
menores que la clave de n (o iguales)
 y todas las del subárbol derecho
mayores (o iguales).
3
Ejemplo
4
1
2
8
2
1
3
6
9
3
3
5
7
4
2
Ejemplo
8
1
6
7
4
5
2
1
3
9
2
3
4
5
Operaciones
• Búsqueda
• Inserción
• Eliminación
6
3
Búsqueda
Buscamos el “3”:
• 3<4: Subárbol izquierdo
• 3>2: Subárbol derecho
• 3=3: Elemento encontrado
4
2
1
8
3
6
5
9
7
http://www.cosc.canterbury.ac.nz/mukundan/dsal/BST.html
7
Inserción
Insertar “6”:
• 6<7: Subárbol izquierdo
• 6>2: Subárbol derecho
• Hueco libre: insertar
7
2
1
9
5
3
6
8
4
Eliminación (1)
Eliminar “5”:
• si es una hoja: eliminar
• si es un nodo degenerado:
reemplazar por el hijo
7
2
1
9
5
3
3
9
Eliminación (2)
Eliminar “2”:
• si el nodo tiene 2 hijos:
reemplazar por
• el mayor del subárbol
izquierdo, o
• el menor del subárbol
derecho
7
2
3
1
9
5
3
10
5
Ejemplo
http://www.ibr.cs.tu-bs.de/courses/ss98/audii/applets/BST/BST-Example.html 11
Programación de sistemas
Árboles:
Montículos
Departamento de Ingeniería Telemática
1
6
Montículos (Heaps)
• Un montículo binario es un árbol binario
completo en el que cada nodo tiene una
clave mayor(*) o igual que la de su padre.
– Normalmente, un montículo se refiere a
montículo binario
– * También podría definirse como menor o igual
(el orden es arbitrario)
• Aplicaciones:
– Colas con prioridad
– Ordenación
13
Montículos: propiedades
• Un montículo cumple dos propiedades
– Propiedad de montículo: para cada nodo n
(excepto para el raíz), su clave es mayor o igual
que la de su padre.
– Completo
14
7
Ejemplo:
propiedad de montículo
1
2
3
4
5
6
9
8
7
Pero no es completo
15
Ejemplo:
Montículo completo
1
2
3
8
4
5
6
9
7
16
8
Implementación
basada en secuencias
1
p(root)=1
p(x.left)=2*p(x)
p(x.right)=2*p(x)+1
2
3
4
5
1
2
6
3
4
5
7
6
7
17
Insertar
4
5
15
16
25 14
6
9
7
12 11
20
8
18
9
Insertar
4
5
15
16
6
9
25 14
7
12 11
20
8
2
19
Insertar
4
5
15
16
25 14
6
9
7
12 11
2
8
20
20
10
Insertar
4
5
15
16
2
9
25 14
7
12 11
6
8
20
21
Insertar
2
5
15
16
25 14
4
9
7
12 11
6
8
20
22
11
Eliminar
4
5
15
16
6
9
25 14
7
12 11
20
8
23
Eliminar
8
4
5
15
16
25 14
6
9
7
20
12 11
24
12
Eliminar
5
8
15
16
25 14
6
9
7
20
12 11
25
Ejemplo
Montículo - Cola con prioridad
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Priority-Q/
13
Ejemplo
Montículo - Cola con prioridad
http://www.cosc.canterbury.ac.nz/mukundan/dsal/MinHeapAppl.html
14