Binære søgetræer (BST)

Kommunikation og IT A · HTX · A-niveau · Datastrukturer og algoritmer

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

Et binært søgetræ er en træ-datastruktur hvor hvert element (node) har op til to børn:

• Venstre barn: altid MINDRE end forælderen
• Højre barn: altid STØRRE end forælderen

```python

class BSTNode:

def __init__(self, val):

self.val = val

self.venstre = None

self.højre = None

def indsæt(rod, val):

if rod is None:

return BSTNode(val)

if val < rod.val:

rod.venstre = indsæt(rod.venstre, val)

else:

rod.højre = indsæt(rod.højre, val)

return rod

```

Søgning: O(log n) for balanceret træ, O(n) i worst case (degenereret til liste).

In-order traversal giver sorteret rækkefølge:

```python

def inorder(node):

if node:

inorder(node.venstre)

print(node.val)

inorder(node.højre)

```

Balancerede varianter: AVL-træ, Red-Black tree — garanterer O(log n).

Læringsmål

• Implementere BST med indsæt og søg
• Forklare BST-invarianten (venstre < rod < højre)
• Udføre in-order, pre-order og post-order traversal
• Diskutere worst-case og balancerede træ-varianter

Sådan kan du arbejde med emnet

• Tegn et BST der opstår ved at indsætte tallene 8, 3, 10, 1, 6, 14 i denne rækkefølge
• Implementer en søgefunktion i et BST og forklar dens tidskompleksitet
• Forklar hvordan in-order traversal af et BST giver tallene i sorteret rækkefølge

Træningsforslag

• Byg et BST og vis in-order, pre-order, post-order traversal
• Implementér sletning af en node fra BST
• Løs LeetCode #98 (Validate Binary Search Tree)