Binaire zoekbomen uitgelegd: invoegen, verwijderen en de vier doorloopvolgordes

Hoe werkt een binaire zoekboom? Leer invoegen, zoeken, verwijderen met de opvolger en preorder, inorder, postorder en level-order, met code in Python en Java.

Een binaire zoekboom (binary search tree, BST) combineert het beste van een gesorteerde array en een gelinkte lijst. Je kunt erin zoeken zoals bij binair zoeken, maar invoegen en verwijderen gaan zonder alles op te schuiven.

Op het tentamen is dit een vaste kluif: "voeg deze sleutels in, teken de boom", "verwijder 3", "geef de inorder-volgorde". In sollicitaties zijn boomvragen populair omdat ze recursief denken testen. En in de praktijk zitten gebalanceerde zoekbomen achter TreeMap in Java, database-indexen en de bestandssystemen op je laptop.

De BST-eigenschap

Elke knoop heeft een sleutel en hoogstens twee kinderen. Voor elke knoop geldt:

alle sleutels in de linker deelboom zijn kleiner;
alle sleutels in de rechter deelboom zijn groter.

Dat geldt dus voor de hele deelboom, niet alleen voor de directe kinderen. In de opgaven komen geen dubbele sleutels voor.

Invoegen

Begin bij de wortel. Is de nieuwe sleutel kleiner, ga naar links; groter, ga naar rechts. Kom je bij een lege plek, dan hang je de nieuwe knoop daar op. Een nieuwe sleutel wordt dus altijd een blad.

We voegen 8, 3, 10, 1, 6, 14, 4, 7, 13 in deze volgorde in:

Sleutel	Route	Wordt
8	lege boom	wortel
3	8 → links	linkerkind van 8
10	8 → rechts	rechterkind van 8
1	8 → links, 3 → links	linkerkind van 3
6	8 → links, 3 → rechts	rechterkind van 3
14	8 → rechts, 10 → rechts	rechterkind van 10
4	8 → links, 3 → rechts, 6 → links	linkerkind van 6
7	8 → links, 3 → rechts, 6 → rechts	rechterkind van 6
13	8 → rechts, 10 → rechts, 14 → links	linkerkind van 14

Het resultaat, de voorbeeldboom voor de rest van deze pagina:

            8
          /   \
         3     10
        / \      \
       1   6      14
          / \    /
         4   7  13

De invoegvolgorde bepaalt de vorm. Dezelfde sleutels in een andere volgorde geven een andere boom.

Zoeken

Zoeken volgt dezelfde route als invoegen. Bij elke knoop vergelijk je en ga je links of rechts.

Zoek	Bezochte knopen	Resultaat
7	8, 3, 6, 7	gevonden
5	8, 3, 6, 4	4 heeft geen rechterkind: niet gevonden

Je bezoekt hoogstens één knoop per niveau. Het aantal stappen is dus de hoogte h van de boom.

Verwijderen: drie gevallen

Zoek eerst de knoop. Wat je daarna doet, hangt af van het aantal kinderen.

Geval 1: blad (geen kinderen). Haal de knoop gewoon weg. Verwijder 13: het linkerkind van 14 wordt leeg, de rest van de boom blijft hetzelfde.

Geval 2: één kind. Het kind schuift op naar de plek van de knoop. Verwijder 10: de deelboom 14 (met 13) wordt het rechterkind van 8.

Geval 3: twee kinderen. Zoek de opvolger (in-order successor): de kleinste sleutel in de rechter deelboom. Die vind je door één keer naar rechts te gaan en dan zo ver mogelijk naar links. Kopieer de sleutel van de opvolger naar de knoop en verwijder daarna de opvolger uit de rechter deelboom. De opvolger heeft nooit een linkerkind, dus dat is altijd geval 1 of 2.

Verwijder 3 uit de oorspronkelijke boom. De rechter deelboom van 3 is 6, 4, 7; de kleinste daarin is 4. Dus 4 komt op de plek van 3, en het blad 4 verdwijnt:

            8
          /   \
         4     10
        / \      \
       1   6      14
            \    /
             7  13

Waarom werkt dit? De opvolger is groter dan alles links en kleiner dan alles wat rechts overblijft, dus de BST-eigenschap blijft intact.

De vier doorloopvolgordes

Een boom doorlopen (traversal) betekent elke knoop één keer bezoeken. Voor de voorbeeldboom:

Volgorde	Regel	Resultaat
Preorder	knoop, links, rechts	`8, 3, 1, 6, 4, 7, 10, 14, 13`
Inorder	links, knoop, rechts	`1, 3, 4, 6, 7, 8, 10, 13, 14`
Postorder	links, rechts, knoop	`1, 4, 7, 6, 3, 13, 14, 10, 8`
Level-order	per niveau, van links naar rechts	`8, 3, 10, 1, 6, 14, 4, 7, 13`

