Order Map - Árboles

Como usar la documentación

Para leer la guía de uso de la documentación, por favor diríjase a la sección Guía de documentación.

Elementos

bst_node.py

Estructura que contiene la información a guardar en una nodo de un árbol binario

new_node(key, value)

Crea una nueva entrada (de tipo bst_node) de un árbol binario con una llave y un valor dados.

El nodo es creado con los siguientes atributos:

key: llave del nodo
value: valor del nodo
size: tamaño del subárbol (inicialmente 1)
left: hijo izquierdo del nodo (inicialmente None)
right: hijo derecho del nodo (inicialmente None)

Parameters:

key (any) – llave del nodo
value (any) – valor del nodo

Returns:

nodo creado

Return type:

bst_node

Example:

# App/logic.py
from DataStructures.Tree import bst_node as bn

# Crea una nueva entrada (nodo) de un árbol binario
node = bn.new_node(1, "uno")
print(node)
# Salida esperada:
# { "key": 1, "value": "uno", "size": 1, "left": None, "right": None }

get_value(my_node)

Obtiene el valor value de un nodo recibido.

Parameters:

my_node (bst_node) – nodo del cual se quiere obtener el valor

Returns:

valor del nodo

Return type:

any

Example:

# App/logic.py
from DataStructures.Tree import bst_node as bn

# Crea una nueva entrada (nodo) de un árbol binario
node = bn.new_node(1, "uno")
print(node)
# Salida esperada:
# { "key": 1, "value": "uno", "size": 1, "left": None, "right": None }

# Obtiene el valor del nodo
value = bn.get_value(node)
print(value)
# Salida esperada:
# "uno"

get_key(my_node)

Obtiene la llave key de un nodo recibido.

Parameters:

my_node (bst_node) – nodo del cual se quiere obtener la llave

Returns:

llave del nodo

Return type:

any

Example:

# App/logic.py
from DataStructures.Tree import bst_node as bn

# Crea una nueva entrada (nodo) de un árbol binario
node = bn.new_node(1, "uno")
print(node)
# Salida esperada:
# { "key": 1, "value": "uno", "size": 1, "left": None, "right": None }

# Obtiene la llave del nodo
key = bn.get_key(node)
print(key)
# Salida esperada:
# 1

rbt_node.py

new_node(key, value, color=0)

Crea una nueva entrada (de tipo :ref:` color:0 - rojo color:1 - negro Args:

value: El valor asociado a la llave key: la llave asociada a la pareja size: El tamaño del subarbol que cuelga de este nodo color: El color inicial del nodo

Returns:: Un nodo con la pareja <llave, valor>
Raises:: Exception

is_red(my_node)

Informa si un nodo es rojo Args:

my_node: El nodo a revisar

Returns:: True si el nodo es rojo, False de lo contrario
Raises:: Exception

get_value(my_node)

Retorna el valor asociado a una pareja llave valor Args:

my_node: El nodo con la pareja llave-valor

Returns:: El valor almacenado en el nodo
Raises:: Exception

get_key(my_node)

Retorna la llave asociado a una pareja llave valor Args:

my_node: El nodo con la pareja llave-valor

Returns:: La llave almacenada en el nodo
Raises:: Exception

change_color(my_node, color)

Cambia el color de un nodo Args:

my_node: El nodo a cambiar color: El nuevo color del nodo

Returns:: None
Raises:: Exception

Implementaciones

binary_search_tree.py

new_map()

Crea una nueva tabla de simbolos (map) ordenada basada en un árbol binario de búsqueda (BST).

La tabla de simbolos es creada con los siguientes atributos:

root: raiz del árbol (inicialmente None)

Returns:

tabla de simbolos creada

Return type:

binary_search_tree

Example:

# App/logic.py
from DataStructures.Tree import binary_search_tree as bst

# Crea un arbol vacío
map = bst.new_map()
print(map)
# Salida esperada: { "root": None }

put(my_bst, key, value)

Agrega un nuevo nodo llave-valor a un árbol binario de búsqueda (BST). Si la llave ya existe, se actualiza el value del nodo.

Esta función llama a la función insert_node para agregar el nodo en la posición correcta del árbol de manera recursiva.

Parameters:

my_bst (binary_search_tree) – árbol binario de búsqueda donde se quiere agregar el nodo
key (any) – llave del nodo
value (any) – valor del nodo

Returns:

árbol binario de búsqueda actualizado

Return type:

binary_search_tree

Example:

# App/logic.py
from DataStructures.Tree import binary_search_tree as bst

# Crea un arbol vacío
map = bst.new_map()
print(map)
# Salida esperada: { "root": None }

# Agrega un nuevo nodo al árbol
map = bst.put(map, 1, "uno")
print(map)
# Salida esperada:
# {
#     "root": {
#        "key": 1,
#        "value": "uno",
#        "size": 1,
#        "left": None,
#        "right": None
#     }
# }

Test Scenarios:

Agrega un nuevo nodo a un árbol vacío

# App/logic.py
from DataStructures.Tree import binary_search_tree as bst

# Crea un arbol vacío
map = bst.new_map()
print(map)
# Salida esperada: { "root": None }

# Agrega un nuevo nodo al árbol
map = bst.put(map, 1, "uno")
print(map)
# Salida esperada:
# {
#     "root": {
#        "key": 1,
#        "value": "uno",
#        "size": 1,
#        "left": None,
#        "right": None
#     }
# }

Agrega un nuevo nodo a un árbol no vacío

# App/logic.py
from DataStructures.Tree import binary_search_tree as bst

# Crea un arbol vacío
map = bst.new_map()
print(map)
# Salida esperada: { "root": None }

# Agrega un nuevo nodo al árbol
map = bst.put(map, 2, "dos")

# Agrega otro nodo al árbol
map = bst.put(map, 1, "uno")

print(map)
# Salida esperada:
# {
#     "root": {
#        "key": 2,
#        "value": "dos",
#        "size": 2,
#        "left": {
#           "key": 1,
#           "value": "uno",
#           "size": 1,
#           "left": None,
#           "right": None
#        },
#        "right": None
#     }
# }

Agregar un nodo con una llave ya existente

# App/logic.py
from DataStructures.Tree import binary_search_tree as bst

# Crea un arbol vacío
map = bst.new_map()
print(map)
# Salida esperada: { "root": None }

# Agrega un nuevo nodo al árbol
map = bst.put(map, 2, "dos")

# Agrega otro nodo al árbol
map = bst.put(map, 1, "uno")

# Agrega otro nodo al árbol con una llave ya existente
map = bst.put(map, 1, "uno modificado")

print(map)
# Salida esperada:
# {
#     "root": {
#        "key": 2,
#        "value": "dos",
#        "size": 2,
#        "left": {
#           "key": 1,
#           "value": "uno modificado",
#           "size": 1,
#           "left": None,
#           "right": None
#        },
#        "right": None
#     }
# }

insert_node(root, key, value)

Inserta un nuevo nodo llave-valor en el árbol binario de búsqueda (BST) de manera recursiva.

Esta función es llamada por la función put.

Parameters:

root (bst_node) – raiz del árbol donde se quiere agregar el nodo
key (any) – llave del nodo
value (any) – valor del nodo

Returns:

raiz del árbol binario de búsqueda actualizado

Return type:

bst_node

get(my_bst, key)

Busca un nodo en el árbol binario de búsqueda (BST) y devuelve su valor.

Esta función llama a la función get_node para buscar el nodo en el árbol de manera recursiva.

Parameters:

my_bst (binary_search_tree) – árbol binario de búsqueda donde se quiere buscar el nodo
key (any) – llave del nodo a buscar

Returns:

valor del nodo encontrado o None si no se encuentra

Return type:

any

Example:

# App/logic.py
from DataStructures.Tree import binary_search_tree as bst

# Crea un arbol vacío
map = bst.new_map()
print(map)
# Salida esperada: { "root": None }

# Agrega un nuevo nodo al árbol
map = bst.put(map, 1, "uno")
print(map)
# Salida esperada:
# {
#     "root": {
#        "key": 1,
#        "value": "uno",
#        "size": 1,
#        "left": None,
#        "right": None
#     }
# }

Test Scenarios:

Busca un nodo en un árbol vacío

# App/logic.py
from DataStructures.Tree import binary_search_tree as bst

# Crea un arbol vacío
map = bst.new_map()
print(map)
# Salida esperada: { "root": None }

# Busca un nodo en el árbol vacío
value = bst.get(map, 1)
print(value)
# Salida esperada: None

Busca un nodo en un árbol no vacío - llave existente

# App/logic.py
from DataStructures.Tree import binary_search_tree as bst

# Crea un arbol vacío
map = bst.new_map()
print(map)
# Salida esperada: { "root": None }

# Agrega un nuevo nodo al árbol
map = bst.put(map, 2, "dos")
map = bst.put(map, 1, "uno")
map = bst.put(map, 3, "tres")

# Busca un nodo en el árbol no vacío
value = bst.get(map, 2)
print(value)
# Salida esperada: "dos"

Busca un nodo en un árbol no vacío - llave no existente

# App/logic.py
from DataStructures.Tree import binary_search_tree as bst

# Crea un arbol vacío
map = bst.new_map()
print(map)
# Salida esperada: { "root": None }

# Agrega un nuevo nodo al árbol
map = bst.put(map, 2, "dos")
map = bst.put(map, 1, "uno")
map = bst.put(map, 3, "tres")

# Busca un nodo en el árbol no vacío
value = bst.get(map, 4)
print(value)
# Salida esperada: None
# (No existe el nodo con llave 4)

get_node(root, key)

Busca un nodo en el árbol binario de búsqueda (BST) de manera recursiva.

Esta función es llamada por la función get.

Parameters:

root (bst_node) – raiz del árbol donde se quiere buscar el nodo
key (any) – llave del nodo a buscar

Returns:

nodo encontrado o None si no se encuentra

Return type:

bst_node

remove(my_bst, key)

Elimina la pareja llave-valor que coincida con``key``.

Usa la función remove_node() para eliminar la pareja

Parameters:

my_bst (binary_search_tree) – El arbol de búsqueda
key (any) – La llave asociada a la pareja a eliminar

Returns:

El arbol sin la pareja key-value

Return type:

binary_search_tree

remove_node(root, key)

Elimina la pareja llave-valor que coincida con``key``.

Es usada en la función remove()

Parameters:

root (bst_node) – La raiz del arbol a examinar
key (any) – La llave asociada a la pareja a eliminar

Returns:

El arbol sin la pareja key-value

Return type:

bst_node

contains(my_bst, key)

Informa si la llave key se encuentra en la tabla de hash.

Usa la función get() para buscar la llave en el arbol

Parameters:

my_bst (binary_search_tree) – El arbol de búsqueda
key (any) – La llave a buscar

Returns:

True si la llave está presente, False en caso contrario

Return type:

bool

size(my_bst)

Retorna el número de entradas en la tabla de simbolos

Usa la función size_tree() para contar el número de elementos

Parameters:: my_bst (binary_search_tree) – El arbol de búsqueda
Returns:: El número de elementos en la tabla
Return type:: int

size_tree(root)

Retornar el número de entradas en la a partir del nodo root

Es usada en la función size()

Parameters:: root (bst_node) – La raiz del arbol a examinar
Returns:: El número de elementos en la tabla
Return type:: int

is_empty(my_bst)

Informa si la tabla de simbolos se encuentra vacia.

Parameters:: my_bst (binary_search_tree) – El arbol de búsqueda
Returns:: True si la tabla es vacía, False en caso contrario
Return type:: bool

key_set(my_bst)

Retorna una lista con todas las llaves de la tabla.

Usa la función key_set_tree() para construir la lista de llaves

Parameters:: my_bst (binary_search_tree) – El arbol de búsqueda
Returns:: Una lista con todas las llaves de la tabla
Return type:: single_linked_list

value_set(my_bst)

Retorna una lista con los valores de la tabla.

Usa la función value_set_tree() para construir la lista de valores

Parameters:: my_bst (binary_search_tree) – El arbol de búsqueda
Returns:: Una lista con todos los valores de la tabla
Return type:: single_linked_list

get_min(my_bst)

Retorna la llave mas pequeña de la tabla de simbolos

Usa la función get_min_node() para encontrar la llave más a la izquierda

Parameters:: my_bst (binary_search_tree) – El arbol de búsqueda
Returns:: La llave más a la izquierda
Return type:: any

get_min_node(root)

Retorna la llave mas pequeña de la tabla de simbolos

Es usada en la función get_min()

Parameters:: root (bst_node) – La raiz del arbol a examinar
Returns:: La llave más a la izquierda
Return type:: any

get_max(my_bst)

Retorna la llave mas grande de la tabla de simbolos

Usa la función get_max_node() para encontrar la llave más grande de del arbol

Parameters:: my_bst (binary_search_tree) – El arbol de búsqueda
Returns:: La llave más a la derecha
Return type:: any

get_max_node(root)

Retorna la llave mas grande de la tabla de simbolos

Es usada en la función get_max() Usa la función get_max_node() para encontrar la llave más grande

Parameters:: root (bst_node) – La raiz del arbol a examinar
Returns:: La llave más a la derecha
Return type:: any

delete_min(my_bst)

Encuentra y remueve la llave mas pequeña de la tabla de simbolos y su valor asociado.

Usa la función delete_min_tree() para eliminar la llave más pequeña

Parameters:: my_bst (binary_search_tree) – El arbol de búsqueda
Returns:: El arbol de búsqueda sin la llave más pequeña
Return type:: binary_search_tree

delete_min_tree(root)

Encuentra y remueve la llave mas pequeña de la tabla de simbolos y su valor asociado

Es usada en la función delete_min() Usa la función delete_min_tree() para eliminar la llave más pequeña

Parameters:: root (bst_node) – La raiz del arbol a examinar
Returns:: Retorna la raiz del arbol sin la llave más pequeña
Return type:: bst_node

delete_max(my_bst)

Encuentra y remueve la llave mas grande de la tabla de simbolos y su valor asociado.

Usa la función delete_max_tree() para eliminar la llave más grande

Parameters:: my_bst (binary_search_tree) – El arbol de búsqueda
Returns:: El arbol de búsqueda sin la llave más grande
Return type:: binary_search_tree

delete_max_tree(root)

Encuentra y remueve la llave mas grande de la tabla de simbolos y su valor asociado.

Es usada en la función delete_max() Usa la función delete_max_tree() para eliminar la llave más grande

Parameters:: root (bst_node) – La raiz del arbol a examinar
Returns:: Retorna la raiz del arbol sin la llave más grande
Return type:: bst_node

floor(my_bst, key)

Retorna la llave que precede a la llave key en la tabla de simbolos.

Si la llave existe, retorna la misma llave. Si no existe, retorna la llave predecedente más cercana como si la llave key existiera en la tabla. Por ejemplo, si la tabla contiene las llaves [1, 3, 5, 7, 9] y se busca la llave 6, la función retornará 5.

Usa la función floor_key() para encontrar la llave predecesora a key

Parameters:

my_bst (binary_search_tree) – El arbol de búsqueda
key (any) – La llave de búsqueda

Returns:

La llave predecesora a key

Return type:

any

floor_key(root, key)

Retorna la llave que precede a la llave key en la tabla de simbolos.

Si la llave existe, retorna la misma llave. Si no existe, retorna la llave predecedente más cercana como si la llave key existiera en la tabla.

Es usada en la función floor() Usa la función floor_key() para encontrar la llave predecesora a key

Parameters:

root (bst_node) – La raiz del arbol a examinar
key (any) – La llave de búsqueda

Returns:

La llave predecesora a key

Return type:

any

ceiling(my_bst, key)

Retorna la llave que sucede a la llave key en la tabla de simbolos.

Si la llave existe, retorna la misma llave. Si no existe, retorna la llave sucesora más cercana como si la llave key existiera en la tabla. Por ejemplo, si la tabla contiene las llaves [1, 3, 5, 7, 9] y se busca la llave 6, la función retornará 7.

Usa la función ceiling_key() para encontrar la llave sucesora a key

Parameters:

my_bst (binary_search_tree) – El arbol de búsqueda
key (any) – La llave de búsqueda

Returns:

La llave sucesora a key

Return type:

any

ceiling_key(root, key)

Retorna la llave que sucede a la llave key en la tabla de simbolos.

Si la llave existe, retorna la misma llave. Si no existe, retorna la llave sucesora más cercana como si la llave key existiera en la tabla. Por ejemplo, si la tabla contiene las llaves [1, 3, 5, 7, 9] y se busca la llave 6, la función retornará 7.

Es usada en la función ceiling() Usa la función ceiling_key() para encontrar la llave sucesora a key

Parameters:

root (bst_node) – La raiz del arbol a examinar
key (any) – La llave de búsqueda

Returns:

La llave sucesora a key

Return type:

any

select(my_bst, pos)

Retorna la siguiente llave a la k-esima llave de izquierda a derecha de la tabla de simbolos.

Usa la función select_key() para encontrar la llave en la posición pos

Parameters:

my_bst (binary_search_tree) – El arbol de búsqueda
pos (int) – la pos-esima llave de izquierda a derecha

Returns:

La llave en la posición pos

Return type:

any

select_key(root, key)

Retorna la siguiente llave a la k-esima llave de izquierda a derecha de la tabla de simbolos.

Es usada en la función select() Usa la función select_key() para encontrar la llave en la posición pos

Parameters:

root (bst_node) – La raiz del arbol a examinar
key (int) – la llave de búsqueda

Returns:

La llave en la posición pos

Return type:

bst_node

rank(my_bst, key)

Retorna el número de llaves en la tabla que son estrictamente predecesoras a key Por ejemplo, si la tabla contiene las llaves [1, 3, 5, 7, 9] y se busca la llave 6, la función retornará 3.

Usa la función rank_keys() para encontrar el número de llaves predecesoras a key

Parameters:

my_bst (binary_search_tree) – El arbol de búsqueda
key (any) – la llave de busqueda

Returns:

El número de llaves

Return type:

int

rank_keys(root, key)

Retorna el número de llaves en la tabla que son estrictamente predecesoras a key Por ejemplo, si la tabla contiene las llaves [1, 3, 5, 7, 9] y se busca la llave 6, la función retornará 3.

Es usada en la función rank() Usa la función rank_keys() para encontrar el número de llaves predecesoras a key

Parameters:

root (bst_node) – La raiz del arbol a examinar
key (any) – la llave de busqueda

Returns:

El número de llaves

Return type:

int

height(my_bst)

Retorna la altura del arbol de busqueda

Usa la función height_tree() para encontrar la altura del arbol

Parameters:: my_bst (binary_search_tree) – El arbol de búsqueda
Returns:: La altura del arbol
Return type:: int

height_tree(root)

Retorna la altura del arbol de busqueda

Es usada en la función height() Usa la función height_tree() para encontrar la altura del arbol

Parameters:: root (bst_node) – La raiz del arbol a examinar
Returns:: La altura del arbol
Return type:: int

keys(my_bst, key_initial, key_final)

Retorna todas las llaves del arbol que se encuentren entre [key_initial, key_final].

Usa la función keys_range() para encontrar las llaves en el rango especificado

Parameters:

my_bst (binary_search_tree) – La tabla de simbolos
key_initial (any) – limite inferior
key_final (any) – limite superior

Returns:

Las llaves en el rago especificado

Return type:

single_linked_list

keys_range(root, key_initial, key_final, list_key)

Retorna todas las llaves del arbol que se encuentren entre [key_initial, key_final].

Es usada en la función keys() Usa la función keys_range() para encontrar las llaves en el rango especificado

Parameters:

root (bst_node) – La raiz del arbol a examinar
key_initial (any) – limite inferior
key_final (any) – limite superior
list_key (single_linked_list) – La lista de respuesta

Returns:

Las llaves en el rago especificado

Return type:

single_linked_list

values(my_bst, key_initial, key_final)

Retorna todas los valores del arbol que se encuentren entre [key_initial, key_final]

Usa la función values_range() para encontrar los valores en el rango especificado

Parameters:

my_bst (binary_search_tree) – La tabla de simbolos
key_initial (any) – limite inferior
key_final (any) – limite superior

Returns:

Las llaves en el rago especificado

Return type:

single_linked_list

values_range(root, key_initial, key_final, list_value)

Retorna todas los valores del arbol que se encuentren entre [key_initial, key_final]

Es usada en la función values() Usa la función values_range() para encontrar los valores en el rango especificado

Parameters:

root (bst_node) – La raiz del arbol a examinar
key_lo (any) – limite inferior
key_hi (any) – limite superior
list_values (single_linked_list) – La lista de respuesta

Returns:

Las llaves en el rago especificado

Return type:

single_linked_list

default_compare(key, element)

Función de comparación por defecto. Compara una llave con la llave de un elemento llave-valor.

Parameters:

key (any) – Llave a comparar
element (bst_node) – entry a comparar

Returns:

0 si son iguales, 1 si key > la llave del element, -1 si key < que la llave del element

Return type:

int

Code:

from DataStructures.Tree import bst_node as bst_node

def default_compare(key, element):
   if key == bst_node.get_key(element):
      return 0
   elif key > bst_node.get_key(element):
      return 1
   return -1

red_black_tree.py

new_map()

Crea una tabla de simbolos ordenada basa en un árbol rojo-negro (RBT) vacia

Se crea una tabla de simbolos ordenada con los siguientes atributos:

root: Raíz del árbol. Inicializado en None
type: Tipo de árbol. Inicializado en “RBT”

Returns:: La tabla de simbolos ordenada sin elementos
Return type:: red_black_tree

put(my_rbt, key, value)

Ingresa una pareja llave,valor. Si la llave ya existe, se reemplaza el valor.

Usa la funcion insert_node()

Parameters:

my_rbt (red_black_tree) – El RBT
key (any) – La llave asociada a la pareja
value (any) – El valor asociado a la pareja

Returns:

El arbol con la nueva pareja

Return type:

red_black_tree

insert_node(root, key, value)

Ingresa una pareja llave,valor. Si la llave ya existe, se reemplaza el valor.

Es usada en la función insert()

Parameters:

root (rbt_node) – La raiz del arbol
key (any) – La llave asociada a la pareja
value (any) – El valor asociado a la pareja

Returns:

El arbol con la nueva pareja

Return type:

rbt_node

get(my_rbt, key)

Retorna el valor con llave igual a key

Usa la función get_node() para buscar la llave en el arbol

Parameters:

my_rbt (reb_black_tree) – El arbol de búsqueda
key (any) – La llave asociada a la pareja

Returns:

La pareja el valor de la llave key. None en caso de no ser encontrada

Return type:

any

get_node(root, key)

Retorna el valor de la llave igual a key

Parameters:

root (rbt_node) – La raiz del arbol
key (any) – La llave asociada a la pareja a buscar

Returns:

El valor de la llave key. None en caso de no ser encontrada

remove(my_rbt, key)

Elimina la pareja llave-valor que coincida con``key``.

Usa la función remove_node() para eliminar la pareja

Parameters:

my_rbt (reb_black_tree) – El arbol de búsqueda
key (any) – La llave asociada a la pareja a eliminar

Returns:

El arbol sin la pareja key-value

Return type:

reb_black_tree

remove_node(root, key)

Elimina la pareja llave-valor que coincida con``key``.

Es usada en la función remove() Usa la funcion remove_node()

Parameters:

root (rbt_node) – La raiz del arbol a examinar
key (any) – La llave asociada a la pareja a eliminar

Returns:

El arbol sin la pareja key-value

Return type:

rbt_node

contains(my_rbt, key)

Informa si la llave key se encuentra en la tabla de hash.

Usa la función get() para buscar la llave en el arbol

Parameters:

my_rbt (reb_black_tree) – El arbol de búsqueda
key (any) – La llave a buscar

Returns:

True si la llave está presente, False en caso contrario

Return type:

bool

size(my_rbt)

Retorna el número de entradas en la tabla de simbolos

Usa la función size_tree() para contar el número de elementos

Parameters:: my_rbt (reb_black_tree) – El arbol de búsqueda
Returns:: El número de elementos en la tabla
Return type:: int

is_empty(my_rbt)

Informa si la tabla de simbolos se encuentra vacia.

Parameters:: my_rbt (reb_black_tree) – El arbol de búsqueda
Returns:: True si la tabla es vacía, False en caso contrario
Return type:: bool

key_set(my_rbt)

Retorna una lista con todas las llaves de la tabla.

Usa la función key_set_tree() para construir la lista de llaves

Parameters:: my_rbt (reb_black_tree) – El arbol de búsqueda
Returns:: Una lista con todas las llaves de la tabla
Return type:: single_linked_list

key_set_tree(root, key_list)

Construye una lista con las llaves de la tabla. Se recorre el arbol en inorder

Es usada en la función key_set()

Si root no es None, se recorre el arbol en inorder, primero el hijo izquierdo, luego la raiz y finalmente el hijo derecho

Parameters:

root (rbt_node) – La raiz del arbol a examinar
key_list (single_linked_list) – La lista de respuesta

Returns:

Una lista con todos las llaves

Return type:

single_linked_list

value_set(my_rbt)

Retorna una lista con los valores de la tabla.

Usa la función value_set_tree() para construir la lista de valores

Parameters:: my_rbt (reb_black_tree) – El arbol de búsqueda
Returns:: Una lista con todos los valores de la tabla
Return type:: single_linked_list

value_set_tree(root, key_list)

Construye una lista con los valorers de la tabla. Se recorre el arbol en inorder

Es usada en la función value_set()

Si root no es None, se recorre el arbol en inorder, primero el hijo izquierdo, luego la raiz y finalmente el hijo derecho

Parameters:

root (rbt_node) – La raiz del arbol a examinar
value_list (single_linked_list) – La lista de respuesta

Returns:

Una lista con todos los valores

Return type:

single_linked_list

get_min(my_rbt)

Retorna la llave mas a la izquierda de la tabla de simbolos

Important

Dependiendo de la definición de la función de comparación, la llave más a la izquierda puede ser la menor o la mayor.

Usa la función left_key_node() para encontrar la llave más a la izquierda

Parameters:: my_rbt (reb_black_tree) – El arbol de búsqueda
Returns:: La llave más a la izquierda
Return type:: any

get_min_node(root)

Retorna la llave mas a la izquierda de la tabla de simbolos

Important

Dependiendo de la definición de la función de comparación, la llave más a la izquierda puede ser la menor o la mayor.

Es usada en la función get_min() Usa la función left_key_tree() para encontrar la llave más a la izquierda

Parameters:: root (rbt_node) – La raiz del arbol a examinar
Returns:: La llave más a la izquierda
Return type:: any

get_max(my_rbt)

Retorna la llave mas a la derecha de la tabla de simbolos

Important

Dependiendo de la definición de la función de comparación, la llave más a la derecha puede ser la menor o la mayor.

Usa la función right_key_node() para encontrar la llave más a la derecha del arbol

Parameters:: my_rbt (reb_black_tree) – El arbol de búsqueda
Returns:: La llave más a la derecha
Return type:: any

get_max_node(root)

Retorna la llave mas a la derecha de la tabla de simbolos

Important

Dependiendo de la definición de la función de comparación, la llave más a la derecha puede ser la menor o la mayor.

Es usada en la función get_max() Usa la función get_max_node() para encontrar la llave más a la derecha

Parameters:: root (rbt_node) – La raiz del arbol a examinar
Returns:: La llave más a la derecha
Return type:: any

delete_min(my_rbt)

Encuentra y remueve la llave mas a la izauierda de la tabla de simbolos y su valor asociado.

Important

Dependiendo de la definición de la función de comparación, la llave más a la izquierda puede ser la menor o la mayor.

Usa la función delete_min_node() para eliminar la llave más a la izquierda

Parameters:: my_rbt (reb_black_tree) – El arbol de búsqueda
Returns:: El arbol de búsqueda sin la llave más a la izquierda
Return type:: reb_black_tree

delete_max(my_rbt)

Encuentra y remueve la llave mas a la derecha de la tabla de simbolos y su valor asociado.

Important

Dependiendo de la definición de la función de comparación, la llave más a la derecha puede ser la menor o la mayor.

Usa la función delete_max_node() para eliminar la llave más a la derecha

Parameters:: my_rbt (reb_black_tree) – El arbol de búsqueda
Returns:: El arbol de búsqueda sin la llave más a la derecha
Return type:: reb_black_tree

delete_max_node(root)

Encuentra y remueve la llave mas a la derecha de la tabla de simbolos y su valor asociado.

Important

Dependiendo de la definición de la función de comparación, la llave más a la derecha puede ser la menor o la mayor.

Es usada en la función delete_max() Usa la función delete_max_node() para eliminar la llave más a la derecha

Parameters:: root (rbt_node) – La raiz del arbol a examinar
Returns:: Retorna la raiz del arbol sin la llave más a la derecha
Return type:: rbt_node

floor(my_rbt, key)

Retorna la llave que precede a la llave key en la tabla de simbolos.

Si la llave existe, retorna la misma llave. Si no existe, retorna la llave predecedente más cercana como si la llave key existiera en la tabla. Por ejemplo, si la tabla contiene las llaves [1, 3, 5, 7, 9] y se busca la llave 6, la función retornará 5.

Usa la función floor_key() para encontrar la llave predecesora a key

Parameters:

my_rbt (reb_black_tree) – El arbol de búsqueda
key (any) – La llave de búsqueda

Returns:

La llave predecesora a key

Return type:

any

floor_key(root, key)

Retorna la llave que precede a la llave key en la tabla de simbolos.

Si la llave existe, retorna la misma llave. Si no existe, retorna la llave predecedente más cercana como si la llave key existiera en la tabla.

Es usada en la función floor() Usa la función floor_key() para encontrar la llave predecesora a key

Parameters:

root (rbt_node) – La raiz del arbol a examinar
key (any) – La llave de búsqueda

Returns:

La llave predecesora a key

Return type:

any

ceiling(my_rbt, key)

Retorna la llave que sucede a la llave key en la tabla de simbolos.

Si la llave existe, retorna la misma llave. Si no existe, retorna la llave sucesora más cercana como si la llave key existiera en la tabla. Por ejemplo, si la tabla contiene las llaves [1, 3, 5, 7, 9] y se busca la llave 6, la función retornará 7.

Usa la función ceiling_key() para encontrar la llave sucesora a key

Parameters:

my_rbt (reb_black_tree) – El arbol de búsqueda
key (any) – La llave de búsqueda

Returns:

La llave sucesora a key

Return type:

any

ceiling_key(root, key)

Retorna la llave que sucede a la llave key en la tabla de simbolos.

Si la llave existe, retorna la misma llave. Si no existe, retorna la llave sucesora más cercana como si la llave key existiera en la tabla. Por ejemplo, si la tabla contiene las llaves [1, 3, 5, 7, 9] y se busca la llave 6, la función retornará 7.

Es usada en la función ceiling() Usa la función ceiling_key() para encontrar la llave sucesora a key

Parameters:

root (rbt_node) – La raiz del arbol a examinar
key (any) – La llave de búsqueda

Returns:

La llave sucesora a key

Return type:

any

select(my_rebt, pos)

Retorna la siguiente llave a la k-esima llave de izquierda a derecha de la tabla de simbolos.

Usa la función select_key() para encontrar la llave en la posición pos

Parameters:

my_rbt (reb_black_tree) – El arbol de búsqueda
pos (int) – la pos-esima llave de izquierda a derecha

Returns:

La llave en la posición pos

Return type:

any

select_key(root, key)

Retorna la siguiente llave a la k-esima llave de izquierda a derecha de la tabla de simbolos.

Es usada en la función select() Usa la función select_key() para encontrar la llave en la posición pos

Parameters:

root (rbt_node) – La raiz del arbol a examinar
key (int) – la llave de búsqueda

Returns:

La llave en la posición pos

Return type:

rbt_node

rank(my_rbt, key)

Retorna el número de llaves en la tabla que son estrictamente predecesoras a key Por ejemplo, si la tabla contiene las llaves [1, 3, 5, 7, 9] y se busca la llave 6, la función retornará 3.

Usa la función rank_keys() para encontrar el número de llaves predecesoras a key

Parameters:

my_rbt (reb_black_tree) – El arbol de búsqueda
key (any) – la llave de busqueda

Returns:

El número de llaves

Return type:

int

rank_keys(root, key)

Retorna el número de llaves en la tabla que son estrictamente predecesoras a key Por ejemplo, si la tabla contiene las llaves [1, 3, 5, 7, 9] y se busca la llave 6, la función retornará 3.

Es usada en la función rank() Usa la función rank_keys() para encontrar el número de llaves predecesoras a key

Parameters:

root (rbt_node) – La raiz del arbol a examinar
key (any) – la llave de busqueda

Returns:

El número de llaves

Return type:

int

height(my_rbt)

Retorna la altura del arbol de busqueda

Usa la función height_tree() para encontrar la altura del arbol

Parameters:: my_rbt (reb_black_tree) – El arbol de búsqueda
Returns:: La altura del arbol
Return type:: int

height_tree(root)

Retorna la altura del arbol de busqueda

Es usada en la función height() Usa la función height_tree() para encontrar la altura del arbol

Parameters:: root (rbt_node) – La raiz del arbol a examinar
Returns:: La altura del arbol
Return type:: int

keys(my_rbt, key_initial, key_final)

Retorna todas las llaves del arbol que se encuentren entre [key_initial, key_final].

Important

Dependiendo de la definición de la función de comparación y del orden de las llaves, el rango puede ser [key_final, key_initial].

Si la función de comparación es la función por defecto, el rango es [key_initial, key_final]. Si la función de comparación es la función inversa, el rango es [key_final, key_initial].

Usa la función keys_range() para encontrar las llaves en el rango especificado

Parameters:

my_rbt (reb_black_tree) – La tabla de simbolos
key_initial (any) – limite inferior
key_final (any) – limite superior

Returns:

Las llaves en el rago especificado

Return type:

single_linked_list

values(my_rbt, key_initial, key_final)

Retorna todas los valores del arbol que se encuentren entre [key_initial, key_final]

Important

Dependiendo de la definición de la función de comparación y del orden de las llaves, el rango puede ser [key_final, key_initial].

Si la función de comparación es la función por defecto, el rango es [key_initial, key_final]. Si la función de comparación es la función inversa, el rango es [key_final, key_initial].

Usa la función values_range() para encontrar los valores en el rango especificado

Parameters:

my_rbt (reb_black_tree) – La tabla de simbolos
key_initial (any) – limite inferior
key_final (any) – limite superior

Returns:

Las llaves en el rago especificado

Return type:

single_linked_list

values_range(root, key_initial, key_final, value_list)

Retorna todas los valores del arbol que se encuentren entre [key_initial, key_final]

Important

Dependiendo de la definición de la función de comparación y del orden de las llaves, el rango puede ser [key_final, key_initial].

Si la función de comparación es la función por defecto, el rango es [key_initial, key_final]. Si la función de comparación es la función inversa, el rango es [key_final, key_initial].

Es usada en la función values() Usa la función values_range() para encontrar los valores en el rango especificado

Parameters:

root (rbt_node) – La raiz del arbol a examinar
key_lo (any) – limite inferior
key_hi (any) – limite superior
list_values (single_linked_list) – La lista de respuesta

Returns:

Las llaves en el rago especificado

Return type:

single_linked_list

rotate_left(node_rbt)

Rotación izquierda para compensar dos enlaces rojos consecutivos

Parameters:: node_rbt – Nodo raiz del arbol a rotar
Returns:: El arbol rotado
Return type:: rbt_node

rotate_right(node_rbt)

Rotación a la derecha para compensar un hijo rojo a la derecha

Parameters:: node_rbt – Nodo raiz del arbol a rotar
Returns:: El arbol rotado
Return type:: rbt_node

flip_node_color(node_rbt)

Cambia el color de un nodo

Parameters:: node_rbt (rbt_node) – El nodo a cambiar
Returns:: El nodo con el color opuesto
Return type:: rbt_node

flip_colors(node_rbt)

Cambia el color de un nodo y de sus dos hijos

Parameters:: node_rbt (rbt_node) – El nodo a cambiar
Returns:: El nodo con el color opuesto
Return type:: rbt_node

is_red(node_rbt)

Indica si un nodo del arbol es rojo

Parameters:: node_rbt (rbt_node) – El nodo a examinar
Returns:: True si el nodo es rojo, False de lo contrario
Return type:: bool

size_tree(root)

Retornar el número de entradas en la a partir del nodo root

Es usada en la función size()

Parameters:: root (rbt_node) – La raiz del arbol a examinar
Returns:: El número de elementos en la tabla
Return type:: int

keys_range(root, key_initial, key_final, list_key)

Retorna todas las llaves del arbol que se encuentren entre [key_initial, key_final].

Important

Dependiendo de la definición de la función de comparación y del orden de las llaves, el rango puede ser [key_final, key_initial].

Si la función de comparación es la función por defecto, el rango es [key_initial, key_final]. Si la función de comparación es la función inversa, el rango es [key_final, key_initial].

Es usada en la función keys() Usa la función keys_range() para encontrar las llaves en el rango especificado

Parameters:

root (rbt_node) – La raiz del arbol a examinar
key_initial (any) – limite inferior
key_final (any) – limite superior
list_key (single_linked_list) – La lista de respuesta

Returns:

Las llaves en el rago especificado

Return type:

single_linked_list

delete_min_node(root)

Encuentra y remueve la llave mas a la izquierda de la tabla de simbolos y su valor asociado

Important

Dependiendo de la definición de la función de comparación, la llave más a la izquierda puede ser la menor o la mayor.

Es usada en la función delete_min() Usa la función delete_min_node() para eliminar la llave más a la izquierda

Parameters:: root (rbt_node) – La raiz del arbol a examinar
Returns:: Retorna la raiz del arbol sin la llave más a la izquierda
Return type:: rbt_node

move_red_right(root)

Cambio de color durante el proceso de eliminacion

Parameters:: root (rbt_node) – Raiz del arbol
Returns:: El arbol con un hijo derecho de root en negro

move_red_left(root)

Cambio de color durante el proceso de eliminacion

Parameters:: root (rbt_node) – Raiz del arbol
Returns:: El arbol con el hijo izquierdo de root en negro
Return type:: rbt_node

balance(root)

Balancea el arbol

Parameters:: root (rbt_node) – raiz del arbol
Returns:: Raiz con el arbol balanceado
Return type:: rbt_node

default_compare(key, element)

Función de comparación por defecto. Compara una llave con la llave de un elemento llave-valor.

Parameters:

key (any) – Llave a comparar
element (rbt_node) – entry a comparar

Returns:

0 si son iguales, 1 si key > la llave del element, -1 si key < que la llave del element

Return type:

int

Algoritmos de recorrido

tree_traversal.py

inorder(my_order_map)

Implementa un recorrido inorder de un arbol binario (tanto AVL como BST). El recorrido pasa por los nodos en el siguiente orden: izquierda, raiz, derecha.

Usa la funcion inorder_tree() para realizar el recorrido.

Parameters:: my_order_map (binary_search_tree o red_black_tree) – El arbol binario a recorrer
Returns:: Una lista con los nodos del arbol en el orden especificado
Return type:: single_linked_list

preorder(my_order_map)

Implementa un recorrido preorder de un arbol binario (tanto AVL como BST). El recorrido pasa por los nodos en el siguiente orden: raiz, izquierda, derecha.

Usa la funcion preorder_tree() para realizar el recorrido.

Parameters:: my_order_map (binary_search_tree o red_black_tree) – El arbol binario a recorrer
Returns:: Una lista con los nodos del arbol en el orden especificado
Return type:: single_linked_list

postorder(my_order_map)

Implementa un recorrido postorder de un arbol binario (tanto AVL como BST). El recorrido pasa por los nodos en el siguiente orden: izquierda, derecha, raiz.

Usa la funcion postorder_tree() para realizar el recorrido.

Parameters:: my_order_map (binary_search_tree o red_black_tree) – El arbol binario a recorrer
Returns:: Una lista con los nodos del arbol en el orden especificado
Return type:: single_linked_list

inorder_tree(root, node_list)

Realiza un recorrido inorder de un arbol binario (tanto AVL como BST). El recorrido pasa por los nodos en el siguiente orden: izquierda, raiz, derecha.

Es usada por las funciones inorder()

Parameters:

root (bst_node o rbt_node) – El nodo raiz del arbol
node_list (single_linked_list) – La lista de nodos que se va a llenar

Returns:

Una lista con los nodos del arbol en el orden especificado

Return type:

single_linked_list

postorder_tree(root, node_list)

Realiza un recorrido postorder de un arbol binario (tanto AVL como BST). El recorrido pasa por los nodos en el siguiente orden: izquierda, derecha, raiz.

Es usada por las funciones postorder()

Parameters:

root (bst_node o rbt_node) – El nodo raiz del arbol
node_list (single_linked_list) – La lista de nodos que se va a llenar

Returns:

Una lista con los nodos del arbol en el orden especificado

Return type:

single_linked_list

preorder_tree(root, node_list)

Realiza un recorrido preorder de un arbol binario (tanto AVL como BST). El recorrido pasa por los nodos en el siguiente orden: raiz, izquierda, derecha.

Es usada por las funciones preorder()

Parameters:

root (bst_node o rbt_node) – El nodo raiz del arbol
node_list (single_linked_list) – La lista de nodos que se va a llenar

Returns:

Una lista con los nodos del arbol en el orden especificado

Return type:

single_linked_list