Бинарное дерево поиска (BST): полное руководство с реализацией

Почему бинарное дерево поиска важно?

Бинарное дерево поиска (Binary Search Tree, BST) — одна из фундаментальных структур данных:

• 🔍 Быстрый поиск, вставка и удаление за O(log n) в среднем
• 📊 Хранит данные в отсортированном порядке
• 🏗️ Основа для более сложных структур (AVL, Red-Black деревья)
• 💾 Используется в базах данных и файловых системах
• 💼 Обязательная тема на собеседованиях в FAANG

Что такое бинарное дерево поиска?

BST — это бинарное дерево, в котором для каждого узла выполняется свойство:

• Все значения в левом поддереве меньше значения узла
• Все значения в правом поддереве больше значения узла

Визуализация BST

//         8          <- корень
//        / \
//       3   10       <- 3 < 8, 10 > 8
//      / \    \
//     1   6    14    <- 1 < 3, 6 > 3; 14 > 10
//        / \   /
//       4   7 13     <- 4 < 6, 7 > 6; 13 < 14

// Свойство BST выполняется для каждого узла:
// Узел 3: левое поддерево {1}, правое {4, 6, 7}
// 1 < 3 и все {4, 6, 7} > 3 ✓

Терминология

// Корень (Root): узел без родителя (8)
// Лист (Leaf): узел без потомков (1, 4, 7, 13)
// Высота (Height): длина пути от узла до самого глубокого листа
// Глубина (Depth): длина пути от корня до узла
// Поддерево (Subtree): дерево, образованное узлом и его потомками

Реализация BST на JavaScript

Базовая структура

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
}

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Вставка элемента

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  // Итеративная вставка
  insert(value) {
    const newNode = new TreeNode(value);

    if (!this.root) {
      this.root = newNode;
      return this;
    }

    let current = this.root;

    while (true) {
      // Игнорируем дубликаты
      if (value === current.value) return this;

      if (value < current.value) {
        if (!current.left) {
          current.left = newNode;
          return this;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          return this;
        }
        current = current.right;
      }
    }
  }

  // Рекурсивная вставка
  insertRecursive(value) {
    this.root = this._insertNode(this.root, value);
    return this;
  }

  _insertNode(node, value) {
    if (!node) {
      return new TreeNode(value);
    }

    if (value < node.value) {
      node.left = this._insertNode(node.left, value);
    } else if (value > node.value) {
      node.right = this._insertNode(node.right, value);
    }

    return node;
  }
}

// Пример использования
const bst = new BinarySearchTree();
[8, 3, 10, 1, 6, 14, 4, 7, 13].forEach((val) => bst.insert(val));

Поиск элемента

class BinarySearchTree {
  // ... предыдущий код

  // Итеративный поиск
  search(value) {
    let current = this.root;

    while (current) {
      if (value === current.value) {
        return current;
      }

      if (value < current.value) {
        current = current.left;
      } else {
        current = current.right;
      }
    }

    return null; // Не найдено
  }

  // Рекурсивный поиск
  searchRecursive(value, node = this.root) {
    if (!node || node.value === value) {
      return node;
    }

    if (value < node.value) {
      return this.searchRecursive(value, node.left);
    }

    return this.searchRecursive(value, node.right);
  }

  // Проверка наличия
  contains(value) {
    return this.search(value) !== null;
  }
}

// Пример
console.log(bst.contains(6)); // true
console.log(bst.contains(100)); // false

Удаление элемента

Удаление — самая сложная операция в BST. Есть три случая:

class BinarySearchTree {
  // ... предыдущий код

  delete(value) {
    this.root = this._deleteNode(this.root, value);
    return this;
  }

  _deleteNode(node, value) {
    if (!node) return null;

    if (value < node.value) {
      // Ищем в левом поддереве
      node.left = this._deleteNode(node.left, value);
    } else if (value > node.value) {
      // Ищем в правом поддереве
      node.right = this._deleteNode(node.right, value);
    } else {
      // Нашли узел для удаления

      // Случай 1: Лист (нет потомков)
      if (!node.left && !node.right) {
        return null;
      }

      // Случай 2: Один потомок
      if (!node.left) {
        return node.right;
      }
      if (!node.right) {
        return node.left;
      }

      // Случай 3: Два потомка
      // Находим минимум в правом поддереве (inorder successor)
      const minRight = this._findMin(node.right);
      node.value = minRight.value;
      node.right = this._deleteNode(node.right, minRight.value);
    }

    return node;
  }

