AVL-boom: complete gids met Python-implementatie

Onbalans in binaire zoekbomen

Binaire zoekbomen (BST’s) zijn een type binaire boom-datastructuur die data ordent volgens een specifieke volgorde. Elk knooppunt bevat een waarde en verwijst naar maximaal twee andere knooppunten: het linker en rechter kind. In een BST geldt de regel dat de waarde van het linkerkind kleiner moet zijn dan die van zijn ouder, en de waarde van het rechterkind groter.

BST’s kunnen zeer efficiënt zijn voor het vinden van specifieke waarden, omdat je tijdens het zoeken grote delen van de boom kunt uitsluiten. Als we bijvoorbeeld naar de waarde één zoeken in de boom hierboven, kunnen we alle knooppunten rechts van zes negeren. Door de orde-eigenschap weten we immers dat al die waarden groter zijn dan zes.

Idealiter splitst elk knooppunt de data doormidden, zodat bij elke stap naar beneden de helft van de waarden wordt geëlimineerd. Dat leidt tot extreem snelle zoekacties. Afhankelijk van de invoegvolgorde kun je echter uitkomen op een ongebalanceerde boom die de data niet effectief splitst. Als je bijvoorbeeld waarden van klein naar groot invoegt, krijg je een lineaire boom, die niet beter presteert dan een lijst.

Wat is een AVL-boom

Een AVL-boom is een binaire zoekboom met de volgende extra eigenschap:

Voor elk knooppunt verschilt de hoogte van de linker- en rechterdeelboom met hoogstens één.

Uitgewerkt betekent dit: de linkerdeelboom van een knooppunt omvat alle knooppunten links ervan, terwijl de rechterdeelboom alle knooppunten rechts ervan bevat. De hoogte van een boom is de lengte van het langste pad van de wortel (het bovenste knooppunt) naar een van zijn bladknooppunten (knooppunten zonder kinderen).

De balansfactor van een knooppunt is het hoogteverschil tussen zijn linker- en rechterdeelboom:

balance(N) = height(linkerdeelboom van N) - height(rechterdeelboom van N)

Bijvoorbeeld, balance(6) = 1 - 3 = -2.

In het diagram heeft knooppunt 6 een balansfactor van -2, wat aangeeft dat de boom niet voldoet aan de AVL-criteria. Voor een AVL-boom moet de balansfactor van elk knooppunt -1, 0 of 1 zijn.

Waarom AVL-bomen gebruiken

De efficiëntie van zoekopdrachten in een binaire zoekboom hangt af van de hoogte van de boom. In het slechtste geval is het aantal te onderzoeken knooppunten gelijk aan de hoogte. Een belangrijk probleem bij BST’s is dat de hoogte kan oplopen tot het aantal knooppunten, wat betekent dat een zoekopdracht mogelijk elk knooppunt moet inspecteren.

Laat M(h) het minimumaantal knooppunten zijn dat nodig is om een binaire zoekboom met hoogte h te krijgen. Voor eenvoudige BST’s hebben we gezien dat M(h) = h, wat betekent dat we met h knooppunten een hoogte h kunnen bereiken. Dit impliceert dat de hoogte lineair kan toenemen met het aantal knooppunten, waardoor de zoektijd evenredig wordt met de grootte van de dataset.

Bewijs dat AVL-bomen een logaritmische hoogte hebben

Beschouw het minimumaantal knooppunten, M(h), dat nodig is om een AVL-boom met hoogte h te maken. Omdat het een AVL-boom is, kan de balansfactor van elk knooppunt alleen -1, 0 of 1 zijn.

Aangezien we aannemen dat de boom zo weinig mogelijk knooppunten heeft om hoogte h te bereiken, kan de wortel geen balans van 0 hebben. Als dat zo was, zouden we een knooppunt links of rechts kunnen verwijderen om een balans van -1 of 1 te krijgen, en nog steeds een geldige AVL-boom overhouden.

