Materia:
Tópicos Avanzados de
Programación
Tema:
Árboles de Búsqueda Digital
Profr: M.C. Juan José Contreras Gaytán
Arboles de Búsqueda Digital
✓ Son estructuras de datos no lineales.
✓ Se utilizan para mejorar la búsqueda en árboles generales
✓ Si las llaves son enteros cada posición de un digito
determina una de 10 posibles hijos de un nodo.
✓ Si las llaves constan de caracteres alfabéticos, cada letra del
alfabeto determina rama en el árbol.
Tópicos Avanzados de Programación
ÁRBOLES DE BÚSQUEDA DIGITAL
LLAVES DE ENTRADA:
180, 185, 1867, 195, 207, 217, 2174, 21749, 217493, 226, 27, 274, 278, 279, 2796
307, 768
raiz
1
Si las llaves son enteros cada
posición de un digito
determina una de 10
posibles hijos de un nodo. 8 9
5
0 5 6
eok
eok eok 7
• eok = end of key
eok (apuntador al registro de datos)
ÁRBOLES DE BÚSQUEDA DIGITAL
LLAVES DE ENTRADA:
180, 185, 1867, 195, 207, 217, 2174, 21749, 217493, 226, 27, 274, 278, 279, 2796
307, 768
2
0 1 2 7
7 7 6 4 8 9 eok
eok
4 eok eok
eok eok eok 6
eok
9
eok
3 eok
eok
Tópicos Avanzados de Programación
ÁRBOLES DE BÚSQUEDA DIGITAL
LLAVES DE ENTRADA:
180, 185, 1867, 195, 207, 217, 2174, 21749, 217493, 226, 27, 274, 278, 279, 2796
307, 768
3 7
0 6
7 8
eok eok
BOSQUE DE ÁRBOLES DE BÚSQUEDA
DIGITAL
raiz 2 3 7
1
0 1 2 7 0 6
8 9 7 7 6 4 8 9
5 4 7 8
0 5 6 6
9
7 3
• El primer árbol en el bosque es apuntado por un
apuntador externo llamado raiz.
• Las raíces de los demás árboles en el bosque están
encadenadas en una lista lineal mediante el
apuntador brother.
• Cada lista de hermanos está organizado en una lista
lineal en forma ascendente mediante el campo
symbol.
ÁRBOLES DE BÚSQUEDA DIGITAL ORGANIZADO COMO UN BOSQUE
También los nodos hijos están en forma de lista enlazada
raiz
7
1 2 3
8 9 0 1 2 7 0
6
raiz
2 3 7
1
1 2 7 0
8 9 0
ÁRBOLES DE BÚSQUEDA DIGITAL
ESTRUCTURA DEL NODO LA CLASE NODO
class Nodo :
symbol
brother def __init__(self, valor):
[Link] = valor
[Link] = None
son [Link] = None
Cada nodo del árbol contiene 3 campos:
– symbol. que contiene un digito de
la llave
– son. apuntador al hijo del nodo
– brother. apuntador al hermano
siguiente del nodo en el árbol.
class ArbolDigital:
def __init__(self): LA CLASE ArbolDigital
[Link] = None #Raiz del bosque
def search(self, key):
p = [Link]
father = None
found = False
i=0
while (found == False):
q = None
paste = False
while p is not None and paste == False:
if [Link] >= key[i]:
paste = True
else:
q = p;
p = [Link]
found = True
if p is None or [Link] > key[i]:
[Link](p, q, father, i, key) #inserta registro de datos.
return "La llave " + key + " fue insertada!!"
elif i == len(key)-1:
return "La llave " + key + " fue encontrada!!" #registro encontrado
else:
father = p
p = [Link]
found = False
i+=1
return
La Clase ArbolDigital
def insert(self, p, q, father, i, key):
s = Nodo(key[i])
[Link] = p
if [Link] is None:
[Link] = s
elif q is not None:
[Link] = s
elif father is None:
[Link] = s
else:
[Link] = s
# Inserta los simbolos restantes de la llave
j=i
while j < len(key)-1:
father = s
s = Nodo(key[j+1])
[Link] = s
[Link] = None
j+=1
El Método Principal
def main():
arbol = ArbolDigital()
opcion = 0
while True:
opcion = int(input("MENU\n" + "1. Ingresar Llave\n" + "2. Salir\n" + "Opcion:" ))
if opcion == 1:
key=input("Llave: ")
#Validar que solo sean digitos
if ([Link]()):
#Coloca cada digito en el árbol de busqueda digital
print([Link](key))
else:
print("Escribir solo digitos!!")
if opcion == 2:
break #Salir del ciclo
if __name__ == "__main__":
main()
CARACTERÍSTICAS:
• La representación de una tabla de llaves como árbol es eficiente
cuando cada nodo tiene relativamente pocos hijos.
• Sin embargo, si el conjunto de llaves es denso dentro del
conjunto de todas las llaves posibles, es decir, si la mayoría de los
nodos tendrá un número muy grande de hijos, el costo del
proceso de búsqueda se vuelve lento.
Tópicos Avanzados de Programación
Aplicación del Árbol de Búsqueda Digital
Se puede usar como método de búsqueda. Por ejemplo:
Desarrollar un programa en Python que acepte como entrada una serie de
números enteros que representan el número de control del estudiante,
adicionalmente asociar su correo electrónico y celular.
La matrícula deberá ser procesada digito a digito, los dígitos los almacena en
un árbol de búsqueda e inserción digital junto con los datos adicionales
(correo, celular); el programa presentará un menú para insertar los datos del
estudiante, otra opción para buscar los datos dentro del bosque
mostrándolos en pantalla.
Tópicos Avanzados de Programación
class Estudiante:
def __init__(self, matricula, correo, celular):
[Link] = matricula
[Link] = correo
[Link] = celular
def __str__(self):
return "[" + [Link] + ", " + [Link] +
", " + [Link] + "]"