  _findMin(node) {
    while (node.left) {
      node = node.left;
    }
    return node;
  }

  _findMax(node) {
    while (node.right) {
      node = node.right;
    }
    return node;
  }
}

Три случая удаления:

// Случай 1: Удаление листа (узел 7)
//       8                    8
//      / \                  / \
//     3   10    =>         3   10
//    / \    \             / \    \
//   1   6    14          1   6    14
//      / \                  /
//     4   7                4

// Случай 2: Один потомок (узел 10)
//       8                    8
//      / \                  / \
//     3   10    =>         3   14
//          \                   /
//          14                 13
//          /
//         13

// Случай 3: Два потомка (узел 3)
//       8                    8
//      / \                  / \
//     3   10    =>         4   10    (заменяем на inorder successor)
//    / \                  / \
//   1   6                1   6
//      /
//     4

Обходы дерева

class BinarySearchTree {
  // ... предыдущий код

  // Inorder: левое -> корень -> правое (отсортированный порядок)
  inorderTraversal(node = this.root, result = []) {
    if (node) {
      this.inorderTraversal(node.left, result);
      result.push(node.value);
      this.inorderTraversal(node.right, result);
    }
    return result;
  }

  // Preorder: корень -> левое -> правое
  preorderTraversal(node = this.root, result = []) {
    if (node) {
      result.push(node.value);
      this.preorderTraversal(node.left, result);
      this.preorderTraversal(node.right, result);
    }
    return result;
  }

  // Postorder: левое -> правое -> корень
  postorderTraversal(node = this.root, result = []) {
    if (node) {
      this.postorderTraversal(node.left, result);
      this.postorderTraversal(node.right, result);
      result.push(node.value);
    }
    return result;
  }

  // Level Order (BFS): по уровням
  levelOrderTraversal() {
    if (!this.root) return [];

    const result = [];
    const queue = [this.root];

    while (queue.length > 0) {
      const node = queue.shift();
      result.push(node.value);

      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    return result;
  }
}

// Пример для дерева: 8, 3, 10, 1, 6, 14, 4, 7, 13
console.log(bst.inorderTraversal()); // [1, 3, 4, 6, 7, 8, 10, 13, 14]
console.log(bst.preorderTraversal()); // [8, 3, 1, 6, 4, 7, 10, 14, 13]
console.log(bst.postorderTraversal()); // [1, 4, 7, 6, 3, 13, 14, 10, 8]
console.log(bst.levelOrderTraversal()); // [8, 3, 10, 1, 6, 14, 4, 7, 13]

Полезные методы

class BinarySearchTree {
  // ... предыдущий код

  // Минимальное значение
  findMin() {
    if (!this.root) return null;
    let current = this.root;
    while (current.left) {
      current = current.left;
    }
    return current.value;
  }

  // Максимальное значение
  findMax() {
    if (!this.root) return null;
    let current = this.root;
    while (current.right) {
      current = current.right;
    }
    return current.value;
  }

  // Высота дерева
  getHeight(node = this.root) {
    if (!node) return -1;
    return 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));
  }

  // Количество узлов
  getSize(node = this.root) {
    if (!node) return 0;
    return 1 + this.getSize(node.left) + this.getSize(node.right);
  }

  // Проверка валидности BST
  isValidBST(node = this.root, min = -Infinity, max = Infinity) {
    if (!node) return true;

    if (node.value <= min || node.value >= max) {
      return false;
    }

    return (
      this.isValidBST(node.left, min, node.value) &&
      this.isValidBST(node.right, node.value, max)
    );
  }

  // Поиск k-го наименьшего элемента
  kthSmallest(k) {
    let count = 0;
    let result = null;

    const inorder = (node) => {
      if (!node || result !== null) return;

      inorder(node.left);

      count++;
      if (count === k) {
        result = node.value;
        return;
      }

      inorder(node.right);
    };

    inorder(this.root);
    return result;
  }

  // Наименьший общий предок (LCA)
  lowestCommonAncestor(p, q) {
    let current = this.root;

    while (current) {
      if (p < current.value && q < current.value) {
        current = current.left;
      } else if (p > current.value && q > current.value) {
        current = current.right;
      } else {
        return current.value;
      }
    }

    return null;
  }
}

