Дерево бінарного пошуку (BST)

Структури даних і алгоритми в Python

Miriam Antona

Software engineer

Визначення

Ліве піддерево вузла:
- значення менші за сам вузол
Праве піддерево вузла:
- значення більші за сам вузол
Ліве й праве піддерева мають бути деревами бінарного пошуку

Схематичне зображення дерева бінарного пошуку.

Реалізація

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

Пошук

Пошук 72

Схематичне зображення дерева бінарного пошуку.

Пошук

Пошук 72

Схематичне зображення дерева бінарного пошуку, де кореневий вузол виділено жовтим.

Пошук

Пошук 72

Схематичне зображення дерева бінарного пошуку, де корінь і ліве піддерево зафарбовано сірим. Перший вузол правого піддерева виділено жовтим.

Пошук

Пошук 72

Схематичне зображення дерева бінарного пошуку. Ліве піддерево попереднього кореня і сам попередній корінь зафарбовано сірим. Новий корінь виділено жовтим.

Пошук

Пошук 72

Схематичне зображення дерева бінарного пошуку, де новий корінь виділено жовтим, інші вузли — сірі.

Пошук

Пошук 72

Схематичне зображення дерева бінарного пошуку, де новий корінь виділено жовтим, інші вузли — сірі. Виділений вузол має число 72.

Пошук

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

Вставка

def insert(self, data):

  new_node = TreeNode(data)

  if self.root == None:

Графічне зображення нового вузла.

Вставка

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

Графічне зображення нового вузла, що став кореневим.

Вставка

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

Графічне зображення нового вузла та кореня з правою дитиною.

Вставка

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.

Вставка

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

Графічне зображення кореня з правою та лівою дитиною. Кореневий вузол — current_node. Новий вузол — ліва дитина.

Вставка

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.

Вставка

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

Графічне зображення нового вузла й дерева з кількома елементами. current_node — ліва дитина кореня.

Вставка

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:

Графічне зображення нового вузла і дерева бінарного пошуку з лівим піддеревом.

Вставка

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

Графічне зображення дерева бінарного пошуку з лівим піддеревом. Новий вузол став правою дитиною кореня.

Вставка

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:

Графічне зображення нового вузла і дерева бінарного пошуку з кількома елементами.

Вставка

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

Графічне зображення нового вузла і дерева з кількома елементами. current_node — права дитина кореня.

Вставка

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

Графічне зображення нового вузла і дерева з кількома елементами. current_node — права дитина кореня. Новий вузол — ліва дитина current_node.

Видалення

Без дітей

Графічне зображення дерева бінарного пошуку з кількома елементами. Один вузол позначено червоним для видалення. У цього вузла немає дітей.

Видалення

Без дітей
- видаліть його

Графічне зображення дерева бінарного пошуку з кількома елементами. Позначений вузол зник із дерева.

Видалення

Одна дитина

Графічне зображення дерева бінарного пошуку з кількома елементами. Один вузол позначено червоним для видалення. У цього вузла є права дитина.

Видалення

Одна дитина
- видаліть його
- з'єднайте дитину з батьком вузла

Графічне зображення дерева бінарного пошуку з кількома елементами. Видалений вузол зник, а корінь вказує на його праву дитину.

Видалення

Одна дитина
- видаліть його
- з'єднайте дитину з батьком вузла

Схематичне зображення дерева бінарного пошуку.

Видалення

Двоє дітей

Графічне зображення дерева бінарного пошуку, де кореневий вузол буде видалено та позначено червоним.

Видалення

Двоє дітей
- замініть його наступником
  - вузол з найменшим значенням, що більше за значення вузла
- знайдіть наступника:

Графічне зображення дерева бінарного пошуку, де кореневий вузол буде видалено та позначено червоним.

Видалення

Двоє дітей
- замініть його наступником
  - вузол із найменшим значенням, що більше за значення вузла
- знайдіть наступника:
  - перейдіть до правої дитини

Графічне зображення дерева бінарного пошуку, де кореневий вузол буде видалено та позначено червоним. Права дитина кореня виділена жовтим.

Видалення

Двоє дітей
- замініть його наступником
  - вузол із найменшим значенням, що більше за значення вузла
- знайдіть наступника:
  - перейдіть до правої дитини
  - далі йдіть лівими вузлами до кінця

Графічне зображення дерева бінарного пошуку, де кореневий вузол буде видалено та позначено червоним. Інший вузол виділено жовтим для пошуку наступника.

Видалення

Двоє дітей
- замініть його наступником
  - вузол із найменшим значенням, що більше за значення вузла
- знайдіть наступника:
  - перейдіть до правої дитини
  - далі йдіть лівими вузлами до кінця

Видалення

Двоє дітей
- замініть його наступником
  - вузол із найменшим значенням, що більше за значення вузла
- знайдіть наступника:
  - перейдіть до правої дитини
  - далі йдіть лівими вузлами до кінця

Графічне зображення дерева бінарного пошуку, де кореневий вузол буде видалено та позначено червоним. Інший вузол виділено жовтим для пошуку наступника. Наступника знайдено — це число 13.

Видалення

Двоє дітей
- замініть його наступником
  - вузол із найменшим значенням, що більше за значення вузла
- знайдіть наступника:
  - перейдіть до правої дитини
  - далі йдіть лівими вузлами до кінця

Схематичне зображення дерева бінарного пошуку. Корінь замінено наступником.

Видалення

Двоє дітей
- замініть його наступником
  - вузол із найменшим значенням, що більше за значення вузла
- знайдіть наступника:
  - перейдіть до правої дитини
  - далі йдіть лівими вузлами до кінця
  - якщо в наступника є права дитина:

Графічне зображення дерева бінарного пошуку, де в наступника є права дитина.

Видалення

Двоє дітей
- замініть його наступником
  - вузол із найменшим значенням, що більше за значення вузла
- знайдіть наступника:
  - перейдіть до правої дитини
  - далі йдіть лівими вузлами до кінця
  - якщо в наступника є права дитина:
    - дитина стає лівою дитиною батька наступника.

Графічне зображення дерева бінарного пошуку, де в наступника була права дитина. Ця дитина стала лівою дитиною батька наступника, а корінь замінено наступником.

Застосування

Ефективно впорядковуйте списки
Значно швидший пошук, ніж у масивах і зв'язаних списках
Значно швидша вставка й видалення, ніж у масивах
Використовується для складніших структур даних:
- динамічні множини
- таблиці пошуку
- черги з пріоритетами

Давайте потренуємось!

Структури даних і алгоритми в Python