Binarne drzewo wyszukiwań (BST)

Struktury danych i algorytmy w Pythonie

Miriam Antona

Software engineer

Definicja

Lewe poddrzewo węzła:
- wartości mniejsze niż węzeł
Prawe poddrzewo węzła:
- wartości większe niż węzeł
Lewe i prawe poddrzewa muszą być binarnymi drzewami wyszukiwań

Schematyczna reprezentacja binarnego drzewa wyszukiwań.

Implementacja

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

Wyszukiwanie

Szukaj 72

Schematyczna reprezentacja binarnego drzewa wyszukiwań.

Wyszukiwanie

Szukaj 72

Schematyczna reprezentacja binarnego drzewa wyszukiwań, w którym węzeł główny jest zaznaczony na żółto.

Wyszukiwanie

Szukaj 72

Schematyczna reprezentacja binarnego drzewa wyszukiwań, gdzie węzeł główny i lewe poddrzewo są zaznaczone na szaro. Pierwszy węzeł prawego poddrzewa jest zaznaczony na żółto.

Wyszukiwanie

Szukaj 72

Schematyczna reprezentacja binarnego drzewa wyszukiwań. Lewe poddrzewo ostatniego węzła głównego i ten węzeł są zaznaczone na szaro. Nowy węzeł główny jest zaznaczony na żółto.

Wyszukiwanie

Szukaj 72

Schematyczna reprezentacja binarnego drzewa wyszukiwań, gdzie nowy węzeł główny jest zaznaczony na żółto, a pozostałe węzły na szaro.

Wyszukiwanie

Szukaj 72

Schematyczna reprezentacja binarnego drzewa wyszukiwań, gdzie nowy węzeł główny jest zaznaczony na żółto, a pozostałe na szaro. Zaznaczony węzeł zawiera liczbę 72 i jest wyróżniony.

Wyszukiwanie

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

Wstawianie

def insert(self, data):

  new_node = TreeNode(data)

  if self.root == None:

Graficzna reprezentacja nowego węzła.

Wstawianie

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

Graficzna reprezentacja nowego węzła, który stał się węzłem głównym.

Wstawianie

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

Graficzna reprezentacja nowego węzła i węzła głównego z prawym dzieckiem.

Wstawianie

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:

Graficzna reprezentacja nowego węzła i węzła głównego z prawym dzieckiem. Węzeł główny jest węzłem bieżącym.

Wstawianie

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

Graficzna reprezentacja węzła głównego z prawym i lewym dzieckiem. Węzeł główny jest węzłem bieżącym. Nowy węzeł jest lewym dzieckiem.

Wstawianie

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:

Graficzna reprezentacja nowego węzła i binarnego drzewa wyszukiwań z kilkoma elementami. Węzeł główny jest węzłem bieżącym.

Wstawianie

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

Graficzna reprezentacja nowego węzła i binarnego drzewa wyszukiwań z kilkoma elementami. Węzeł bieżący jest lewym dzieckiem węzła głównego.

Wstawianie

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:

Graficzna reprezentacja nowego węzła i binarnego drzewa wyszukiwań z lewym poddrzewem.

Wstawianie

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

Graficzna reprezentacja binarnego drzewa wyszukiwań z lewym poddrzewem. Nowy węzeł jest teraz prawym dzieckiem węzła głównego.

Wstawianie

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:

Graficzna reprezentacja nowego węzła i binarnego drzewa wyszukiwań z kilkoma elementami.

Wstawianie

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

Graficzna reprezentacja nowego węzła i binarnego drzewa wyszukiwań z kilkoma elementami. Węzeł bieżący jest prawym dzieckiem węzła głównego.

Wstawianie

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

Graficzna reprezentacja nowego węzła i binarnego drzewa wyszukiwań z kilkoma elementami. Węzeł bieżący jest prawym dzieckiem węzła głównego. Nowy węzeł jest lewym dzieckiem węzła bieżącego.

Usuwanie

Brak dzieci

Graficzna reprezentacja binarnego drzewa wyszukiwań z kilkoma elementami. Jeden z węzłów jest zaznaczony na czerwono, ponieważ ma zostać usunięty. Ten węzeł nie ma dzieci.

Usuwanie

Brak dzieci
- usuń węzeł

Graficzna reprezentacja binarnego drzewa wyszukiwań z kilkoma elementami. Węzeł przeznaczony do usunięcia zniknął z drzewa.

Usuwanie

Jedno dziecko

Graficzna reprezentacja binarnego drzewa wyszukiwań z kilkoma elementami. Jeden z węzłów jest zaznaczony na czerwono, ponieważ ma zostać usunięty. Ten węzeł ma prawe dziecko.

