Метод вставки дерева двоичного поиска в Java

В блоке кода необходимо отредактировать два момента.

• Завершить процесс, если дерево пусто: после проверки isEmpty(), если дерево пусто, я добавил оператор возврата после установки нового узла в качестве корневого. Это предотвращает ненужное зацикливание.

• Инициализация родительской переменной: перед циклом я инициализировал родительскую переменную нулевым значением. Это важно для обеспечения правильного обновления родительских и текущих переменных внутри цикла.

    public void insert(int number) {
        Node newNode = new Node(number);
  
        if (isEmpty()) {
            root = newNode;
            return; // End Process If Tree is Empty.
        }
  
        Node current = root;
        Node parent = null; // Initializing the Parent Variable
  
        while (true) {
            parent = current;
            if (current.data > number) {
                current = current.left;
                if (current == null) {
                    parent.left = newNode;
                    return;
                }
            } else {
                current = current.right;
                if (current == null) {
                    parent.right = newNode;
                    return;
                }
            }
        }
    }
  

Надеюсь, это было полезно.

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

private Node insert(Node current, int number) {
    if (current == null) {
        return new Node(number);
    }

    if (number < current.data) {
        current.left = insert(current.left, number);
    } else if (number > current.data) {
        current.right = insert(current.right, number);
    }

    return current;
}

Объяснение:

• Базовый случай: если узел current равен null, это означает, что мы нашли правильное место для вставки нового узла, поэтому мы создаем новый узел и возвращаем его.
• Рекурсивный случай:
  • Если number меньше данных узла current, метод рекурсивно обращается к левому поддереву.
  • Если number больше, он рекурсивно переходит в правое поддерево.
• Возврат: метод возвращает узел current, чтобы гарантировать сохранение древовидной структуры.

Этот рекурсивный подход должен решить любые проблемы, возникающие при неправильной вставке значений как слева, так и справа. Он упрощает логику за счет естественного обхода дерева на основе сравнения между вставляемым number узлом и данными current узла.

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

Рекурсивный метод

Преимущества:

1. Читабельность и простота:

   • Рекурсивный метод зачастую более краток и понятен, поскольку он напрямую следует естественной рекурсивной структуре двоичного дерева. Он ясно выражает идею о том, что точка вставки каждого узла определяется путем рекурсивной проверки его левого или правого дочернего элемента.

2. Меньше кода:

   • Рекурсивный метод обычно требует меньше строк кода и более элегантен, что упрощает его поддержку и снижает вероятность ошибок в сложной логике.

3. Нет необходимости в отслеживании родителей:

   • В рекурсии вам не нужно вручную отслеживать родительский узел, поскольку рекурсивные вызовы естественным образом обрабатывают обход.

Недостатки:

1. Риск переполнения стека:

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

2. Накладные расходы на вызов функции:

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

Итерационный метод

Преимущества:

1. Избегает переполнения стека:

   • Итеративный метод, как правило, более безопасен с точки зрения использования стека, поскольку он не полагается на стек вызовов для обхода. Он больше подходит для очень больших деревьев или случаев, когда дерево может потерять равновесие.

2. Эффективность:

   • Поскольку итеративный метод позволяет избежать накладных расходов, связанных с вызовами функций в рекурсии, он может быть немного быстрее, особенно для очень больших наборов данных.

Недостатки:

1. Более сложный код:

   • Итеративный метод обычно требует большего количества кода, включая ручное управление родительскими указателями и более сложный поток управления, что затрудняет чтение и поддержку.

2. Ручное отслеживание родителей:

   • Вам необходимо вручную отслеживать родительский узел во время обхода, что усложняет работу и увеличивает вероятность возникновения ошибок.

Какой метод удобнее?

• Для обучения и читаемости: рекурсивный метод более удобен. Его легче понимать, поддерживать и он хорошо согласуется с концептуальной структурой двоичного дерева.

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