Реализация на Python

Полная реализация BST

class TreeNode:
    """Узел бинарного дерева"""
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


class BinarySearchTree:
    """Бинарное дерево поиска"""

    def __init__(self):
        self.root = None

    def insert(self, value) -> 'BinarySearchTree':
        """Вставка элемента"""
        if not self.root:
            self.root = TreeNode(value)
            return self

        current = self.root
        while True:
            if value == current.value:
                return self  # Игнорируем дубликаты

            if value < current.value:
                if not current.left:
                    current.left = TreeNode(value)
                    return self
                current = current.left
            else:
                if not current.right:
                    current.right = TreeNode(value)
                    return self
                current = current.right

    def search(self, value) -> TreeNode:
        """Поиск элемента"""
        current = self.root

        while current:
            if value == current.value:
                return current
            elif value < current.value:
                current = current.left
            else:
                current = current.right

        return None

    def contains(self, value) -> bool:
        """Проверка наличия элемента"""
        return self.search(value) is not None

    def delete(self, value) -> 'BinarySearchTree':
        """Удаление элемента"""
        self.root = self._delete_node(self.root, value)
        return self

    def _delete_node(self, node: TreeNode, value) -> TreeNode:
        """Рекурсивное удаление узла"""
        if not node:
            return None

        if value < node.value:
            node.left = self._delete_node(node.left, value)
        elif value > node.value:
            node.right = self._delete_node(node.right, value)
        else:
            # Нашли узел для удаления

            # Случай 1 и 2: нет потомков или один потомок
            if not node.left:
                return node.right
            if not node.right:
                return node.left

            # Случай 3: два потомка
            min_node = self._find_min(node.right)
            node.value = min_node.value
            node.right = self._delete_node(node.right, min_node.value)

        return node

    def _find_min(self, node: TreeNode) -> TreeNode:
        """Найти минимальный узел"""
        while node.left:
            node = node.left
        return node

    # Обходы дерева
    def inorder(self, node=None, result=None) -> list:
        """Inorder обход (отсортированный порядок)"""
        if result is None:
            result = []
            node = self.root

        if node:
            self.inorder(node.left, result)
            result.append(node.value)
            self.inorder(node.right, result)

        return result

    def preorder(self, node=None, result=None) -> list:
        """Preorder обход"""
        if result is None:
            result = []
            node = self.root

        if node:
            result.append(node.value)
            self.preorder(node.left, result)
            self.preorder(node.right, result)

        return result

    def postorder(self, node=None, result=None) -> list:
        """Postorder обход"""
        if result is None:
            result = []
            node = self.root

        if node:
            self.postorder(node.left, result)
            self.postorder(node.right, result)
            result.append(node.value)

        return result

    def level_order(self) -> list:
        """Level order обход (BFS)"""
        if not self.root:
            return []

        result = []
        queue = [self.root]

        while queue:
            node = queue.pop(0)
            result.append(node.value)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        return result

    def get_height(self, node=None) -> int:
        """Высота дерева"""
        if node is None:
            node = self.root
        if not node:
            return -1
        return 1 + max(self.get_height(node.left), self.get_height(node.right))

    def is_valid_bst(self, node=None, min_val=float('-inf'),
                     max_val=float('inf')) -> bool:
        """Проверка валидности BST"""
        if node is None:
            node = self.root
        if not node:
            return True

        if node.value <= min_val or node.value >= max_val:
            return False

        return (self.is_valid_bst(node.left, min_val, node.value) and
                self.is_valid_bst(node.right, node.value, max_val))


# Пример использования
bst = BinarySearchTree()
for val in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    bst.insert(val)

print(bst.inorder())      # [1, 3, 4, 6, 7, 8, 10, 13, 14]
print(bst.contains(6))    # True
print(bst.get_height())   # 3

bst.delete(3)
print(bst.inorder())      # [1, 4, 6, 7, 8, 10, 13, 14]

Python: Итеративные обходы

def inorder_iterative(root: TreeNode) -> list:
    """Итеративный inorder обход с использованием стека"""
    result = []
    stack = []
    current = root

    while current or stack:
        # Идем до самого левого узла
        while current:
            stack.append(current)
            current = current.left

        # Обрабатываем текущий узел
        current = stack.pop()
        result.append(current.value)

        # Переходим к правому поддереву
        current = current.right

    return result


def preorder_iterative(root: TreeNode) -> list:
    """Итеративный preorder обход"""
    if not root:
        return []

    result = []
    stack = [root]

    while stack:
        node = stack.pop()
        result.append(node.value)

        # Правый потомок добавляется первым (LIFO)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

    return result

Временная и пространственная сложность

Сложность операций

Когда возникает худший случай?

// Худший случай: вырожденное дерево (похоже на связный список)
// Возникает при вставке отсортированных данных

// Вставка: 1, 2, 3, 4, 5
//     1
//      \
//       2
//        \
//         3
//          \
//           4
//            \
//             5

// Высота = n - 1, все операции O(n)

Пространственная сложность

• O(n) — для хранения n узлов
• O(h) — для стека рекурсии, где h — высота дерева
  • Лучший случай: O(log n)
  • Худший случай: O(n)

Балансировка деревьев

Для гарантии O(log n) используют самобалансирующиеся деревья:

AVL-дерево

// AVL: разница высот поддеревьев ≤ 1 для каждого узла

//    Несбалансированное          После балансировки (AVL)
//         30                           20
//        /                            /  \
//       20          =>              10    30
//      /
//     10

// Ротации для балансировки:
// - Left Rotation
// - Right Rotation
// - Left-Right Rotation
// - Right-Left Rotation

Red-Black дерево

// Используется в:
// - std::map, std::set в C++
// - TreeMap, TreeSet в Java
// - Многих базах данных

// Свойства:
// 1. Каждый узел красный или черный
// 2. Корень всегда черный
// 3. Красный узел имеет только черных потомков
// 4. Путь от корня до любого листа содержит одинаковое число черных узлов

Популярные задачи на BST

1. Проверка валидности BST

function isValidBST(root, min = -Infinity, max = Infinity) {
  if (!root) return true;

  if (root.value <= min || root.value >= max) {
    return false;
  }

  return (
    isValidBST(root.left, min, root.value) &&
    isValidBST(root.right, root.value, max)
  );
}

2. Преобразование отсортированного массива в сбалансированное BST

function sortedArrayToBST(nums) {
  if (nums.length === 0) return null;

  const mid = Math.floor(nums.length / 2);
  const node = new TreeNode(nums[mid]);

  node.left = sortedArrayToBST(nums.slice(0, mid));
  node.right = sortedArrayToBST(nums.slice(mid + 1));

  return node;
}

// [1, 2, 3, 4, 5, 6, 7] =>
//        4
//       / \
//      2   6
//     / \ / \
//    1  3 5  7

3. Сериализация и десериализация BST

function serialize(root) {
  if (!root) return '';

  const result = [];

  function preorder(node) {
    if (!node) return;
    result.push(node.value);
    preorder(node.left);
    preorder(node.right);
  }

  preorder(root);
  return result.join(',');
}

function deserialize(data) {
  if (!data) return null;

  const values = data.split(',').map(Number);
  let index = 0;

  function build(min, max) {
    if (index >= values.length) return null;

    const value = values[index];
    if (value < min || value > max) return null;

    index++;
    const node = new TreeNode(value);
    node.left = build(min, value);
    node.right = build(value, max);

    return node;
  }

  return build(-Infinity, Infinity);
}

4. Наименьший общий предок (LCA)

function lowestCommonAncestor(root, p, q) {
  while (root) {
    if (p < root.value && q < root.value) {
      root = root.left;
    } else if (p > root.value && q > root.value) {
      root = root.right;
    } else {
      return root;
    }
  }
  return null;
}

Сравнение с другими структурами

Практические применения

• Базы данных: B-деревья для индексации
• Файловые системы: организация директорий
• Компиляторы: таблицы символов
• Автодополнение: префиксные деревья (Trie)
• Игры: пространственное разбиение (BSP-деревья)

Заключение

Бинарное дерево поиска — это фундаментальная структура данных:

• Обеспечивает эффективный поиск, вставку и удаление
• Хранит данные в отсортированном порядке
• Основа для понимания более сложных деревьев (AVL, Red-Black, B-tree)
• Необходимый навык для собеседований и практической разработки

Понимание BST открывает путь к изучению баз данных, компиляторов и многих других областей computer science.