Какова временная сложность удаления узла в двоичном дереве

Question

Для удаления узла в двоичном дереве мы должны выполнить поиск узла. Это возможно при минимальном O (log N) и максимальном O (N). В зависимости от узла, мы должны переставить указатели. Как мы рассчитываем сложность времени этого.

Answer 1

Это зависит от того, как вы делаете удаление. Наиболее распространенным способом является поиск преемника узла, а затем замена узла этим преемником. Это можно сделать в O (h), где h - высота дерева. В худшем случае это O (n), но в сбалансированном дереве это худший вариант O (lg n).

Answer 2

Да, лучшая сложность случая O (logn) (когда идеально сбалансировано) исложность наихудшего случая - O (n)1 - 2 - 3 - 4

Но основная проблема с удалением BST (удаление Хиббарда) заключается в том, что он не симметричен.После многих вставок и удалений BST становится меньше баланса.Исследователи доказали, что после достаточно большого количества случайных вставок и удалений высота дерева становится sqrt (n) .так что теперь каждая операция (поиск, вставка, удаление) займет sqrt (n) время, что не очень хорошо по сравнению с O (logn) .

Это очень давняя (около 50 лет) открытая проблема для эффективного симметричного удаления для BST.для гарантированного сбалансированного дерева мы должны использовать RedBlack Tree и т. д.

Answer 3

Где вы получаете «худшее время поиска как max O (N)»?Это никогда не должно происходить в BST.В худшем случае это должно быть max O (h) для поиска и удаления, где «h» - высота дерева.Смотрите эту полезную статью .

Answer 4

Большая часть сложности заключается в поиске узла. Как только он был найден - пока родительский узел сохранен - ​​осталось всего несколько назначений для удаления узла. Так что это постоянный порядок.