Для удаления узла в двоичном дереве нам нужно выполнить поиск узла. Это возможно в минимальном O (log N) и max O (N). В зависимости от узла мы должны переставить указатели. Как мы вычислим временную сложность этого.Какова временная сложность удаления узла в двоичном дереве
Большая часть сложности - поиск узла. Как только он будет найден - пока сохраняется родительский узел, удалить узел будет всего несколько. Так что это постоянный порядок.
Это зависит от того, как вы делаете удаление. Наиболее распространенным способом является поиск преемника узла, а затем замена узла этим преемником. Это можно сделать в O (h), где h - высота дерева. В худшем случае это O (n), но в сбалансированном дереве наихудший вариант O (lg n).
Где вы получаете "наихудшее время поиска как max O (N)"? Это никогда не должно происходить в BST. В худшем случае он должен быть максимальным O (h) для поиска и удаления, где «h» - высота дерева. См. Это helpful article.
O (h) может быть O (n) в патологически вырожденном дереве. – templatetypedef
Да лучше сложность случая O (LOGN) (при идеально сбалансированы) и
худший случай сложность O (п)
1 - 2 - 3 - 4
Но главная проблема с BST удалением (Hibbard Deletion) заключается в том, что он не симметричен. После того, как многие вставки и удаления BST становятся менее сбалансированными. Исследователи доказали, что после достаточно большого количества случайных вставок и высоты удаления дерева становится sqrt (n). так что теперь каждая операция (поиск, вставка, удаление) займет sqrt (n) время, которое не очень хорошо по сравнению с O (logn).
Это очень давняя проблема (около 50 лет) для эффективного симметричного удаления для BST. для гарантированного сбалансированного дерева, мы должны использовать RedBlack Tree и т. д.
+1, Nice и лаконичный. –