Дерево поиска BST

Дерево поиска BST (Binary Search Tree)

Свойство BST

Для каждого узла N: все значения в левом поддереве < N, все в правом поддереве > N.

        8
       / \
      3   10
     / \    \
    1   6   14
       / \  /
      4  7 13

Inorder: 1, 3, 4, 6, 7, 8, 10, 13, 14 (отсортировано!)

Поиск — O(h)

<?php
declare(strict_types=1);

function searchBst(?TreeNode $root, int $target): ?TreeNode
{
    if ($root === null) {
        return null;
    }
    if ($target === $root->val) {
        return $root;
    }

    return $target < $root->val
        ? searchBst($root->left, $target)
        : searchBst($root->right, $target);
}

// Iterative
function searchBstIter(?TreeNode $root, int $target): ?TreeNode
{
    while ($root !== null) {
        if ($target === $root->val) {
            return $root;
        }
        $root = $target < $root->val ? $root->left : $root->right;
    }

    return null;
}

// searchBst searches for a value in BST (recursive).
func searchBst(root *TreeNode, target int) *TreeNode {
	if root == nil {
		return nil
	}
	if target == root.Val {
		return root
	}

	if target < root.Val {
		return searchBst(root.Left, target)
	}
	return searchBst(root.Right, target)
}

// searchBstIter searches for a value in BST (iterative).
func searchBstIter(root *TreeNode, target int) *TreeNode {
	for root != nil {
		if target == root.Val {
			return root
		}
		if target < root.Val {
			root = root.Left
		} else {
			root = root.Right
		}
	}
	return nil
}

// SearchBst searches for a value in BST (recursive).
static TreeNode? SearchBst(TreeNode? root, int target)
{
    if (root is null)
    {
        return null;
    }
    if (target == root.Val)
    {
        return root;
    }

    return target < root.Val
        ? SearchBst(root.Left, target)
        : SearchBst(root.Right, target);
}

// SearchBstIter searches for a value in BST (iterative).
static TreeNode? SearchBstIter(TreeNode? root, int target)
{
    while (root is not null)
    {
        if (target == root.Val)
        {
            return root;
        }
        root = target < root.Val ? root.Left : root.Right;
    }

    return null;
}

from __future__ import annotations

def search_bst(root: TreeNode | None, target: int) -> TreeNode | None:
    """Search for a value in BST (recursive)."""
    if root is None:
        return None
    if target == root.val:
        return root

    return (
        search_bst(root.left, target)
        if target < root.val
        else search_bst(root.right, target)
    )

def search_bst_iter(root: TreeNode | None, target: int) -> TreeNode | None:
    """Search for a value in BST (iterative)."""
    while root is not None:
        if target == root.val:
            return root
        root = root.left if target < root.val else root.right

    return None

Визуализация поиска числа 7:

        8       8 > 7, идём влево
       / \
      3   10    3 < 7, идём вправо
     / \
    1   6       6 < 7, идём вправо
       / \
      4   7     7 == 7, нашли!

Вставка — O(h)

<?php
declare(strict_types=1);

function insertBst(?TreeNode $root, int $val): TreeNode
{
    if ($root === null) {
        return new TreeNode($val);
    }

    if ($val < $root->val) {
        $root->left = insertBst($root->left, $val);
    } elseif ($val > $root->val) {
        $root->right = insertBst($root->right, $val);
    }

    return $root;
}

func insertBst(root *TreeNode, val int) *TreeNode {
	if root == nil {
		return &TreeNode{Val: val}
	}

	if val < root.Val {
		root.Left = insertBst(root.Left, val)
	} else if val > root.Val {
		root.Right = insertBst(root.Right, val)
	}

	return root
}

static TreeNode InsertBst(TreeNode? root, int val)
{
    if (root is null)
    {
        return new TreeNode(val);
    }

    if (val < root.Val)
    {
        root.Left = InsertBst(root.Left, val);
    }
    else if (val > root.Val)
    {
        root.Right = InsertBst(root.Right, val);
    }

    return root;
}

def insert_bst(root: TreeNode | None, val: int) -> TreeNode:
    if root is None:
        return TreeNode(val)

    if val < root.val:
        root.left = insert_bst(root.left, val)
    elif val > root.val:
        root.right = insert_bst(root.right, val)

    return root

Вставка 5 в BST:

        8              8
       / \            / \
      3   10   ->    3   10
     / \    \       / \    \
    1   6   14     1   6   14
       / \            / \
      4   7          4   7
                    /
                   5  <- новый узел

Удаление — O(h)

Три случая:

Лист — просто удаляем
Один потомок — заменяем узел потомком
Два потомка — заменяем inorder-преемником (наименьший в правом поддереве)

<?php
declare(strict_types=1);