Stel dat de balans van de wortel 1 is (de redenering is hetzelfde bij -1). Dit impliceert de volgende structuur:

Daarnaast moeten zowel de linker- als de rechterdeelboom ook AVL-bomen zijn, elk met het minimumaantal knooppunten voor hun respectieve hoogtes (anders zouden er nog knooppunten te verwijderen zijn). Het totale aantal knooppunten in de boom is 1 (voor de wortel) plus het aantal in de linkerdeelboom plus het aantal in de rechterdeelboom.

M(h) = 1 + (knooppunten in L) + (knooppunten in R) = 1 + M(h - 1) + M(h - 2)

Naarmate de hoogte toeneemt, zijn er meer knooppunten nodig om die hoogte te bereiken. Daarom geldt:

M(h - 1) > M(h - 2)

Gecombineerd kunnen we zeggen:

M(h) = 1 + M(h - 1) + M(h - 2) > 1 + 2 × M(h - 2) > 2 × M(h - 2)

Dit kunnen we h/2 keer toepassen totdat we M(1) = 1 of M(2) = 2 bereiken:

M(h) > 2 × M(h - 2) > 2 × 2 × M(h - 4) > 2 × 2 × 2 × M(h - 6) > … > 2(h/2)

Ter verduidelijking toont de volgende afbeelding de specifieke voorbeelden voor h = 7 en h = 6:

We concluderen dat het minimumaantal knooppunten in een AVL-boom met hoogte h minstens 2(h/2) is:

M(h) > 2(h/2)

Door aan beide kanten de logaritme met grondtal twee te nemen, krijgen we:

log2(M(h)) > log2(2(h/2)) = h/2

Door vervolgens beide kanten met twee te vermenigvuldigen, leiden we af dat de hoogte hoogstens twee keer de 2-logaritme van het aantal knooppunten is:

2 × log2(M(h)) > h

We hebben aangetoond dat:

De hoogte van een AVL-boom met N knooppunten is hoogstens 2 × log2(N).

Dit betekent dat zoekopdrachten in een AVL-boom slechts een klein deel van de dataset hoeven te onderzoeken. Bij één miljard items is de logaritme bijvoorbeeld ongeveer 30, wat inhoudt dat je zelfs dan maar zo’n 60 datapunten hoeft te bekijken om een specifieke waarde te vinden. Dat is een flinke verbetering ten opzichte van BST’s, die in het slechtste geval elk van die miljard datapunten moeten inspecteren.

Wil je dieper in tijdcomplexiteit duiken en het verschil tussen lineaire en logaritmische tijdcomplexiteit begrijpen? Lees dan deze blog over Big-O-notatie en tijdcomplexiteit.

De balans behouden met AVL-bomen

AVL-bomen garanderen snelle zoekopdrachten door af te dwingen dat de balans van elk knooppunt -1, 0 of 1 is. Om die balans te behouden, moeten we de boom herbouwen na het invoegen van een nieuwe waarde.

Invoegen in binaire zoekbomen gebeurt door vanaf de wortel het pad naar beneden te volgen. We gaan links als de in te voegen waarde kleiner is, en anders rechts.

Een invoeging vergroot de hoogte met hoogstens één. Als de balanceigenschap na het invoegen niet meer geldt, betekent dit dat er ofwel een knooppunt met balans -1 nu -2 heeft, of een knooppunt met balans 1 nu 2 heeft. Het eerste gebeurt in het bovenstaande voorbeeld.

Enkelvoudige rotaties

Om de balans te herstellen, gebruiken we boomrotaties. Een linkerrotatie op knooppunt A herstructureert de boom door A naar links te draaien, zoals hieronder getoond:

In het diagram:

• BL stelt de linkerdeelboom van B voor
• BR is de rechterdeelboom
• AL is de linkerdeelboom van A

Let op dat na de rotatie de volgorde van knooppunten nog steeds geldig is:

1. Knooppunt A is kleiner dan B omdat B zijn rechterkind was.
2. Knooppunten in BL zijn groter dan A omdat ze rechts van A stonden.
3. Knooppunten in AL zijn kleiner dan B omdat ze kleiner zijn dan A.

Een rechterrotatie werkt symmetrisch door A naar rechts te draaien.

Laten we een concreet voorbeeld bekijken door de onbalans na het invoegen van 19 te herstellen met een linkerrotatie op knooppunt 6.

Na het invoegen herstellen we de onbalans door een knooppunt met balans -2 of 2 te roteren. In dit geval had knooppunt 6 een balansfactor -2, wat betekent dat de boom naar rechts helt, dus passen we een linkerrotatie toe (tegengesteld aan de onbalans). Als de balans 2 is, gebruik je een rechterrotatie.

Dubbele rotaties

In het vorige voorbeeld helt de boom volledig naar rechts, dus was één linkerrotatie genoeg. Soms heb je echter een zigzag-onbalans: de boom helt naar één kant, maar de deelboom naar de andere. Om dit te zien gaan we terug naar de oorspronkelijke boom vóór het invoegen van 19 en voegen we in plaats daarvan 7 in:

In dit geval helt de boom nog steeds naar rechts, maar de deelboom met wortel 10 helt naar links. We moeten daarom eerst knooppunt 10 naar rechts roteren:

Let op dat knooppunt B geen rechterkind heeft. We tonen het in het diagram toch in blauw om het makkelijker te visualiseren. 

Na de rechterrotatie vallen we terug op het vorige geval, waarbij een linkerrotatie op 6 de balans herstelt:

Hoe implementeer je een AVL-boom in Python

We beginnen met de implementatie van het knooppunt.

Knooppuntimplementatie

Elk knooppunt van de boom heeft vijf attributen:

• De waarde die het opslaat (self.value)
• Het ouderknooppunt (self.parent)
• Het linkerkind (self.left)
• Het rechterkind (self.right)
• De hoogte van de deelboom met dit knooppunt als wortel (self.height)

class Node:
  def __init__(self, value, parent = None):
    self.value = value
    self.parent = parent
    self.left = None
    self.right = None
    self.height = 1

We gebruiken de waarde None om ontbrekende knooppunten te representeren. De standaardhoogte is 1, omdat een boom met één knooppunt hoogte 1 heeft. 

Om de boomimplementatie te vereenvoudigen, voegen we meerdere methoden toe aan de Node-klasse.

# Inside the Node class
  def left_height(self):
    # Get the heigth of the left subtree
    return 0 if self.left is None else self.left.height
  
  def right_height(self):
    # Get the height of the right subtree
    return 0 if self.right is None else self.right.height
  def balance_factor(self):
    # Get the balance factor
    return self.left_height() - self.right_height()
  def update_heigth(self):
    # Update the heigth of this node
    self.height = 1 + max(self.left_height(),self.right_height())
    
  def set_left(self, node):
    # Set the left child
    self.left = node
    if node is not None:
      node.parent = self
    self.update_heigth()
  
  def set_right(self, node):
    # Set the right child
    self.right = node
    if node is not None:
      node.parent = self
    self.update_heigth()
  def is_left_child(self):
    # Check whether this node is a left child
    return self.parent is not None and self.parent.left == self
  
  def is_right_child(self):
    # Check whether this node is a right child
    return self.parent is not None and self.parent.right == self

Let op dat we de methoden .set_left() en .set_right() gebruiken om respectievelijk het linker- en rechterkind toe te wijzen. We doen dit in plaats van direct self.left en self.right te wijzigen, omdat je bij elke wijziging van een kind ook de ouder van het nieuwe kind én de hoogte van het knooppunt moet bijwerken.

AVL-boomimplementatie

De AVL-boom bewaart één parameter: de wortel van de boom, het bovenste knooppunt.

class AVLTree:
  def __init__(self):
    self.root = None