Ezelsbruggetje: pre, in en post zeggen wanneer de knoop zelf aan de beurt is: vóór, tussen of na zijn deelbomen.

Inorder geeft bij een BST altijd de gesorteerde volgorde. Handige controle voor je antwoord.
Preorder is handig om een boom te kopiëren of op te slaan: voeg je de preorder-volgorde opnieuw in, dan krijg je exact dezelfde boom terug.
Postorder verwerkt kinderen vóór de ouder, bijvoorbeeld bij het opruimen van een boom of het uitrekenen van een expressieboom.
Level-order is breedte-eerst zoeken en gebruikt een wachtrij, net als BFS bij grafen (zie ook stapels en wachtrijen).

Code

from collections import deque


class Knoop:
    def __init__(self, sleutel):
        self.sleutel = sleutel
        self.links = None
        self.rechts = None


def voeg_toe(knoop, sleutel):
    if knoop is None:
        return Knoop(sleutel)  # nieuwe sleutel wordt een blad
    if sleutel < knoop.sleutel:
        knoop.links = voeg_toe(knoop.links, sleutel)
    elif sleutel > knoop.sleutel:
        knoop.rechts = voeg_toe(knoop.rechts, sleutel)
    return knoop


def zoek(knoop, sleutel):
    while knoop is not None and knoop.sleutel != sleutel:
        knoop = knoop.links if sleutel < knoop.sleutel else knoop.rechts
    return knoop


def verwijder(knoop, sleutel):
    if knoop is None:
        return None
    if sleutel < knoop.sleutel:
        knoop.links = verwijder(knoop.links, sleutel)
    elif sleutel > knoop.sleutel:
        knoop.rechts = verwijder(knoop.rechts, sleutel)
    else:
        if knoop.links is None:  # blad of alleen rechterkind
            return knoop.rechts
        if knoop.rechts is None:  # alleen linkerkind
            return knoop.links
        opvolger = knoop.rechts  # twee kinderen: kleinste in rechter deelboom
        while opvolger.links is not None:
            opvolger = opvolger.links
        knoop.sleutel = opvolger.sleutel
        knoop.rechts = verwijder(knoop.rechts, opvolger.sleutel)
    return knoop


def preorder(k):
    return [] if k is None else [k.sleutel] + preorder(k.links) + preorder(k.rechts)


def inorder(k):
    return [] if k is None else inorder(k.links) + [k.sleutel] + inorder(k.rechts)


def postorder(k):
    return [] if k is None else postorder(k.links) + postorder(k.rechts) + [k.sleutel]


def level_order(wortel):
    resultaat, wachtrij = [], deque([wortel] if wortel else [])
    while wachtrij:
        k = wachtrij.popleft()
        resultaat.append(k.sleutel)
        for kind in (k.links, k.rechts):
            if kind is not None:
                wachtrij.append(kind)
    return resultaat


wortel = None
for s in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    wortel = voeg_toe(wortel, s)
print(inorder(wortel))  # [1, 3, 4, 6, 7, 8, 10, 13, 14]

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

static class Knoop {
    int sleutel;
    Knoop links, rechts;

    Knoop(int sleutel) {
        this.sleutel = sleutel;
    }
}

static Knoop voegToe(Knoop knoop, int sleutel) {
    if (knoop == null) return new Knoop(sleutel); // nieuwe sleutel wordt een blad
    if (sleutel < knoop.sleutel) knoop.links = voegToe(knoop.links, sleutel);
    else if (sleutel > knoop.sleutel) knoop.rechts = voegToe(knoop.rechts, sleutel);
    return knoop;
}

static Knoop zoek(Knoop knoop, int sleutel) {
    while (knoop != null && knoop.sleutel != sleutel) {
        knoop = sleutel < knoop.sleutel ? knoop.links : knoop.rechts;
    }
    return knoop;
}

static Knoop verwijder(Knoop knoop, int sleutel) {
    if (knoop == null) return null;
    if (sleutel < knoop.sleutel) {
        knoop.links = verwijder(knoop.links, sleutel);
    } else if (sleutel > knoop.sleutel) {
        knoop.rechts = verwijder(knoop.rechts, sleutel);
    } else {
        if (knoop.links == null) return knoop.rechts; // blad of alleen rechterkind
        if (knoop.rechts == null) return knoop.links; // alleen linkerkind
        Knoop opvolger = knoop.rechts; // twee kinderen: kleinste in rechter deelboom
        while (opvolger.links != null) opvolger = opvolger.links;
        knoop.sleutel = opvolger.sleutel;
        knoop.rechts = verwijder(knoop.rechts, opvolger.sleutel);
    }
    return knoop;
}

static void preorder(Knoop k, List<Integer> uit) {
    if (k == null) return;
    uit.add(k.sleutel);
    preorder(k.links, uit);
    preorder(k.rechts, uit);
}

