Удаление бинарного дерева поиска без копирования

При программировании простой структуры данных бинарного дерева поиска (не самоуравновешивающейся) большинство ресурсов дают совет при удалении узла с двумя дочерними элементами — копировать данные из одного левого дочернего элемента в удаляемый узел. Это плохая практика? Разве некоторые манипуляции с указателями не обеспечат более быстрых результатов? Есть ли алгоритм вращения BST, который может обобщить это?

1

Решение

Да, вы не хотите копировать узел, вы просто хотите «переместить» его (т.е. поменять указатели вокруг), чтобы поместить его на место удаляемого. Если вы не пытаетесь сохранить баланс, вам не нужно делать никакого поворота — вы просто выбираете самый правый узел в левом поддереве (или самый левый узел в правом поддереве). -tree). Вы удаляете это с текущего места и вставляете на место узла, который нужно удалить (все строго с помощью указателей).

1

Другие решения

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

0

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector