Publicado · en mejora
Algorithm
Aprende vocabulario y recorridos de árboles, búsqueda, inserción y borrado en árboles binarios de búsqueda, y montículos con colas de prioridad, con código.
Un árbol es una estructura de datos jerárquica que parte de una raíz y se ramifica en padres e hijos. Si a un árbol binario se le añade la regla "las claves menores a la izquierda y las mayores a la derecha", se obtiene un árbol binario de búsqueda (BST); si se exige que cada padre no sea mayor que sus hijos y que la forma sea completa, se obtiene un montículo binario (heap). Este tema reúne el vocabulario de árboles, los cuatro recorridos, los BST, los árboles balanceados, los montículos y las colas de prioridad.
Los árboles y los montículos sostienen muchos sistemas reales. Los índices de bases de datos son árboles B, std::map de C++ y TreeMap de Java son árboles rojo-negro, y los planificadores, los temporizadores y los caminos mínimos de Dijkstra dependen de árboles o montículos. Entender que la altura determina el rendimiento y que un montículo cabe en un solo arreglo ayuda a elegir la estructura adecuada, y son preguntas habituales en entrevistas técnicas.
Empieza dibujando un árbol pequeño en papel y siguiendo a mano los recorridos en preorden, inorden, postorden y por niveles. Después implementa tú mismo la inserción, búsqueda y borrado en un BST y las operaciones sift up y sift down del montículo, y comprueba por qué heapify es O(n). Por último, resuelve problemas como el top-K o la mezcla de listas ordenadas con herramientas estándar como heapq de Python, priority_queue de C++ y PriorityQueue de Java.
Términos como raíz, hoja, profundidad y altura, junto con los recorridos en preorden, inorden, postorden y por niveles, bastan para leer y resolver la mayoría de los problemas de árboles.
Como las claves menores van a la izquierda y las mayores a la derecha, buscar, insertar y borrar cuesta un tiempo proporcional a la altura, y el recorrido inorden da el orden ascendente.
Con entradas ordenadas, un BST degenera en una lista enlazada. Los árboles AVL y rojo-negro usan rotaciones para mantener la altura en O(log n).
Un árbol binario completo guardado en un arreglo permite consultar el mínimo en O(1), insertar y extraer en O(log n) y aplicar heapify a todo un arreglo en O(n).
La clase Node forma el árbol binario de búsqueda: bst_insert compara claves hasta encontrar un hueco libre para el nuevo nodo y bst_search desciende con un bucle. El recorrido inorden confirma que las claves salen ordenadas. MinHeap guarda los elementos en una lista y restablece la propiedad de montículo con sift up en push y sift down en pop, de modo que los valores salen de menor a mayor.
trees_and_heaps.py
# Binary search tree (insert/search) and a binary min-heap
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def bst_insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = bst_insert(root.left, key)
elif key > root.key:
root.right = bst_insert(root.right, key)
return root # duplicates are ignored
def bst_search(root, key):
while root is not None and root.key != key:
root = root.left if key < root.key else root.right
return root is not None
def inorder(root, out):
if root is not None:
inorder(root.left, out)
out.append(root.key)
inorder(root.right, out)
return out
class MinHeap:
def __init__(self):
self.a = []
def push(self, x):
a = self.a
a.append(x)
i = len(a) - 1
while i > 0 and a[(i - 1) // 2] > a[i]: # sift up
p = (i - 1) // 2
a[i], a[p] = a[p], a[i]
i = p
def pop(self):
a = self.a
top, last = a[0], a.pop()
if a:
a[0] = last
i, n = 0, len(a)
while True: # sift down
small = i
for c in (2 * i + 1, 2 * i + 2):
if c < n and a[c] < a[small]:
small = c
if small == i:
break
a[i], a[small] = a[small], a[i]
i = small
return top
def __len__(self):
return len(self.a)
root = None
for k in [50, 30, 70, 20, 40, 60, 80]:
root = bst_insert(root, k)
print(inorder(root, [])) # [20, 30, 40, 50, 60, 70, 80]
print(bst_search(root, 60), bst_search(root, 65)) # True False
heap = MinHeap()
for x in [5, 3, 8, 1, 9, 2]:
heap.push(x)
print([heap.pop() for _ in range(len(heap))]) # [1, 2, 3, 5, 8, 9]
python trees_and_heaps.pySeis capítulos que te llevan desde la instalación hasta las ideas clave de Árboles y montículos.
Haz preguntas, comparte tu experiencia e intercambia opiniones sobre Árboles y montículos.
Todavía no hay debates. Empieza el primero.
0 comentarios
Iniciar sesión · Inicia sesión para dejar un comentario.
Sé el primero en comentar.