Hoja de trabajo RBT
Enviado por Lindsay Pinto • 10 de Mayo de 2021 • Informes • 1.257 Palabras (6 Páginas) • 61 Visitas
Trabajo Cooperativo en sesión sincrónica
- Publicar Hoja de Trabajo con los problemas a resolver en el Aula Bloque Neón
- Usar Collaborate / Zoom para conformación de grupos de trabajo (parejas conformadas aleatoriamente). Trabajo en grupos durante 5 minutos por problema.
- Usar Padlet para la publicación de las respuestas trabajadas por los grupos.
Cada grupo publica sus respuestas propuestas en el Padlet de la sesión.
- Regreso a Sala General (Re-agrupamiento del curso).
- Discusión de resultados de los problemas publicados en el Padlet entre el profesor y los estudiantes.
Código de Referencia:
https://github.com/ISIS1225DEVS/ISIS1225-Lib/blob/master/DISClib/DataStructures/bst.py
https://github.com/ISIS1225DEVS/ISIS1225-Lib/blob/master/DISClib/DataStructures/bstnode.py
https://github.com/ISIS1225DEVS/ISIS1225-Lib/blob/master/DISClib/DataStructures/rbt.py
https://github.com/ISIS1225DEVS/ISIS1225-Lib/blob/master/DISClib/DataStructures/rbtnode.py
Funcionalidad Básica del TAD Tabla de Símbolos Ordenada
Implementaciones: Estructura de Datos Binary Search Tree (BST) y Red-Black Tree (RBT)
Operación Ordered Map | Descripción |
newMap(type, cmpfunction=None) | Crea una tabla de simbolos ordenada vacia |
put(map, key, value) | Ingresa una pareja llave-valor. Si la llave ya existe, se reemplaza el valor. |
get(map, key) | Retorna la pareja llave-valor, cuya llave sea igual a key. |
remove(map, key) | Elimina la pareja llave-valor, donde llave sea igual a key |
contains(map, key) | Retorna True si la llave key se encuentra en la tabla o False en caso contrario. |
size(map) | Retorna el número de parejas llave-valor en la tabla de simbolos |
height(map) | Retorna la altura del arbol |
isEmpty(map) | Informa si la tabla de simbolos se encuentra vacia |
keySet(map) | Retorna una lista con las llaves de la tabla |
valueSet(map) | Retorna una lista con los valores de la tabla |
minKey(map) | Retorna la menor llave de la tabla de simbolos |
maxKey(map) | Retorna la mayor llave de la tabla de simbolos |
deleteMin(map) | Encuentra y elimina la pareja llave-valor con menor llave |
deleteMax(map) | Encuentra y elimina la pareja llave-valor con mayor llave |
floor(map, key) | Retorna la llave mas grande en la tabla de simbolos, menor o igual a la llave key |
ceiling(map, key) | Retorna la llave mas pequeña en la tabla de simbolos, mayor o igual a la llave key |
select(map, pos) | Retorna la siguiente llave a la k-esima llave mas pequeña de la tabla |
rank(map, key) | Retorna el número de llaves en la tabla estrictamente menores que key |
keys(map, keylo, keyhi) | Retorna todas las llaves del arbol que se encuentren entre [keylo, keyhi] |
values(map, keylo, keyhi) | Retorna todos los valores del arbol cuyas llaves se encuentren entre [keylo, keyhi] |
1. Árbol BST: Las llaves son comparables usando la función cmpfunction(key1,key2). Tenga en cuenta que en un BST la inserción de una llave se debe hacer con su valor asociado.
1.1 Problema: Agregue la siguiente secuencia de llaves usando el algoritmo de inserción en un BST inicialmente vacio: {100, 50, 150, 200, 30, 10, 180, 160, 170, …}
La gráfica es una guía para facilitar la construcción del BST. Por cada llave que agregue al BST cambiar el color del nodo y el color del texto de su llave.
Después de agregar todas las llaves a la gráfica puede eliminar todos los nodos y conexiones que NO fueron utilizados para ver la estructura real del BST.
[pic 1]
1.2 Problema: Dar el peso (size) del BST:
El peso del BST es 9 debido a que hay 9 nodos en total.
1.3 Problema: Dar la altura del BST:
La altura del BST sería 5 pues existen 5 arcos al lado derecho.
1.4 Problema: ¿Cuál es el número de comparaciones en el peor caso para buscar una llave en el BST?
El número de comparaciones en el peor de los casos es 5
1.5 Problema: ¿El BST resultante es un árbol ordenado?
Si el BST resultante sí es un árbol ordenado.
1.6 Problema: ¿El BST resultante es un árbol balanceado?
El BST resultante no está balanceado pues la diferencia en las alturas del hijo izquierdo y derecho no es < = a 1.
...