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

Удаление вершины по значению из бинарного дерева

Операция, которая позволяет удалить узел без потомков из структуры дерева.

Краткий алгоритм удаления узла, который имеет как левое, так и правое поддерево:
1. Найдите в дереве вершину, которую надо удалить.
2. Если у узла есть и левое, и правое поддерево, найти наибольший (или наименьший) элемент в левом (или правом) поддереве.
3. Заменить значение удаляемого узла значением найденного элемента.
4. Удалить найденный элемент из левого (или правого) поддерева.

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

www.tgoop.com/the_algorithms/4650

5.9K viewsDec 23, 2023 at 09:03

Удаление вершины по значению из бинарного дерева

Операция, которая позволяет удалить узел без потомков из структуры дерева.

Краткий алгоритм удаления узла, который имеет как левое, так и правое поддерево:
1. Найдите в дереве вершину, которую надо удалить.
2. Если у узла есть и левое, и правое поддерево, найти наибольший (или наименьший) элемент в левом (или правом) поддереве.
3. Заменить значение удаляемого узла значением найденного элемента.
4. Удалить найденный элемент из левого (или правого) поддерева.

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

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