Rilasciato · in miglioramento
Algorithm
Terminologia e visite degli alberi, ricerca, inserimento e cancellazione negli alberi binari di ricerca, heap binari e code di priorità, con codice.
Un albero è una struttura dati gerarchica che parte da una radice e si ramifica in genitori e figli. Aggiungendo a un albero binario la regola "chiavi minori a sinistra, maggiori a destra" si ottiene un albero binario di ricerca (BST); imponendo che ogni genitore non superi i figli e che la forma sia completa si ottiene uno heap binario. Questo argomento riunisce la terminologia degli alberi, le quattro visite, i BST, gli alberi bilanciati, gli heap e le code di priorità.
Alberi e heap sono l'ossatura di molti sistemi reali. Gli indici dei database sono B-tree, std::map in C++ e TreeMap in Java sono alberi rosso-neri, e scheduler, timer e cammini minimi di Dijkstra si basano su alberi o heap. Capire che l'altezza determina le prestazioni e che uno heap sta in un solo array aiuta a scegliere la struttura giusta, e sono domande frequenti nei colloqui tecnici.
Comincia disegnando un piccolo albero su carta e seguendo a mano le visite in preordine, in ordine, in postordine e per livelli. Poi implementa da solo inserimento, ricerca e cancellazione in un BST e le operazioni sift up e sift down dello heap, e verifica perché heapify costa O(n). Infine risolvi problemi come il top-K o la fusione di liste ordinate con strumenti standard come heapq di Python, priority_queue di C++ e PriorityQueue di Java.
Termini come radice, foglia, profondità e altezza, insieme alle visite in preordine, in ordine, in postordine e per livelli, bastano per leggere e risolvere la maggior parte dei problemi sugli alberi.
Poiché le chiavi minori stanno a sinistra e le maggiori a destra, ricerca, inserimento e cancellazione costano un tempo proporzionale all'altezza, e la visita in ordine restituisce le chiavi ordinate.
Con input ordinato un BST degenera in una lista concatenata. Gli alberi AVL e rosso-neri usano rotazioni per mantenere l'altezza in O(log n).
Un albero binario completo memorizzato in un array offre accesso al minimo in O(1), inserimento ed estrazione in O(log n) e heapify di un intero array in O(n).
La classe Node forma l'albero binario di ricerca: bst_insert confronta le chiavi fino a trovare un posto libero per il nuovo nodo, e bst_search scende con un ciclo. La visita in ordine conferma che le chiavi escono ordinate. MinHeap conserva gli elementi in una lista e ripristina la proprietà di heap con sift up in push e sift down in pop, così i valori escono dal più piccolo al più grande.
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.pySei capitoli che ti accompagnano dall'installazione ai concetti chiave di Alberi e heap.
Fai domande, condividi la tua esperienza e scambia opinioni su Alberi e heap.
Ancora nessuna discussione. Avvia la prima.
0 commenti
Accedi · Accedi per lasciare un commento.
Scrivi tu il primo commento.