function deleteBst(?TreeNode $root, int $key): ?TreeNode
{
    if ($root === null) {
        return null;
    }

    if ($key < $root->val) {
        $root->left = deleteBst($root->left, $key);
    } elseif ($key > $root->val) {
        $root->right = deleteBst($root->right, $key);
    } else {
        // Found the node to delete
        // Case 1 & 2: missing one child
        if ($root->left === null) {
            return $root->right;
        }
        if ($root->right === null) {
            return $root->left;
        }

        // Case 3: two children
        // Find inorder successor (minimum of right subtree)
        $successor = $root->right;
        while ($successor->left !== null) {
            $successor = $successor->left;
        }

        $root->val = $successor->val;
        $root->right = deleteBst($root->right, $successor->val);
    }

    return $root;
}

func deleteBst(root *TreeNode, key int) *TreeNode {
	if root == nil {
		return nil
	}

	if key < root.Val {
		root.Left = deleteBst(root.Left, key)
	} else if key > root.Val {
		root.Right = deleteBst(root.Right, key)
	} else {
		// Found the node to delete
		// Case 1 & 2: missing one child
		if root.Left == nil {
			return root.Right
		}
		if root.Right == nil {
			return root.Left
		}

		// Case 3: two children
		// Find inorder successor (minimum of right subtree)
		successor := root.Right
		for successor.Left != nil {
			successor = successor.Left
		}

		root.Val = successor.Val
		root.Right = deleteBst(root.Right, successor.Val)
	}

	return root
}

static TreeNode? DeleteBst(TreeNode? root, int key)
{
    if (root is null)
    {
        return null;
    }

    if (key < root.Val)
    {
        root.Left = DeleteBst(root.Left, key);
    }
    else if (key > root.Val)
    {
        root.Right = DeleteBst(root.Right, key);
    }
    else
    {
        // Found the node to delete
        // Case 1 & 2: missing one child
        if (root.Left is null)
        {
            return root.Right;
        }
        if (root.Right is null)
        {
            return root.Left;
        }

        // Case 3: two children
        // Find inorder successor (minimum of right subtree)
        TreeNode successor = root.Right;
        while (successor.Left is not null)
        {
            successor = successor.Left;
        }

        root.Val = successor.Val;
        root.Right = DeleteBst(root.Right, successor.Val);
    }

    return root;
}

def delete_bst(root: TreeNode | None, key: int) -> TreeNode | None:
    if root is None:
        return None

    if key < root.val:
        root.left = delete_bst(root.left, key)
    elif key > root.val:
        root.right = delete_bst(root.right, key)
    else:
        # Found the node to delete
        # Case 1 & 2: missing one child
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left

        # Case 3: two children
        # Find inorder successor (minimum of right subtree)
        successor = root.right
        while successor.left is not None:
            successor = successor.left

        root.val = successor.val
        root.right = delete_bst(root.right, successor.val)

    return root

Удаление узла 3 (два потомка):

        8                    8
       / \                  / \
      3   10    ->         4   10
     / \    \             / \    \
    1   6   14           1   6   14
       / \                  / \
      4   7                5   7
       \
        5

Inorder-преемник 3 = 4 (минимум правого поддерева)
Заменяем значение 3 на 4, удаляем старый узел 4

Задача: Validate BST

<?php
declare(strict_types=1);

function isValidBst(?TreeNode $root): bool
{
    return validate($root, PHP_INT_MIN, PHP_INT_MAX);
}

function validate(?TreeNode $node, int $minVal, int $maxVal): bool
{
    if ($node === null) {
        return true;
    }
    if ($node->val <= $minVal || $node->val >= $maxVal) {
        return false;
    }

    return validate($node->left, $minVal, $node->val)
        && validate($node->right, $node->val, $maxVal);
}

import "math"

func isValidBst(root *TreeNode) bool {
	return validate(root, math.MinInt64, math.MaxInt64)
}

func validate(node *TreeNode, minVal, maxVal int) bool {
	if node == nil {
		return true
	}
	if node.Val <= minVal || node.Val >= maxVal {
		return false
	}

	return validate(node.Left, minVal, node.Val) &&
		validate(node.Right, node.Val, maxVal)
}

static bool IsValidBst(TreeNode? root) => Validate(root, long.MinValue, long.MaxValue);

// Bounds are long so that int.MinValue/int.MaxValue node values stay valid.
static bool Validate(TreeNode? node, long minVal, long maxVal)
{
    if (node is null)
    {
        return true;
    }
    if (node.Val <= minVal || node.Val >= maxVal)
    {
        return false;
    }

    return Validate(node.Left, minVal, node.Val)
        && Validate(node.Right, node.Val, maxVal);
}

def is_valid_bst(root: TreeNode | None) -> bool:
    return validate(root, float("-inf"), float("inf"))

