Алгоритмы и структуры данных

Добавление элементов в бинарное дерево поиска

Операция, которая позволяет вставить новый элемент в дерево, сохраняя его структуру упорядоченной.

Алгоритм:
1. Если дерево пустое, создайте новый узел и сделайте его корневым.
2. Иначе, начните с корневого узла и сравните значение нового элемента со значением текущего узла.
3. Если значение нового элемента меньше значения текущего узла, перейдите к его левому поддереву.
- Если левого поддерева нет, создайте новый узел и сделайте его левым потомком текущего узла.
- Иначе, перейдите в левое поддерево и повторите шаги с пункта 2.
4. Если значение нового элемента больше или равно значению текущего узла, перейдите к его правому поддереву.
- Если правого поддерева нет, создайте новый узел и сделайте его правым потомком текущего узла.
- Иначе, перейдите в правое поддерево и повторите шаги с пункта 2.

Сложность: O(log n)

www.tgoop.com/the_algorithms/4644

5.8K viewsDec 19, 2023 at 09:02

Добавление элементов в бинарное дерево поиска

Операция, которая позволяет вставить новый элемент в дерево, сохраняя его структуру упорядоченной.

Алгоритм:
1. Если дерево пустое, создайте новый узел и сделайте его корневым.
2. Иначе, начните с корневого узла и сравните значение нового элемента со значением текущего узла.
3. Если значение нового элемента меньше значения текущего узла, перейдите к его левому поддереву.
- Если левого поддерева нет, создайте новый узел и сделайте его левым потомком текущего узла.
- Иначе, перейдите в левое поддерево и повторите шаги с пункта 2.
4. Если значение нового элемента больше или равно значению текущего узла, перейдите к его правому поддереву.
- Если правого поддерева нет, создайте новый узел и сделайте его правым потомком текущего узла.
- Иначе, перейдите в правое поддерево и повторите шаги с пункта 2.

Сложность: O(log n)

BY Алгоритмы и структуры данных