Publié · en amélioration
Algorithm
Vocabulaire et parcours d'arbres, recherche, insertion et suppression dans un arbre binaire de recherche, tas binaires et files de priorité, avec du code.
Un arbre est une structure de données hiérarchique qui part d'une racine et se ramifie en parents et enfants. En ajoutant à un arbre binaire la règle « clés plus petites à gauche, plus grandes à droite », on obtient un arbre binaire de recherche (ABR) ; en imposant que chaque parent ne dépasse pas ses enfants et que la forme soit complète, on obtient un tas binaire. Ce sujet réunit le vocabulaire des arbres, les quatre parcours, les ABR, les arbres équilibrés, les tas et les files de priorité.
Arbres et tas forment l'ossature de nombreux systèmes réels. Les index de bases de données sont des arbres B, std::map en C++ et TreeMap en Java sont des arbres rouge-noir, et les ordonnanceurs, les minuteurs et les plus courts chemins de Dijkstra reposent sur des arbres ou des tas. Comprendre que la hauteur détermine les performances et qu'un tas tient dans un seul tableau permet de choisir la bonne structure ; ce sont aussi des questions courantes en entretien technique.
Commencez par dessiner un petit arbre sur papier et suivez à la main les parcours préfixe, infixe, postfixe et en largeur. Implémentez ensuite vous-même l'insertion, la recherche et la suppression dans un ABR ainsi que la percolation vers le haut et vers le bas d'un tas, et vérifiez pourquoi heapify est en O(n). Enfin, résolvez des problèmes comme le top-K ou la fusion de listes triées avec heapq en Python, priority_queue en C++ et PriorityQueue en Java.
Des termes comme racine, feuille, profondeur et hauteur, avec les parcours préfixe, infixe, postfixe et en largeur, suffisent pour lire et résoudre la plupart des problèmes d'arbres.
Comme les clés plus petites vont à gauche et les plus grandes à droite, recherche, insertion et suppression coûtent un temps proportionnel à la hauteur, et le parcours infixe donne l'ordre trié.
Avec des données triées, un ABR dégénère en liste chaînée. Les arbres AVL et rouge-noir utilisent des rotations pour garder une hauteur en O(log n).
Un arbre binaire complet stocké dans un tableau donne l'accès au minimum en O(1), l'insertion et l'extraction en O(log n) et la construction d'un tas à partir d'un tableau en O(n).
La classe Node forme l'arbre binaire de recherche : bst_insert compare les clés jusqu'à trouver une place libre pour le nouveau nœud, et bst_search descend dans une boucle. Le parcours infixe confirme que les clés sortent triées. MinHeap range les éléments dans une liste et rétablit la propriété de tas par percolation vers le haut dans push et vers le bas dans pop, si bien que les valeurs sortent de la plus petite à la plus 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.pySix chapitres pour aller de l'installation aux notions essentielles de Arbres et tas.
Posez vos questions, partagez votre expérience et échangez vos avis sur Arbres et tas.
Aucune discussion pour l'instant. Lancez la première.
0 commentaire
Se connecter · Connectez-vous pour laisser un commentaire.
Soyez le premier à commenter.