# Python ints are unbounded, so infinite floats are the natural sentinels.
def validate(node: TreeNode | None, min_val: float, max_val: float) -> bool:
    if node is None:
        return True
    if node.val <= min_val or node.val >= max_val:
        return False

    return validate(node.left, min_val, node.val) and validate(
        node.right, node.val, max_val
    )

## Задача: Lowest Common Ancestor (BST)

В BST это проще, чем в обычном дереве:

<?php
declare(strict_types=1);

function lcaBst(?TreeNode $root, TreeNode $p, TreeNode $q): ?TreeNode
{
    while ($root !== null) {
        if ($p->val < $root->val && $q->val < $root->val) {
            $root = $root->left;      // Both on the left
        } elseif ($p->val > $root->val && $q->val > $root->val) {
            $root = $root->right;     // Both on the right
        } else {
            return $root;             // Split point — this is LCA
        }
    }

    return null;
}

func lcaBst(root, p, q *TreeNode) *TreeNode {
	for root != nil {
		if p.Val < root.Val && q.Val < root.Val {
			root = root.Left // both on the left
		} else if p.Val > root.Val && q.Val > root.Val {
			root = root.Right // both on the right
		} else {
			return root // split point — this is LCA
		}
	}
	return nil
}

static TreeNode? LcaBst(TreeNode? root, TreeNode p, TreeNode q)
{
    while (root is not null)
    {
        if (p.Val < root.Val && q.Val < root.Val)
        {
            root = root.Left;         // both on the left
        }
        else if (p.Val > root.Val && q.Val > root.Val)
        {
            root = root.Right;        // both on the right
        }
        else
        {
            return root;              // split point — this is LCA
        }
    }

    return null;
}

def lca_bst(root: TreeNode | None, p: TreeNode, q: TreeNode) -> TreeNode | None:
    while root is not None:
        if p.val < root.val and q.val < root.val:
            root = root.left      # both on the left
        elif p.val > root.val and q.val > root.val:
            root = root.right     # both on the right
        else:
            return root           # split point — this is LCA

    return None

## Задача: Kth Smallest Element

<?php
declare(strict_types=1);

function kthSmallest(?TreeNode $root, int $k): int
{
    $stack = [];
    $current = $root;

    while ($current !== null || $stack !== []) {
        while ($current !== null) {
            $stack[] = $current;
            $current = $current->left;
        }

        $current = array_pop($stack);
        $k--;
        if ($k === 0) {
            return $current->val;
        }

        $current = $current->right;
    }

    throw new \RuntimeException('k is out of range');
}

import "errors"

func kthSmallest(root *TreeNode, k int) (int, error) {
	var stack []*TreeNode
	current := root

	for current != nil || len(stack) > 0 {
		for current != nil {
			stack = append(stack, current)
			current = current.Left
		}

		current = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		k--
		if k == 0 {
			return current.Val, nil
		}

		current = current.Right
	}

	return 0, errors.New("k is out of range")
}

static int KthSmallest(TreeNode? root, int k)
{
    var stack = new Stack<TreeNode>();
    TreeNode? current = root;

    while (current is not null || stack.Count > 0)
    {
        while (current is not null)
        {
            stack.Push(current);
            current = current.Left;
        }

        current = stack.Pop();
        k--;
        if (k == 0)
        {
            return current.Val;
        }

        current = current.Right;
    }

    throw new ArgumentOutOfRangeException(nameof(k), "k is out of range");
}

def kth_smallest(root: TreeNode | None, k: int) -> int:
    stack: list[TreeNode] = []
    current = root

    while current is not None or stack:
        while current is not None:
            stack.append(current)
            current = current.left

        current = stack.pop()
        k -= 1
        if k == 0:
            return current.val

        current = current.right

    raise ValueError("k is out of range")

## Проблема балансировки

BST гарантирует O(h), но h может быть O(n) для вырожденного дерева.

Сбалансированное:          Вырожденное (вставка 1,2,3,4,5):
      3                    1
     / \                    \
    2   4                    2
   /     \                    \
  1       5                    3
                                \
h = 2, O(log n)                  4
                                  \
                                   5
                            h = 4, O(n)

Операция	Сбалансированное	Вырожденное
Поиск	O(log n)	O(n)
Вставка	O(log n)	O(n)
Удаление	O(log n)	O(n)

Решения: AVL-деревья и Red-Black деревья (следующая глава).

Запомни: BST = левое < узел < правое. Inorder обход = отсортированные данные. Все операции O(h), где h = log n для сбалансированного и n для вырожденного. Удаление узла с двумя потомками: заменить inorder-преемником. Валидация BST — через передачу диапазона (min, max).

Итоги

BST: left < node < right для каждого узла
Поиск, вставка, удаление = O(h)
Inorder обход BST = отсортированная последовательность
Удаление с двумя потомками: найти inorder-преемника
Без балансировки BST может деградировать до O(n)