Какими свойствами обладает бинарное дерево поиска

Бинарное дерево поиска (BST) — это структура данных, где каждый узел имеет не более двух потомков (левый и правый). Основные свойства:

1. Упорядоченность: Для любого узла:
   • Все значения в левом поддереве меньше значения узла.
   • Все значения в правом поддереве больше или равны значению узла.

2. Рекурсивная структура: Левый и правый потомки сами являются BST.

3. Эффективный поиск: В среднем случае операции (вставка, удаление, поиск) выполняются за O(log n), но в худшем (вырожденное дерево) — O(n).

Пример BST:

class Node {
    int value;
    Node left, right;
    Node(int value) { this.value = value; }
}

// Поиск в BST
Node search(Node root, int key) {
    if (root == null || root.value == key) return root;
    return (key < root.value) 
        ? search(root.left, key) 
        : search(root.right, key);
}