Введение
Двоичное дерево поиска (BST) — это тип двоичного дерева, в котором каждый узел имеет не более двух дочерних узлов, называемых левым дочерним элементом и правым дочерним элементом. Для каждого узла левое поддерево содержит только узлы со значениями меньше значения узла, а правое поддерево содержит только узлы со значениями больше значения узла. BST используются для эффективных операций поиска, вставки и удаления.

Зачем использовать двоичное дерево поиска?
BST имеют ряд преимуществ:

Эффективный поиск: средняя временная сложность поиска, вставки и удаления равна O(log n).
Динамический набор элементов: поддерживает динамические операции, в отличие от статических массивов.
Упорядоченные элементы: упорядоченный обход BST дает элементы в отсортированном порядке.
Пошаговое руководство по созданию BST
Шаг 1. Определите структуру узла
Первым шагом является определение структуры узла в дереве. Каждый узел будет иметь три атрибута: значение, ссылку на левого дочернего элемента и ссылку на правого дочернего элемента.

public class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

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

Шаг 2. Создайте класс BST с помощью конструктора
Далее мы создаем класс BST, содержащий ссылку на корень дерева и методы вставки элементов.

public class BinarySearchTree {
    TreeNode root;

    public BinarySearchTree() {
        this.root = null;
    }
}

Шаг 3. Реализуйте метод вставки
Чтобы вставить элемент в BST, нам нужно найти правильную позицию для нового узла. Метод вставки обычно реализуется как рекурсивная функция.

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

private TreeNode insertRec(TreeNode root, int value) {
    // Base case: if the tree is empty, return a new node
    if (root == null) {
        root = new TreeNode(value);
        return root;
    }

    // Otherwise, recur down the tree
    if (value  root.value) {
        root.right = insertRec(root.right, value);
    }

    // Return the (unchanged) node pointer
    return root;
}

Визуализация
Чтобы лучше понять, как работает вставка, рассмотрим пример. Предположим, мы хотим вставить в BST следующую последовательность чисел: 50, 30, 70, 20, 40, 60, 80.

50

  50
 /
30

  50
 /  \
30  70

50
 /  \
30  70
/

Вставьте 40:

  50
 /  \
30  70
/ \

Вставьте 60

  50
 /  \
30  70
/ \  /

Вставьте 80:

  50
 /  \
30  70
/ \  / \

Полный код
Вот полный код для создания BST и вставки элементов:

public class BinarySearchTree {
    TreeNode root;

    public BinarySearchTree() {
        this.root = null;
    }

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

    private TreeNode insertRec(TreeNode root, int value) {
        if (root == null) {
            root = new TreeNode(value);
            return root;
        }

        if (value  root.value) {
            root.right = insertRec(root.right, value);
        }

        return root;
    }

    // Additional methods for traversal, search, and delete can be added here

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        int[] values = {50, 30, 70, 20, 40, 60, 80};
        for (int value : values) {
            bst.insert(value);
        }

        // Add code to print or traverse the tree
    }
}

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

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