Binære søgetræer (BST)

It A · STX · A-niveau · Datastrukturer og algoritmer

💻 Binære søgetræer (BST)

Binært søgetræ (Binary Search Tree): hierarkisk datastruktur. Hvert knudepunkt (node) har: data/key, venstre barn (left child ≤ parent), højre barn (right child > parent).

Operationer og kompleksitet (gennemsnitlig/worst case): Search O(log n)/O(n), Insert O(log n)/O(n), Delete O(log n)/O(n). Worst case O(n) ved skæv træ (fx indsæt sorteret data).

Traverseringsmetoder: In-order (venstre→rod→højre) → sorteret rækkefølge. Pre-order (rod→venstre→højre) → kopiér træ. Post-order (venstre→højre→rod) → slet træ. Selvbalancerende træer undgår O(n) worst case: AVL-træ: streng balancering (|height(left)-height(right)| ≤ 1). Rotationer ved indsæt/slet.

Rød-sort træ (Red-Black Tree): bruges i C++ STL (std::map) og Java's TreeMap.

B-træer: bruges i databaser og filsystemer — håndterer disklæsninger effektivt (store noder = færre disk-reads).

Heap: komplet binært træ, men heap-egenskab (forælderens nøgle ≥ børns for max-heap). Bruges til Priority Queue og HeapSort.

Læringsmål

• Redegøre for opbygningen af et binært søgetræ
• Implementere indsættelse og søgning i et BST
• Analysere tidskompleksiteten for operationer på et BST

Sådan kan du arbejde med emnet

• Implementér et BST i Python med insert, search og in-order traversal
• Forklar, hvad der er det bedste og det værste tilfælde for søgning i et BST
• Diskutér, hvad der sker med et BST, hvis data indsættes i sorteret rækkefølge

Arbejd iterativt med prototyper og dokumentation. Test, evaluér og dokumentér.