Om de balans te behouden, moeten we linker- en rechterrotaties implementeren. Zo ziet een linkerrotatie eruit in het diagram:

# Inside the AVLTree class
  
  def rotate_left(self, a):
    b = a.right
    # 1. The new right child of A becomes the left child of B
    a.set_right(b.left)
    # 2. The new left child of B becomes A
    b.set_left(a)
    return b # 3. Return B to replace A with it

Rechterrotaties worden symmetrisch geïmplementeerd:

# Inside the AVLTree class
  
  def rotate_right(self, a):
    b = a.left
    a.set_left(b.right)
    b.set_right(a)
    return b

Met rotaties kunnen we de boom herverdelen. Een knooppunt moet hersteld worden als zijn balansfactor 2 (boom helt naar links) of -2 (boom helt naar rechts) is. In totaal onderscheiden we vier scenario’s:

We implementeren deze vier gevallen in de methode .rebalance().

# Inside the AVLTree class
  
  def rebalance(self, node):
    if node is None:
      # Empty tree, no rebalancing needed
      return None
    balance = node.balance_factor()
    if abs(balance) <= 1:
      # The node is already balanced, no rebalancing needed
      return node
    if balance == 2: 
      # Cases 1 and 2, the tree is leaning to the left
      if node.left.balance_factor() == -1: 
        # Case 2, we first do a left rotation
        node.set_left(self.rotate_left(node.left))
      return self.rotate_right(node)
    # Balance must be -2
    # Cases 3 and 4, the tree is leaning to the left
    if node.right.balance_factor() == 1:
      # Case 4, we first do a right rotation
      node.set_right(self.rotate_right(node.right)) 
    return self.rotate_left(node)

Merk op dat in elk geval de methode de wortel van de zojuist gebalanceerde deelboom teruggeeft. Deze nieuwe deelboomwortel gebruiken we later om tijdens het herverdelen de kinderen bij te werken.

Een knooppunt toevoegen aan een AVL-boom lijkt op een reguliere BST, met als extra stap het herstellen van de balans na het invoegen. In een BST begin je bij de wortel en ga je naar beneden. Bij elke stap vergelijk je de toe te voegen waarde met de huidige waarde. Is de waarde kleiner, dan ga je links; anders rechts. Tijdens het afdalen houd je de ouder bij, zodat je het nieuwe knooppunt als kind kunt invoegen.

Als we een leeg knooppunt bereiken, zijn er twee gevallen:

1. De ouder is None; de boom is leeg, dus het nieuwe knooppunt wordt de wortel.
2. We hebben de ouder gevonden en zetten het nieuwe knooppunt als linker- of rechterkind, afhankelijk van de waarden.

# Inside the AVLTree class
  def add(self, value):
    self.size += 1
    parent = None
    current = self.root
    while current is not None:
      parent = current
      if value < current.value:
        # Value to insert is smaller than node value, go left
        current = current.left
      else:
        # Value to insert is larger than node value, go right
        current = current.right
    # We found the parent, create the new node
    new_node = Node(value, parent)
    # Case 1: The parent is None so the new node is the root
    if parent is None:
      self.root = new_node
    else:
      # Case 2: Set the new node as a child of the parent
      if value < parent.value:
        parent.left = new_node
      else:
        parent.right = new_node
    # After a new node is added, we need to restore balance
    self.restore_balance(new_node)

Het enige verschil tussen de .add()-methode van een BST en die van een AVL-boom zit in de laatste stap. We lopen terug omhoog door de boom en herstellen de balans, te beginnen bij het nieuw toegevoegde knooppunt tot aan de wortel, en balanceren elk knooppunt met de methode .rebalance().

# Inside the AVLTree class
  def restore_balance(self, node):
    current = node
    # Go up the tree and rebalance left and right children
    while current is not None:
      current.set_left(self.rebalance(current.left))
      current.set_right(self.rebalance(current.right))
      current.update_heigth()
      current = current.parent
    self.root = self.rebalance(self.root)
    self.root.parent = None

