Binární vyhledávací strom (BST)

Datové struktury a algoritmy v Pythonu

Miriam Antona

Software engineer

Definice

Levý podstrom uzlu:
- hodnoty menší než hodnota uzlu
Pravý podstrom uzlu:
- hodnoty větší než hodnota uzlu
Levý i pravý podstrom musí být binární vyhledávací stromy

Schematické znázornění binárního vyhledávacího stromu.

Implementace

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

Vyhledávání

Hledání hodnoty 72

Schematické znázornění binárního vyhledávacího stromu.

Vyhledávání

Hledání hodnoty 72

Schematické znázornění binárního vyhledávacího stromu, kde kořenový uzel je zbarven žlutě.

Vyhledávání

Hledání hodnoty 72

Schematické znázornění binárního vyhledávacího stromu, kde kořenový uzel a levý podstrom kořenového uzlu jsou zbarveny šedě. První uzel pravého podstromu je zbarven žlutě.

Vyhledávání

Hledání hodnoty 72

Schematické znázornění binárního vyhledávacího stromu. Levý podstrom posledního kořenového uzlu a samotný uzel jsou zbarveny šedě. Nový kořenový uzel je zbarven žlutě.

Vyhledávání

Hledání hodnoty 72

Schematické znázornění binárního vyhledávacího stromu, kde nový kořenový uzel je zbarven žlutě a ostatní uzly šedě.

Vyhledávání

Hledání hodnoty 72

Schematické znázornění binárního vyhledávacího stromu, kde nový kořenový uzel je zbarven žlutě a ostatní uzly šedě. Zbarvený uzel obsahuje číslo 72 a je zvýrazněn.

Vyhledávání

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

Vkládání

def insert(self, data):

  new_node = TreeNode(data)

  if self.root == None:

Grafické znázornění nového uzlu.

Vkládání

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

Grafické znázornění nového uzlu, který se stal kořenovým uzlem.

Vkládání

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

Grafické znázornění nového uzlu a kořenového uzlu s pravým potomkem.

Vkládání

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:

Grafické znázornění nového uzlu a kořenového uzlu s pravým potomkem. Kořenový uzel je aktuálním uzlem (current_node).

Vkládání

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

Grafické znázornění kořenového uzlu s pravým a levým potomkem. Kořenový uzel je aktuálním uzlem. Nový uzel je levým potomkem.

Vkládání

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:

Grafické znázornění nového uzlu a binárního vyhledávacího stromu s několika prvky. Kořenový uzel je aktuálním uzlem.

Vkládání

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

Grafické znázornění nového uzlu a binárního vyhledávacího stromu s několika prvky. Aktuálním uzlem je levý potomek kořene.

Vkládání

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:

Grafické znázornění nového uzlu a binárního vyhledávacího stromu s levým podstromem.

Vkládání

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

Grafické znázornění binárního vyhledávacího stromu s levým podstromem. Nový uzel je nyní pravým potomkem kořene.

Vkládání

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:

Grafické znázornění nového uzlu a binárního vyhledávacího stromu s několika prvky.

Vkládání

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

Grafické znázornění nového uzlu a binárního vyhledávacího stromu s několika prvky. Aktuálním uzlem je pravý potomek kořene.

Vkládání

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

Grafické znázornění nového uzlu a binárního vyhledávacího stromu s několika prvky. Aktuálním uzlem je pravý potomek kořene. Nový uzel je levým potomkem aktuálního uzlu.

Mazání

Žádní potomci

Grafické znázornění binárního vyhledávacího stromu s několika prvky. Jeden z uzlů je zbarven červeně, protože bude odstraněn. Tento uzel nemá žádné potomky.

Mazání

Žádní potomci
- uzel se odstraní

Grafické znázornění binárního vyhledávacího stromu s několika prvky. Uzel určený k odstranění zmizel ze stromu.

Mazání

Jeden potomek

Grafické znázornění binárního vyhledávacího stromu s několika prvky. Jeden z uzlů je zbarven červeně, protože bude odstraněn. Tento uzel má pravého potomka.

Mazání

Jeden potomek
- uzel se odstraní
- potomek se připojí k rodiči odstraněného uzlu