Usuwanie

Jedno dziecko
- usuń węzeł
- połącz dziecko z rodzicem usuniętego węzła

Graficzna reprezentacja binarnego drzewa wyszukiwań z kilkoma elementami. Węzeł przeznaczony do usunięcia zniknął, a węzeł główny wskazuje teraz na prawe dziecko usuniętego węzła.

Usuwanie

Jedno dziecko
- usuń węzeł
- połącz dziecko z rodzicem usuniętego węzła

Graficzna reprezentacja binarnego drzewa wyszukiwań.

Usuwanie

Dwoje dzieci

Graficzna reprezentacja binarnego drzewa wyszukiwań, w którym węzeł główny ma zostać usunięty i jest zaznaczony na czerwono.

Usuwanie

Dwoje dzieci
- zastąp węzeł jego następnikiem
  - węzeł o najmniejszej wartości większej niż wartość usuwanego węzła
- znajdź następnika:

Graficzna reprezentacja binarnego drzewa wyszukiwań, w którym węzeł główny ma zostać usunięty i jest zaznaczony na czerwono.

Usuwanie

Dwoje dzieci
- zastąp węzeł jego następnikiem
  - węzeł o najmniejszej wartości większej niż wartość usuwanego węzła
- znajdź następnika:
  - odwiedź prawe dziecko

Graficzna reprezentacja binarnego drzewa wyszukiwań, w którym węzeł główny ma zostać usunięty i jest zaznaczony na czerwono. Prawe dziecko węzła głównego jest zaznaczone na żółto.

Usuwanie

Dwoje dzieci
- zastąp węzeł jego następnikiem
  - węzeł o najmniejszej wartości większej niż wartość usuwanego węzła
- znajdź następnika:
  - odwiedź prawe dziecko
  - przechodź do lewych węzłów aż do końca

Graficzna reprezentacja binarnego drzewa wyszukiwań, w którym węzeł główny ma zostać usunięty i jest zaznaczony na czerwono. Inny węzeł jest zaznaczony na żółto w celu znalezienia następnika.

Usuwanie

Dwoje dzieci
- zastąp węzeł jego następnikiem
  - węzeł o najmniejszej wartości większej niż wartość usuwanego węzła
- znajdź następnika:
  - odwiedź prawe dziecko
  - przechodź do lewych węzłów aż do końca

Usuwanie

Dwoje dzieci
- zastąp węzeł jego następnikiem
  - węzeł o najmniejszej wartości większej niż wartość usuwanego węzła
- znajdź następnika:
  - odwiedź prawe dziecko
  - przechodź do lewych węzłów aż do końca

Usuwanie

Dwoje dzieci
- zastąp węzeł jego następnikiem
  - węzeł o najmniejszej wartości większej niż wartość usuwanego węzła
- znajdź następnika:
  - odwiedź prawe dziecko
  - przechodź do lewych węzłów aż do końca

Graficzna reprezentacja binarnego drzewa wyszukiwań. Węzeł główny został zastąpiony następnikiem.

Usuwanie

Dwoje dzieci
- zastąp węzeł jego następnikiem
  - węzeł o najmniejszej wartości większej niż wartość usuwanego węzła
- znajdź następnika:
  - odwiedź prawe dziecko
  - przechodź do lewych węzłów aż do końca
  - jeśli następnik ma prawe dziecko:

Graficzna reprezentacja binarnego drzewa wyszukiwań, w którym węzeł następnika ma prawe dziecko.

Usuwanie

Dwoje dzieci
- zastąp węzeł jego następnikiem
  - węzeł o najmniejszej wartości większej niż wartość usuwanego węzła
- znajdź następnika:
  - odwiedź prawe dziecko
  - przechodź do lewych węzłów aż do końca
  - jeśli następnik ma prawe dziecko:
    - dziecko staje się lewym dzieckiem rodzica następnika.

Graficzna reprezentacja binarnego drzewa wyszukiwań, w którym węzeł następnika miał prawe dziecko. Dziecko następnika stało się lewym dzieckiem rodzica następnika, a węzeł główny został zastąpiony następnikiem.

Zastosowania

Efektywne sortowanie list
Znacznie szybsze wyszukiwanie niż w tablicach i listach powiązanych
Znacznie szybsze wstawianie i usuwanie niż w tablicach
Stosowane do implementacji bardziej zaawansowanych struktur danych:
- zbiory dynamiczne
- tablice przeglądowe
- kolejki priorytetowe

Czas na ćwiczenia!

Struktury danych i algorytmy w Pythonie