Merk op dat de methode .rebalance() niets doet als het knooppunt al in balans is—dezelfde node wordt gewoon teruggegeven. Daarom kunnen we tijdens het omhoog lopen beide kanten aanroepen, ook al kan slechts één daarvan uit balans zijn. De andere aanroep laat de boom ongewijzigd.

We hebben .rebalance() zo geïmplementeerd dat het de (mogelijk) nieuwe wortel van de deelboom teruggeeft. Zo kunnen we tijdens het herstellen van de balans de linker- en rechterkinderen van de huidige knooppunten bijwerken.

Het volgende diagram toont de stappen van .restore_balance() terwijl we omhoog door de boom gaan.

In dit voorbeeld voegen we eerst knooppunt 8 toe. Vervolgens begint het herstellen van de balans bij dit knooppunt en werken we omhoog door de boom, waarbij we de linker- en rechterkinderen van elk tegengekomen knooppunt controleren en balanceren. Dit gaat door totdat we knooppunt 10 bereiken. Tot dat moment hebben de aanroepen van .rebalance() geen effect, omdat de knooppunten in balans zijn.

Bij knooppunt 10 zien we echter dat zijn linkerkind, knooppunt 7, een balansfactor van -2 heeft, waardoor herverdeling nodig is. Daarom wordt .rebalance(7) aangeroepen, wat ertoe leidt dat het linkerkind van knooppunt 10 wordt vervangen door de nieuwe wortel van de linkerdeelboom, knooppunt 8, waarmee de balans wordt hersteld.

Aanvullende AVL-boombewerkingen

Naast het toevoegen en verwijderen van elementen met behoud van balans, ondersteunen AVL-bomen nog een aantal essentiële operaties.

Minimum en maximum

Door de geordende aard van BST staat de minimumwaarde in het meest linkse knooppunt van de boom, terwijl de maximumwaarde in het meest rechtse knooppunt staat.

We hebben twee hulpmethoden geïmplementeerd die vanaf een gegeven knooppunt het meest linker en meest rechter knooppunt vinden. Deze functies zijn handig bij het implementeren van het verwijderen van knooppunten.

# Inside the AVLTree class
  
  def leftmost(self, starting_node):
    # Find the leftmost node from a given starting node
    previous = None
    current = starting_node
    while current is not None:
      previous = current
      current = current.left
    return previous
  def minimum(self):
    # Return the minimum value in the tree
    if self.root is None:
      raise Exception("Empty tree")
    return self.leftmost(self.root).value

# Inside the AVLTree class
 
  def rightmost(self, starting_node):
    # Find the rightmost node from a given starting node
    previous = None
    current = starting_node
    while current is not None:
      previous = current
      current = current.right
    return previous
  
  def maximum(self):
    # Fidn the maximum value in the tree
    if self.root is None:
      raise Exception("Empty tree")
    return self.rightmost(self.root).value

Bevat

Om te bepalen of een boom een bepaalde waarde bevat, gebruiken we de orde-eigenschap om onze zoekrichting te bepalen. Vanaf de wortel gaan we naar links als de gezochte waarde kleiner is dan het huidige knooppunt en naar rechts als die groter is. Bereiken we het einde van de boom zonder de waarde te vinden, dan is die niet aanwezig.

Hiervoor implementeren we een hulpmethode .locate_node(). Deze helpt niet alleen bij zoeken, maar ook bij bewerkingen zoals verwijderen. Daarnaast gebruiken we de methode .__contains__(), zodat we de operator in kunnen gebruiken om eenvoudig te controleren of een waarde in de boom zit.

# Inside the AVLTree class

  def locate_node(self, value):

    # Returns the node containing a given value or None if no

    # such node exists

    current = self.root

    while current is not None:

      if value == current.value:

        return current

      if value < current.value:

        current = current.left

      else:

        current = current.right

    return None

  def __contains__(self, value):

    node = self.locate_node(value)

    return node is not None