Grafické znázornění binárního vyhledávacího stromu s několika prvky. Odstraněný uzel zmizel ze stromu a kořenový uzel nyní ukazuje na pravého potomka odstraněného uzlu.

Mazání

Jeden potomek
- uzel se odstraní
- potomek se připojí k rodiči odstraněného uzlu

Grafické znázornění binárního vyhledávacího stromu.

Mazání

Dva potomci

Grafické znázornění binárního vyhledávacího stromu, kde kořenový uzel bude odstraněn a je zbarven červeně.

Mazání

Dva potomci
- nahradit uzlem nástupce
  - uzel s nejmenší hodnotou větší než hodnota odstraňovaného uzlu
- nalezení nástupce:

Grafické znázornění binárního vyhledávacího stromu, kde kořenový uzel bude odstraněn a je zbarven červeně.

Mazání

Dva potomci
- nahradit uzlem nástupce
  - uzel s nejmenší hodnotou větší než hodnota odstraňovaného uzlu
- nalezení nástupce:
  - navštívit pravého potomka

Grafické znázornění binárního vyhledávacího stromu, kde kořenový uzel bude odstraněn a je zbarven červeně. Pravý potomek kořene je zbarven žlutě.

Mazání

Dva potomci
- nahradit uzlem nástupce
  - uzel s nejmenší hodnotou větší než hodnota odstraňovaného uzlu
- nalezení nástupce:
  - navštívit pravého potomka
  - procházet levé uzly až na konec

Grafické znázornění binárního vyhledávacího stromu, kde kořenový uzel bude odstraněn a je zbarven červeně. Další uzel je zbarven žlutě při hledání nástupce.

Mazání

Dva potomci
- nahradit uzlem nástupce
  - uzel s nejmenší hodnotou větší než hodnota odstraňovaného uzlu
- nalezení nástupce:
  - navštívit pravého potomka
  - procházet levé uzly až na konec

Grafické znázornění binárního vyhledávacího stromu, kde kořenový uzel bude odstraněn a je zbarven červeně. Další uzel je zbarven žlutě při hledání nástupce.

Mazání

Dva potomci
- nahradit uzlem nástupce
  - uzel s nejmenší hodnotou větší než hodnota odstraňovaného uzlu
- nalezení nástupce:
  - navštívit pravého potomka
  - procházet levé uzly až na konec

Grafické znázornění binárního vyhledávacího stromu, kde kořenový uzel bude odstraněn a je zbarven červeně. Další uzel je zbarven žlutě při hledání nástupce. Nástupce byl nalezen a je jím číslo 13.

Mazání

Dva potomci
- nahradit uzlem nástupce
  - uzel s nejmenší hodnotou větší než hodnota odstraňovaného uzlu
- nalezení nástupce:
  - navštívit pravého potomka
  - procházet levé uzly až na konec

Grafické znázornění binárního vyhledávacího stromu. Kořenový uzel byl nahrazen nástupcem.

Mazání

Dva potomci
- nahradit uzlem nástupce
  - uzel s nejmenší hodnotou větší než hodnota odstraňovaného uzlu
- nalezení nástupce:
  - navštívit pravého potomka
  - procházet levé uzly až na konec
  - pokud má nástupce pravého potomka:

Grafické znázornění binárního vyhledávacího stromu, kde uzel nástupce má pravého potomka.

Mazání

Dva potomci
- nahradit uzlem nástupce
  - uzel s nejmenší hodnotou větší než hodnota odstraňovaného uzlu
- nalezení nástupce:
  - navštívit pravého potomka
  - procházet levé uzly až na konec
  - pokud má nástupce pravého potomka:
    - potomek se stane levým potomkem rodiče nástupce.

Grafické znázornění binárního vyhledávacího stromu, kde uzel nástupce měl pravého potomka. Potomek nástupce se stal levým potomkem rodiče nástupce a kořenový uzel byl nahrazen uzlem nástupce.

Využití

Efektivní řazení seznamů
Mnohem rychlejší vyhledávání než u polí a seznamů
Mnohem rychlejší vkládání a mazání než u polí
Využívány při implementaci pokročilejších datových struktur:
- dynamické množiny
- vyhledávací tabulky
- prioritní fronty

Pojďme procvičovat!

Datové struktury a algoritmy v Pythonu