Удаление в бинарном дереве поиска

Question

Почему удаление в BST является операцией O (log (n)).Как я понимаю, это включает в себя освобождение узла и указание родительской ссылки на NULL.Не должно ли это занять O (1)

Answer 1

Ожидается O (lg n ), если вы начинаете с корня дерева: тогда вам нужно найти элемент, который нужно удалить, а затем его преемника по порядку.

Answer 2

Проблема заключается в том, как удалить узел, у которого есть два потомка - дерево должно быть реструктурировано, чтобы дети нашли подходящих новых родителей.Подробное объяснение здесь .Google твой друг.

Answer 3

Удаление в бинарном дереве поиска - это O (h), где h - высота дерева.

Теперь, когда вы не упомянули, является ли дерево сбалансированным или нет, сложность наихудшего случая для несбалансированногодерево будет O (n), т. е. когда оно является вырожденным деревом.

Если bst является одним из сбалансированных (Avl, красный черный и т. д.), то сложность в худшем случае будет O (lgn) поскольку высота практически всех сбалансированных bst равна K * (lg n).

Например, для дерева avl k = 1 и для красного черного дерева K = 2.

Answer 4

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