Бинарное дерево поиска
Бинарное дерево поиска
BST (Binary Search Tree) - структура данных, где для каждого узла все значения слева меньше, а справа - больше.
Реализация BST
type TreeNode struct {
Value int
Left, Right *TreeNode
}
type BST struct {
Root *TreeNode
}
func (t *BST) Insert(val int) {
t.Root = insert(t.Root, val)
}
func insert(node *TreeNode, val int) *TreeNode {
if node == nil {
return &TreeNode{Value: val}
}
if val < node.Value {
node.Left = insert(node.Left, val)
} else if val > node.Value {
node.Right = insert(node.Right, val)
}
return node
}
func (t *BST) Search(val int) bool {
return search(t.Root, val)
}
func search(node *TreeNode, val int) bool {
if node == nil {
return false
}
switch {
case val == node.Value:
return true
case val < node.Value:
return search(node.Left, val)
default:
return search(node.Right, val)
}
}
<?php
declare(strict_types=1);
final class TreeNode
{
public ?TreeNode $left = null;
public ?TreeNode $right = null;
public function __construct(public readonly int $value) {}
}
final class BinarySearchTree
{
public ?TreeNode $root = null;
public function insert(int $val): void
{
$this->root = $this->insertNode($this->root, $val);
}
private function insertNode(?TreeNode $node, int $val): TreeNode
{
if ($node === null) {
return new TreeNode($val);
}
if ($val < $node->value) {
$node->left = $this->insertNode($node->left, $val);
} elseif ($val > $node->value) {
$node->right = $this->insertNode($node->right, $val);
}
return $node;
}
public function search(int $val): bool
{
return $this->searchNode($this->root, $val);
}
private function searchNode(?TreeNode $node, int $val): bool
{
if ($node === null) {
return false;
}
return match (true) {
$val === $node->value => true,
$val < $node->value => $this->searchNode($node->left, $val),
default => $this->searchNode($node->right, $val),
};
}
}
В PHP native бинарного дерева нет - пишем руками. Структура TreeNode тривиальна, поведение - в отдельном BinarySearchTree.
from dataclasses import dataclass
@dataclass(slots=True)
class TreeNode:
value: int
left: "TreeNode | None" = None
right: "TreeNode | None" = None
class BST:
def __init__(self) -> None:
self.root: TreeNode | None = None
def insert(self, val: int) -> None:
self.root = _insert(self.root, val)
def search(self, val: int) -> bool:
return _search(self.root, val)
def _insert(node: TreeNode | None, val: int) -> TreeNode:
if node is None:
return TreeNode(val)
if val < node.value:
node.left = _insert(node.left, val)
elif val > node.value:
node.right = _insert(node.right, val)
return node
def _search(node: TreeNode | None, val: int) -> bool:
if node is None:
return False
if val == node.value:
return True
if val < node.value:
return _search(node.left, val)
return _search(node.right, val)
В PHP готового сбалансированного дерева нет ни в ядре, ни в ext-ds:
\Ds\Set- это хеш-таблица (O(1) на add/contains, порядок вставки, без сортировки). Если нужен отсортированный обход, храни данные в массиве и сортируй (sort) или держи отсортированный массив с бинарным поиском. Дерево руками пиши только для учебных задач.
Удаление узла
Удаление - самая хитрая операция BST, потому что после него дерево должно остаться деревом поиска. Сначала узел находим обычным спуском, потом смотрим, сколько у него детей:
- Лист (детей нет) - просто убираем узел.
- Один потомок - ставим потомка на место удаляемого узла.
- Два потомка - находим in-order преемника: минимальный узел правого поддерева (идём направо один раз, потом влево до упора). Копируем его значение в удаляемый узел, а самого преемника удаляем из правого поддерева. У преемника нет левого потомка, поэтому его удаление сводится к случаю 1 или 2.
func (t *BST) Delete(val int) {
t.Root = deleteNode(t.Root, val)
}
func deleteNode(node *TreeNode, val int) *TreeNode {
if node == nil {
return nil // значения нет - нечего удалять
}
switch {
case val < node.Value:
node.Left = deleteNode(node.Left, val)
case val > node.Value:
node.Right = deleteNode(node.Right, val)
default:
// Случаи 1 и 2: лист или один потомок - поднимаем потомка
if node.Left == nil {
return node.Right
}
if node.Right == nil {
return node.Left
}
// Случай 3: два потомка - берём минимум правого поддерева
successor := node.Right
for successor.Left != nil {
successor = successor.Left
}
node.Value = successor.Value
node.Right = deleteNode(node.Right, successor.Value)
}
return node
}
Сложность та же, что у поиска: O(h), где h - высота дерева. На сбалансированном дереве это O(log n), на вырожденном O(n).
Обходы дерева
// Inorder: Left → Root → Right (отсортированный порядок!)
func inorder(node *TreeNode, result *[]int) {
if node == nil {
return
}
inorder(node.Left, result)
*result = append(*result, node.Value)
inorder(node.Right, result)
}
// Preorder: Root → Left → Right (для сериализации)
func preorder(node *TreeNode, result *[]int) {
if node == nil {
return
}
*result = append(*result, node.Value)
preorder(node.Left, result)
preorder(node.Right, result)
}
// Postorder: Left → Right → Root (для удаления)
func postorder(node *TreeNode, result *[]int) {
if node == nil {
return
}
postorder(node.Left, result)
postorder(node.Right, result)
*result = append(*result, node.Value)
}
// Level order (BFS)
func levelOrder(root *TreeNode) [][]int {
if root == nil {
return nil
}
var result [][]int
queue := []*TreeNode{root}
for len(queue) > 0 {
levelSize := len(queue)
var level []int
for i := 0; i < levelSize; i++ {
node := queue[0]
queue = queue[1:]
level = append(level, node.Value)
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
result = append(result, level)
}
return result
}
<?php
declare(strict_types=1);
final class TreeTraversal
{
/**
* @param array<int> $result
*/
public function inorder(?TreeNode $node, array &$result): void
{
if ($node === null) {
return;
}
$this->inorder($node->left, $result);
$result[] = $node->value;
$this->inorder($node->right, $result);
}
/**
* @param array<int> $result
*/
public function preorder(?TreeNode $node, array &$result): void
{
if ($node === null) {
return;
}
$result[] = $node->value;
$this->preorder($node->left, $result);
$this->preorder($node->right, $result);
}
/**
* @param array<int> $result
*/
public function postorder(?TreeNode $node, array &$result): void
{
if ($node === null) {
return;
}
$this->postorder($node->left, $result);
$this->postorder($node->right, $result);
$result[] = $node->value;
}
/**
* @return array<int, array<int>>
*/
public function levelOrder(?TreeNode $root): array
{
if ($root === null) {
return [];
}
$result = [];
$queue = new SplQueue();
$queue->enqueue($root);
while (!$queue->isEmpty()) {
$levelSize = count($queue);
$level = [];
for ($i = 0; $i < $levelSize; $i++) {
/** @var TreeNode $node */
$node = $queue->dequeue();
$level[] = $node->value;
if ($node->left !== null) {
$queue->enqueue($node->left);
}
if ($node->right !== null) {
$queue->enqueue($node->right);
}
}
$result[] = $level;
}
return $result;
}
}
from collections import deque
def inorder(node: TreeNode | None, result: list[int]) -> None:
"""Left -> Root -> Right (отсортированный порядок!)."""
if node is None:
return
inorder(node.left, result)
result.append(node.value)
inorder(node.right, result)
def preorder(node: TreeNode | None, result: list[int]) -> None:
"""Root -> Left -> Right (для сериализации)."""
if node is None:
return
result.append(node.value)
preorder(node.left, result)
preorder(node.right, result)
def postorder(node: TreeNode | None, result: list[int]) -> None:
"""Left -> Right -> Root (для удаления)."""
if node is None:
return
postorder(node.left, result)
postorder(node.right, result)
result.append(node.value)
# Level order (BFS)
def level_order(root: TreeNode | None) -> list[list[int]]:
if root is None:
return []
result: list[list[int]] = []
# deque: popleft за O(1), в отличие от list.pop(0)
queue: deque[TreeNode] = deque([root])
while queue:
level_size = len(queue)
level: list[int] = []
for _ in range(level_size):
node = queue.popleft()
level.append(node.value)
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
result.append(level)
return result
Сложность
| Операция | Среднее | Худшее (вырожденное) |
|---|---|---|
| Поиск | O(log n) | O(n) |
| Вставка | O(log n) | O(n) |
| Удаление | O(log n) | O(n) |
Вырожденное дерево - когда все элементы вставлены по порядку и дерево превращается в список.
Рекурсивные insert и search на вырожденном дереве имеют глубину n. В Python это RecursionError уже около 1000 элементов (лимит рекурсии по умолчанию), в Go - рост стека горутины. Для больших данных пиши итеративную версию или используй сбалансированное дерево.
ℹ️ Сбалансированные деревья
Сбалансированным называют дерево, у которого высота на n узлах около log₂ n: каждый следующий уровень вмещает вдвое больше узлов, чем предыдущий, поэтому до любого узла не больше log₂ n шагов. В реальных системах используют AVL-деревья или Red-Black деревья, которые держат дерево сбалансированным и тем гарантируют O(log n). После каждой вставки и удаления они восстанавливают баланс поворотами (ротациями) узлов. AVL держит разницу высот поддеревьев не больше 1, поэтому дерево ниже и поиск чуть быстрее, но вставки чаще требуют ротаций. Red-Black допускает перекос до 2 раз по высоте и делает меньше ротаций, поэтому его чаще берут для структур с частыми изменениями. В Go стандартная
mapиспользует hash table, а не дерево. B-tree - основа индексов в PostgreSQL.
Куча: дерево в массиве
Ещё одно важное дерево - двоичная куча (binary heap), на которой строится очередь с приоритетом. Это не дерево поиска: правило другое. В min-heap каждый родитель не больше своих детей, поэтому минимум всегда в корне, а порядок между братьями не важен. Куча всегда почти полная, и её хранят прямо в массиве: дети элемента i лежат в 2i+1 и 2i+2. Вставка и извлечение минимума - O(log n): элемент «всплывает» или «тонет» по одной ветке.
Классическая задача - top-K: найти K наибольших из n чисел. Сортировать всё - O(n log n). Быстрее держать min-heap размера K: в корне лежит самый маленький из текущих K лучших. Каждое новое число сравниваем с корнем: если оно больше, заменяем корень и восстанавливаем кучу за O(log K). Итого O(n log K) времени и O(K) памяти.
// IntHeap - min-heap из урока про очередь с приоритетом
// (Len, Less, Swap, Push, Pop для container/heap).
func topK(nums []int, k int) []int {
h := &IntHeap{}
for _, x := range nums {
if h.Len() < k {
heap.Push(h, x)
} else if k > 0 && x > (*h)[0] {
(*h)[0] = x // заменяем минимум
heap.Fix(h, 0) // и восстанавливаем кучу: O(log k)
}
}
return *h // K наибольших, в порядке кучи
}
// topK([]int{5, 1, 9, 3, 7, 2}, 3) -> 3 наибольших: 5, 7, 9
<?php
declare(strict_types=1);
/**
* @param list<int> $nums
* @return list<int>
*/
function topK(array $nums, int $k): array
{
$heap = new SplMinHeap(); // в корне - минимум из текущих K лучших
foreach ($nums as $x) {
if ($heap->count() < $k) {
$heap->insert($x);
} elseif ($k > 0 && $x > $heap->top()) {
$heap->extract(); // убираем минимум
$heap->insert($x); // O(log k)
}
}
return iterator_to_array($heap, false); // извлекает элементы по возрастанию
}
// topK([5, 1, 9, 3, 7, 2], 3) -> [5, 7, 9]
import heapq
def top_k(nums: list[int], k: int) -> list[int]:
h: list[int] = [] # min-heap: в h[0] минимум из текущих K лучших
for x in nums:
if len(h) < k:
heapq.heappush(h, x)
elif k > 0 and x > h[0]:
heapq.heapreplace(h, x) # pop минимума + push за O(log k)
return h
# top_k([5, 1, 9, 3, 7, 2], 3) -> 3 наибольших: 5, 7, 9
# (в стандартной библиотеке есть готовое: heapq.nlargest(k, nums))