Binaire zoekboom (BST)

Datastructuren en algoritmen in Python

Miriam Antona

Software engineer

Definitie

Linkersubboom van een knoop:
- waarden kleiner dan de knoop zelf
Rechtersubboom van een knoop:
- waarden groter dan de knoop zelf
Linker- en rechtersubbomen moeten binaire zoekbomen zijn

Schematische weergave van een binaire zoekboom.

Implementatie

class TreeNode:  
  def __init__(self, data, left=None, right=None):
    self.data = data
    self.left_child = left
    self.right_child = right

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

Zoeken

Zoek naar 72

Schematische weergave van een binaire zoekboom.

Zoeken

Zoek naar 72

Schematische weergave van een binaire zoekboom waarbij de wortel geel is.

Zoeken

Zoek naar 72

Schematische weergave van een binaire zoekboom waarbij de wortel en de linkersubboom grijs zijn. De eerste knoop van de rechtersubboom is geel.

Zoeken

Zoek naar 72

Schematische weergave van een binaire zoekboom. De linkersubboom van de laatste wortel en de laatste wortel zijn grijs. De nieuwe wortel is geel.

Zoeken

Zoek naar 72

Schematische weergave van een binaire zoekboom waarbij de nieuwe wortel geel is en de rest grijs.

Zoeken

Zoek naar 72

Schematische weergave van een binaire zoekboom waarbij de nieuwe wortel geel is en de rest grijs. De gekleurde knoop heeft het getal 72 en is gemarkeerd.

Zoeken

def search(self, search_value):

    current_node = self.root

    while current_node:

      if search_value == current_node.data:

        return True

      elif search_value < current_node.data:

        current_node = current_node.left_child

      else:

        current_node = current_node.right_child

    return False

Invoegen

def insert(self, data):

  new_node = TreeNode(data)

  if self.root == None:

Grafische weergave van een nieuwe knoop.

Invoegen

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return

Grafische weergave van de nieuwe knoop die wortel is geworden.

Invoegen

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:

Grafische weergave van een nieuwe knoop en een wortel met een rechterkind.

Invoegen

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root

    while True:

      if data < current_node.data:

        if current_node.left_child == None:

Grafische weergave van een nieuwe knoop en een wortel met een rechterkind. De wortel is de current_node.

Invoegen

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return

Grafische weergave van een wortel met een rechter- en linkerkind. De wortel is de current_node. De nieuwe knoop is het linkerkind.

Invoegen

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None: 
          current_node.left_child = new_node
          return
        else:

Grafische weergave van een nieuwe knoop en een binaire zoekboom met enkele elementen. De wortel is de current_node.

Invoegen

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None: 
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child

Grafische weergave van een nieuwe knoop en een binaire zoekboom met enkele elementen. De current_node is het linkerkind van de wortel.

Invoegen

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:

        if current_node.right_child == None:

Grafische weergave van een nieuwe knoop en een binaire zoekboom met een linkersubboom.

Invoegen

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return

Grafische weergave van een binaire zoekboom met een linkersubboom. De nieuwe knoop is nu het rechterkind van de wortel.

Invoegen

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return
        else:

Grafische weergave van een nieuwe knoop en een binaire zoekboom met enkele elementen.

Invoegen

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return
        else:
          current_node = current_node.right_child

Grafische weergave van een nieuwe knoop en een binaire zoekboom met enkele elementen. De current_node is het rechterkind van de wortel.

Invoegen

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return 
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return
        else:
          current_node = current_node.right_child

Grafische weergave van een nieuwe knoop en een binaire zoekboom met enkele elementen. De current_node is het rechterkind van de wortel. De nieuwe knoop is het linkerkind van de current_node.

Verwijderen

Geen kinderen

Grafische weergave van een binaire zoekboom met enkele elementen. Een knoop is rood omdat die wordt verwijderd. Deze knoop heeft geen kinderen.

Verwijderen

Geen kinderen
- verwijder de knoop

Grafische weergave van een binaire zoekboom met enkele elementen. De te verwijderen knoop is verdwenen.

Verwijderen