Verwijderen

Een knooppunt verwijderen in een AVL-boom kan lastig zijn wanneer het knooppunt in het midden van de boom staat. Als het een blad is, dus geen kinderen heeft, kunnen we het eenvoudig verwijderen door de linker- of rechterkindverwijzing van de ouder op None te zetten, afhankelijk van of het een linker- of rechterkind is.

Een speciaal geval doet zich voor wanneer het te verwijderen knooppunt de wortel is. In dat geval kunnen we het verwijderen door de wortel op None te zetten.

# Inside the AVLTree class

  def delete_leaf(self, node):

    if node.parent is None:

      self.root = None

    elif node.is_left_child():

      node.parent.left = None

      node.parent = None

    else:

      node.parent.right = None

      node.parent = None

Om een waarde uit een AVL-boom te verwijderen, moeten we eerst het knooppunt met die waarde vinden met .locate_node(). Als het een blad is, kunnen we het verwijderen met .delete_leaf(). Als het geen blad is, zou direct verwijderen de structuur verstoren. Daarom zoeken we een geschikte vervanger. Als het te verwijderen knooppunt een linkerkind heeft, kiezen we het meest rechter knooppunt in zijn linkerdeelboom. Zo blijft de geordende structuur behouden.

Het onderstaande diagram toont het verwijderen van knooppunt 10. Omdat het een linkerkind heeft, vervangen we het door het meest rechter knooppunt in de linkerdeelboom. Na de vervanging is het belangrijk om de boom opnieuw te balanceren, te beginnen bij de ouder van het zojuist verplaatste knooppunt.

In dit voorbeeld is het vervangende knooppunt een blad. Als het vervangende knooppunt echter kinderen heeft, moeten die opnieuw aan de ouder van het vervangende knooppunt worden toegewezen. Omdat het vervangende knooppunt een extreem knooppunt is (meest links of meest rechts), kan het hoogstens één kind hebben. Deze herverwijzing is dus altijd mogelijk.

# Inside the AVLTree class

  def delete(self, value):

    # Delete a value from the tree

    node = self.locate_node(value)

    if node is None:

      raise Exception("Value not stored in tree")

    replacement = None

    rebalance_node = node.parent

    if node.left is not None:

      # There's a left child so we replace with rightmost node

      replacement = self.rightmost(node.left)

      # Check if reparenting is needed

      if replacement.is_left_child():

        replacement.parent.set_left(replacement.left)

      else:

        replacement.parent.set_right(replacement.left)

    elif node.right is not None:

      # There's a right child so we replace with the leftmost node

      replacement = self.leftmost(node.right)

      # Check if reparenting is needed

      if replacement.is_left_child():

        replacement.parent.set_left(replacement.right)

      else:

        replacement.parent.set_right(replacement.right)

    if replacement:

      # We found a replacement so replace the value

      node.value = replacement.value

      rebalance_node = replacement.parent

    else:

      # No replacement so it means the node to delete is a leaf

      self.delete_leaf(node)

    if rebalance_node is not None:

      self.restore_balance(rebalance_node)

Bereikquery

Bereikqueries houden in dat je alle waarden vindt die tussen twee opgegeven waarden liggen. Dankzij de orde van AVL-bomen kunnen we dit efficiënt doen.

Om alle waarden binnen het bereik met ondergrens lb en bovengrens ub te vinden, doorzoeken we de boom recursief. Voor elk knooppunt dat we tegenkomen: als de waarde binnen het bereik valt, voegen we die toe aan de resultaten. Vervolgens verkennen we zowel de linker- als de rechterdeelboom om door te zoeken.

