🌳 Бинарное дерево поиска (BST)

BST — это бинарное дерево, где:

• Значение в левой ветви меньше значения в узле.

• Значение в правой ветви больше значения в узле.

Такое свойство обеспечивает эффективный поиск, вставку и удаление — в среднем за O(log n).

Пример реализации:

class Node
{
    public int Value;
    public Node Left;
    public Node Right;

    public Node(int value)
    {
        Value = value;
        Left = Right = null;
    }

    // Вставка нового значения в дерево
    public void Insert(int value)
    {
        if (value < Value)
        {
            if (Left == null)
                Left = new Node(value);
            else
                Left.Insert(value);
        }
        else if (value > Value)
        {
            if (Right == null)
                Right = new Node(value);
            else
                Right.Insert(value);
        }
    }

    // Поиск значения в дереве
    public Node Search(int value)
    {
        if (value == Value)
            return this;
        if (value < Value && Left != null)
            return Left.Search(value);
        if (value > Value && Right != null)
            return Right.Search(value);
        return null;
    }

    // Обход дерева в порядке (LNR - InOrder)
    public void InOrderTraversal()
    {
        if (Left != null)
            Left.InOrderTraversal();
        
        Console.Write(Value + " ");

        if (Right != null)
            Right.InOrderTraversal();
    }
}

Как это работает?

1️⃣ Вставка:

• Если значение меньше текущего узла, идём в левое поддерево.

• Если больше — в правое.

• Если узел пуст, создаём новый.

2️⃣ Поиск:

• Сравниваем искомое значение с текущим.

• Меньше — идём влево, больше — вправо, равное — нашли.

3️⃣ Обход:

• In-order обход (LNR) обходит узлы в отсортированном порядке.

💬 А вы уже реализовали BST? Делитесь опытом и вопросами в комментариях!

🐸Библиотека шарписта