Lançado · em melhoria
Algorithm
Aprenda vocabulário e percursos de árvores, busca, inserção e remoção em árvores binárias de busca, e heaps binários com filas de prioridade, com código.
Uma árvore é uma estrutura de dados hierárquica que começa em uma raiz e se ramifica em pais e filhos. Ao adicionar a uma árvore binária a regra "chaves menores à esquerda, maiores à direita", você obtém uma árvore binária de busca (BST); ao exigir que cada pai não seja maior que os filhos e que o formato seja completo, você obtém um heap binário. Este tópico reúne o vocabulário de árvores, os quatro percursos, BSTs, árvores balanceadas, heaps e filas de prioridade.
Árvores e heaps sustentam muitos sistemas reais. Índices de bancos de dados são árvores B, std::map do C++ e TreeMap do Java são árvores rubro-negras, e escalonadores, timers e os caminhos mínimos de Dijkstra dependem de árvores ou heaps. Entender que a altura determina o desempenho e que um heap cabe em um único array ajuda a escolher a estrutura certa, e esses temas aparecem com frequência em entrevistas técnicas.
Comece desenhando uma árvore pequena no papel e acompanhando à mão os percursos em pré-ordem, em ordem, pós-ordem e por nível. Depois implemente você mesmo a inserção, a busca e a remoção em uma BST e as operações sift up e sift down do heap, e confira por que o heapify é O(n). Por fim, resolva problemas como top-K e a intercalação de listas ordenadas com ferramentas padrão como heapq do Python, priority_queue do C++ e PriorityQueue do Java.
Termos como raiz, folha, profundidade e altura, junto com os percursos em pré-ordem, em ordem, pós-ordem e por nível, bastam para ler e resolver a maioria dos problemas de árvores.
Como as chaves menores ficam à esquerda e as maiores à direita, busca, inserção e remoção custam tempo proporcional à altura, e o percurso em ordem produz a sequência ordenada.
Com entrada ordenada, uma BST degenera em uma lista ligada. Árvores AVL e rubro-negras usam rotações para manter a altura em O(log n).
Uma árvore binária completa guardada em um array oferece consulta ao mínimo em O(1), inserção e remoção em O(log n) e heapify de um array inteiro em O(n).
A classe Node forma a árvore binária de busca: bst_insert compara chaves até achar um espaço livre para o novo nó, e bst_search desce em um laço. O percurso em ordem confirma que as chaves saem ordenadas. MinHeap guarda os itens em uma lista e restaura a propriedade de heap com sift up em push e sift down em pop, de modo que os valores saem do menor para o maior.
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 levam você da instalação aos conceitos essenciais de Árvores e heaps.
Tire dúvidas, compartilhe experiências e troque opiniões sobre Árvores e heaps.
Ainda não há discussões. Comece a primeira.
0 comentários
Fazer login · Faça login para deixar um comentário.
Seja o primeiro a comentar.