Eén kind

Grafische weergave van een binaire zoekboom met enkele elementen. Een knoop is rood omdat die wordt verwijderd. Deze knoop heeft een rechterkind.

Verwijderen

Eén kind
- verwijder de knoop
- verbind het kind met de ouder

Grafische weergave van een binaire zoekboom met enkele elementen. De verwijderde knoop is weg en de wortel wijst nu naar het rechterkind van de verwijderde knoop.

Verwijderen

Eén kind
- verwijder de knoop
- verbind het kind met de ouder

Grafische weergave van een binaire zoekboom.

Verwijderen

Twee kinderen

Grafische weergave van een binaire zoekboom waar de wortel rood is omdat die wordt verwijderd.

Verwijderen

Twee kinderen
- vervang door de opvolger
  - de knoop met de kleinste waarde groter dan die van de knoop
- vind de opvolger:

Grafische weergave van een binaire zoekboom waar de wortel rood is omdat die wordt verwijderd.

Verwijderen

Twee kinderen
- vervang door de opvolger
  - de knoop met de kleinste waarde groter dan die van de knoop
- vind de opvolger:
  - ga naar het rechterkind

Grafische weergave van een binaire zoekboom waar de wortel rood is omdat die wordt verwijderd. Het rechterkind van de wortel is geel.

Verwijderen

Twee kinderen
- vervang door de opvolger
  - de knoop met de kleinste waarde groter dan die van de knoop
- vind de opvolger:
  - ga naar het rechterkind
  - ga steeds links tot het einde

Grafische weergave van een binaire zoekboom waar de wortel rood is omdat die wordt verwijderd. Een andere knoop is geel om de opvolger te vinden.

Verwijderen

Twee kinderen
- vervang door de opvolger
  - de knoop met de kleinste waarde groter dan die van de knoop
- vind de opvolger:
  - ga naar het rechterkind
  - ga steeds links tot het einde

Grafische weergave van een binaire zoekboom waar de wortel rood is omdat die wordt verwijderd. Een andere knoop is geel om de opvolger te vinden.

Verwijderen

Twee kinderen
- vervang door de opvolger
  - de knoop met de kleinste waarde groter dan die van de knoop
- vind de opvolger:
  - ga naar het rechterkind
  - ga steeds links tot het einde

Grafische weergave van een binaire zoekboom waar de wortel rood is omdat die wordt verwijderd. Een andere knoop is geel om de opvolger te vinden. De opvolger is gevonden: 13.

Verwijderen

Twee kinderen
- vervang door de opvolger
  - de knoop met de kleinste waarde groter dan die van de knoop
- vind de opvolger:
  - ga naar het rechterkind
  - ga steeds links tot het einde

Grafische weergave van een binaire zoekboom. De wortel is vervangen door de opvolger.

Verwijderen

Twee kinderen
- vervang door de opvolger
  - de knoop met de kleinste waarde groter dan die van de knoop
- vind de opvolger:
  - ga naar het rechterkind
  - ga steeds links tot het einde
  - als de opvolger een rechterkind heeft:

Grafische weergave van een binaire zoekboom waar de opvolger een rechterkind heeft.

Verwijderen

Twee kinderen
- vervang door de opvolger
  - de knoop met de kleinste waarde groter dan die van de knoop
- vind de opvolger:
  - ga naar het rechterkind
  - ga steeds links tot het einde
  - als de opvolger een rechterkind heeft:
    - het kind wordt het linkerkind van de ouder van de opvolger.

Grafische weergave van een binaire zoekboom waar de opvolger een rechterkind had. Dit kind is nu het linkerkind van de ouder van de opvolger en de wortel is vervangen door de opvolger.

Toepassingen

Lijsten efficiënt ordenen
Veel sneller zoeken dan in arrays en gelinkte lijsten
Veel sneller invoegen en verwijderen dan in arrays
Gebruikt voor geavanceerdere datastructuren:
- dynamische verzamelingen
- opzoektabellen
- prioriteitswachtrijen

Laten we oefenen!

Datastructuren en algoritmen in Python