static void inorder(Knoop k, List<Integer> uit) {
    if (k == null) return;
    inorder(k.links, uit);
    uit.add(k.sleutel);
    inorder(k.rechts, uit);
}

static void postorder(Knoop k, List<Integer> uit) {
    if (k == null) return;
    postorder(k.links, uit);
    postorder(k.rechts, uit);
    uit.add(k.sleutel);
}

static List<Integer> levelOrder(Knoop wortel) {
    List<Integer> resultaat = new ArrayList<>();
    Deque<Knoop> wachtrij = new ArrayDeque<>();
    if (wortel != null) wachtrij.add(wortel);
    while (!wachtrij.isEmpty()) {
        Knoop k = wachtrij.poll();
        resultaat.add(k.sleutel);
        if (k.links != null) wachtrij.add(k.links);
        if (k.rechts != null) wachtrij.add(k.rechts);
    }
    return resultaat;
}

Gebalanceerd of scheef

Alle operaties kosten O(h), met h de hoogte van de boom. Hoe hoog is een boom met n knopen?

Gebalanceerd: elk niveau is (bijna) vol. Een boom met hoogte h bevat dan tot 2^(h+1) - 1 knopen, dus h ≈ log n. Met een miljoen sleutels heb je ongeveer twintig stappen nodig.
Scheef (degenerate tree): voeg je 1, 2, 3, 4, 5 in deze volgorde in, dan gaat elke sleutel naar rechts. Je krijgt een gelinkte lijst en h = n - 1. Zoeken kost dan O(n).

Gesorteerde invoer is precies het geval dat in de praktijk vaak voorkomt (oplopende id's, tijdstempels). Daarom gebruik je in echte software een zelfbalancerende boom.

AVL-bomen en rotaties

Een AVL-boom is een BST die na elke invoeging en verwijdering controleert of bij elke knoop de hoogtes van de linker en rechter deelboom hoogstens 1 verschillen. Zo niet, dan herstelt hij de balans met een rotatie: een kleine herschikking van drie knopen die de BST-eigenschap behoudt.

Rotatie naar rechts bij een te zware linkerkant (links-links-geval).
Rotatie naar links bij een te zware rechterkant (rechts-rechts-geval).
Dubbele rotaties (links-rechts en rechts-links) als de zware kant een "knik" heeft.

Een rotatie kost O(1), dus een AVL-boom garandeert O(log n) voor alle operaties. Een rood-zwarte boom (red-black tree) doet hetzelfde met iets soepelere regels; die zit achter Java's TreeMap en TreeSet.

Complexiteit

Operatie	Gebalanceerd	Scheef (slechtste geval)
Zoeken	`O(log n)`	`O(n)`
Invoegen	`O(log n)`	`O(n)`
Verwijderen	`O(log n)`	`O(n)`
Doorlopen (alle vier)	`O(n)`	`O(n)`
Minimum / maximum	`O(log n)`	`O(n)`

Voor een AVL- of rood-zwarte boom geldt de middelste kolom altijd. Vergelijk dit met een hashtabel: die is gemiddeld sneller (O(1)), maar een zoekboom houdt de sleutels gesorteerd, zodat je ook "geef alle sleutels tussen 20 en 50" efficiënt kunt beantwoorden.

Veelgemaakte fouten op het tentamen

Alleen met het directe kind vergelijken. De BST-eigenschap geldt voor de hele deelboom. Een boom met 5 als wortel en 7 ergens in de linker deelboom is geen BST, ook al klopt elk ouder-kindpaar.
Met de verkeerde opvolger vervangen. Bij twee kinderen neem je de kleinste in de rechter deelboom, niet het rechterkind zelf. Bij het verwijderen van 3 is dat 4, niet 6.
Preorder en postorder verwisselen. Preorder begint met de wortel, postorder eindigt ermee.
Level-order als "eerst alles links" lezen. Level-order gaat niveau voor niveau: 8, 3, 10, …, niet 8, 3, 1, … (dat is preorder).
Vergeten dat de invoegvolgorde de vorm bepaalt. Gesorteerde invoer geeft een scheve boom met hoogte n - 1, geen gebalanceerde.

Samenvatting

In een BST staat alles links van een knoop kleiner en alles rechts groter; inorder geeft de gesorteerde volgorde.
Invoegen en zoeken volgen één pad vanaf de wortel; nieuwe sleutels worden altijd een blad.
Verwijderen kent drie gevallen; bij twee kinderen vervang je de sleutel door de opvolger, de kleinste in de rechter deelboom.
Alle operaties kosten O(h): O(log n) als de boom gebalanceerd is, O(n) als hij scheef is.
AVL- en rood-zwarte bomen houden de boom met rotaties in balans.

Binaire zoekbomen uitgelegd: invoegen, verwijderen en de vier doorloopvolgordes

Oefenen