We negeren de linkerdeelboom als de knooppuntwaarde kleiner is dan de ondergrens, omdat alle waarden daarin kleiner zijn dan de knooppuntwaarde. Evenzo negeren we de rechterdeelboom als de knooppuntwaarde groter is dan de bovengrens, omdat alle waarden daarin groter zullen zijn.

  def search(self, node, lb, ub, results):

    # Search for values between lower bound and upper bound

    if node is None:

      return

    if lb <= node.value and node.value <= ub:

      results.append(node.value)

    if node.value >= lb:

      self.search(node.left, lb, ub, results)

    if node.value <= ub:

      self.search(node.right, lb, ub, results)

  def range_query(self, lb, ub):

    # Search for values between lower bound and upper bound

    results = []

    self.search(self.root, lb, ub, results)

    return results

Andere zelfbalancerende bomen

We hebben een AVL-boom geïmplementeerd die de volgende bewerkingen kan uitvoeren:

• Een waarde toevoegen
• Een waarde verwijderen
• Een waarde opzoeken
• Het minimum en maximum opvragen
• Alle waarden opvragen die tussen twee waarden vallen

Het avltree-pakket biedt een Python-implementatie met deze mogelijkheden.

Andere zelfbalancerende binaire zoekbomen, zoals red-black-bomen, splay-bomen en B-bomen, bieden vergelijkbare functionaliteit. Over het algemeen is hun performance vergelijkbaar voor de meeste toepassingen, omdat ze allemaal een gegarandeerd logaritmische hoogte behouden. AVL-bomen zijn doorgaans strakker gebalanceerd, wat zoekoperaties optimaliseert, maar mogelijk tot tragere invoegingen leidt door strengere herverdelingsvereisten.

Splay-bomen zijn bijzonder effectief wanneer recent geraadpleegde elementen vaak opnieuw gebruikt worden, waardoor ze een uitstekende keuze zijn voor cache-implementaties.

B-bomen zijn uniek ontworpen om efficiënt op schijf te werken in plaats van in geheugen, wat ze onmisbaar maakt voor het beheren van grote datasets die niet in het geheugen passen, zoals bij het aanmaken van database-indexen.

Verdere verbeteringen

Er zijn verschillende manieren om onze implementatie te verbeteren. Hier zijn enkele suggesties voor oefeningen om je begrip van AVL-bomen te verdiepen:

• In onze huidige implementatie slaan knooppunten slechts één waarde op. Voor gebruik als database-indexen is het nodig om hele rijen op te slaan, omdat de waarde overeenkomt met een kolom in de tabel. We kunnen onze implementatie uitbreiden zodat de AVL-boom werkt als een dictionary die waarden aan rijen koppelt.
• Onze implementatie ondersteunt geen duplicaten. Je kunt deze echter aanpassen om meerdere knooppunten met dezelfde waarde toe te staan.
• Meestal worden AVL-bomen recursief geïmplementeerd. Wij kozen ervoor dit te vermijden om geen diepgaande kennis van recursie te vereisen. Recursieve implementaties zijn over het algemeen eleganter en beknopter, maar vragen wel een goed begrip van het concept recursie.

Conclusie

BST’s zijn een type binaire boomdatastructuur die data volgens een specifieke orde organiseert. Daardoor hoef je bij het zoeken naar specifieke waarden niet de hele dataset te inspecteren. BST’s kunnen echter uit balans raken, wat leidt tot slechtere prestaties en in sommige gevallen toch het inspecteren van de hele dataset vereist.

AVL-bomen lossen dit op door extra balanceigenschappen af te dwingen via rotaties. Deze eigenschappen zorgen ervoor dat de hoogte van de boom logaritmisch blijft ten opzichte van de grootte van de dataset, wat een aanzienlijke verbetering biedt.

Logaritmische tijdcomplexiteit is een grote stap vooruit ten opzichte van lineaire tijdcomplexiteit, waardoor AVL-bomen extreem efficiënt zijn voor zoekopdrachten. Zelfs bij datasets met miljarden items hoef je maar enkele datapunten te bekijken om een element te vinden, wat ze aanzienlijk efficiënter maakt.