Двоичное дерево поиска (BST)

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

Miriam Antona

Software engineer

Определение

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

Схематичное представление двоичного дерева поиска.

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

Реализация

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
Структуры данных и алгоритмы на Python

Поиск

  • Поиск числа 72

Схематичное представление двоичного дерева поиска.

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

Поиск

  • Поиск числа 72

Схематичное представление двоичного дерева поиска: корневой узел выделен жёлтым.

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

Поиск

  • Поиск числа 72

Схематичное представление двоичного дерева поиска: корневой узел и его левое поддерево выделены серым. Первый узел правого поддерева выделен жёлтым.

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

Поиск

  • Поиск числа 72

Схематичное представление двоичного дерева поиска: левое поддерево последнего корневого узла и сам этот узел выделены серым. Новый корневой узел выделен жёлтым.

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

Поиск

  • Поиск числа 72

Схематичное представление двоичного дерева поиска: новый корневой узел выделен жёлтым, остальные узлы — серым.

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

Поиск

  • Поиск числа 72

Схематичное представление двоичного дерева поиска: новый корневой узел выделен жёлтым, остальные — серым. Выделенный узел содержит число 72 и подсвечен.

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

Поиск

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
Структуры данных и алгоритмы на Python

Вставка

def insert(self, data):

  new_node = TreeNode(data)

  if self.root == None:

Графическое представление нового узла.

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

Вставка

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

Графическое представление нового узла, ставшего корневым.

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

Вставка

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

Графическое представление нового узла и корневого узла с правым потомком.

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

Вставка

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).

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

Вставка

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). Новый узел является левым потомком.

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

Вставка

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).

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

Вставка

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) — левый потомок корня.

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

Вставка

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:

Графическое представление нового узла и двоичного дерева поиска с левым поддеревом.

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

Вставка

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

Графическое представление двоичного дерева поиска с левым поддеревом. Новый узел теперь является правым потомком корня.

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

Вставка

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:

Графическое представление нового узла и двоичного дерева поиска с несколькими элементами.

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

Вставка

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) — правый потомок корня.

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

Вставка

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) — правый потомок корня. Новый узел — левый потомок текущего узла.

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

Удаление

  • Нет потомков

Графическое представление двоичного дерева поиска с несколькими элементами. Один из узлов выделен красным — он будет удалён. У этого узла нет потомков.

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

Удаление

  • Нет потомков
    • удалить узел

Графическое представление двоичного дерева поиска с несколькими элементами. Узел, который нужно было удалить, исчез из дерева.

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

Удаление

  • Один потомок

Графическое представление двоичного дерева поиска с несколькими элементами. Один из узлов выделен красным — он будет удалён. У этого узла есть правый потомок.

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

Удаление

  • Один потомок
    • удалить узел
    • связать потомка с родителем удалённого узла

Графическое представление двоичного дерева поиска с несколькими элементами. Удалённый узел исчез, и корневой узел теперь указывает на правого потомка удалённого узла.

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

Удаление

  • Один потомок
    • удалить узел
    • связать потомка с родителем удалённого узла

Графическое представление двоичного дерева поиска.

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

Удаление

  • Два потомка

Графическое представление двоичного дерева поиска: корневой узел, который будет удалён, выделен красным.

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

Удаление

  • Два потомка
    • заменить узлом-преемником
      • узел с наименьшим значением, превышающим значение удаляемого
    • найти преемника:

Графическое представление двоичного дерева поиска: корневой узел, который будет удалён, выделен красным.

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

Удаление

  • Два потомка
    • заменить узлом-преемником
      • узел с наименьшим значением, превышающим значение удаляемого
    • найти преемника:
      • перейти к правому потомку

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

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

Удаление

  • Два потомка
    • заменить узлом-преемником
      • узел с наименьшим значением, превышающим значение удаляемого
    • найти преемника:
      • перейти к правому потомку
      • продолжать спускаться по левым узлам до конца

Графическое представление двоичного дерева поиска: корневой узел, который будет удалён, выделен красным. Другой узел выделен жёлтым в процессе поиска преемника.

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

Удаление

  • Два потомка
    • заменить узлом-преемником
      • узел с наименьшим значением, превышающим значение удаляемого
    • найти преемника:
      • перейти к правому потомку
      • продолжать спускаться по левым узлам до конца

Графическое представление двоичного дерева поиска: корневой узел, который будет удалён, выделен красным. Другой узел выделен жёлтым в процессе поиска преемника.

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

Удаление

  • Два потомка
    • заменить узлом-преемником
      • узел с наименьшим значением, превышающим значение удаляемого
    • найти преемника:
      • перейти к правому потомку
      • продолжать спускаться по левым узлам до конца

Графическое представление двоичного дерева поиска: корневой узел, который будет удалён, выделен красным. Другой узел выделен жёлтым. Преемник найден — это число 13.

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

Удаление

  • Два потомка
    • заменить узлом-преемником
      • узел с наименьшим значением, превышающим значение удаляемого
    • найти преемника:
      • перейти к правому потомку
      • продолжать спускаться по левым узлам до конца

Графическое представление двоичного дерева поиска. Корневой узел заменён преемником.

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

Удаление

  • Два потомка
    • заменить узлом-преемником
      • узел с наименьшим значением, превышающим значение удаляемого
    • найти преемника:
      • перейти к правому потомку
      • продолжать спускаться по левым узлам до конца
      • если у преемника есть правый потомок:

Графическое представление двоичного дерева поиска: у узла-преемника есть правый потомок.

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

Удаление

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

Графическое представление двоичного дерева поиска: потомок преемника стал левым потомком родителя преемника, а корневой узел заменён узлом-преемником.

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

Применение

  • Эффективное упорядочивание списков
  • Поиск значительно быстрее, чем в массивах и связных списках
  • Вставка и удаление значительно быстрее, чем в массивах
  • Используются для реализации более сложных структур данных:
    • динамические множества
    • таблицы поиска
    • очереди с приоритетом
Структуры данных и алгоритмы на Python

Давайте потренируемся!

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

Preparing Video For Download...