Какие основные характеристики отличают бинарное дерево поиска?

Бинарное дерево поиска (Binary Search Tree, BST) обладает следующими основными характеристиками:

• Каждый узел содержит ключ (значение).
• Для любого узла все ключи в левом поддереве меньше ключа этого узла.
• Все ключи в правом поддереве больше ключа этого узла.
• Левое и правое поддерево также являются бинарными деревьями поиска.

Это позволяет эффективно выполнять операции поиска, вставки и удаления со средней сложностью O(log n), если дерево сбалансировано.

Пример вставки в BST на Java:

class Node {
    int key;
    Node left, right;

    public Node(int item) {
        key = item;
        left = right = null;
    }
}

class BST {
    Node root;

    void insert(int key) {
        root = insertRec(root, key);
    }

    Node insertRec(Node root, int key) {
        if (root == null) {
            root = new Node(key);
            return root;
        }
        if (key < root.key)
            root.left = insertRec(root.left, key);
        else if (key > root.key)
            root.right = insertRec(root.right, key);
        return root;
    }
}