이진 트리에서 노드를 삭제할 때의 시간 복잡도는 무엇입니까

Question

이진 트리에서 노드를 삭제하려면 노드를 검색해야합니다. 이는 최소 O (log N) 및 최대 O (N)에서 가능합니다. 노드에 따라 포인터를 다시 정렬해야합니다. 우리는 어떻게 그것의 시간 복잡성을 계산합니까?

Answer 1

대부분의 복잡성으로 인해 노드가 검색됩니다. 일단 부모 노드가 유지되는 한 노드를 삭제하기위한 추가 할당이 있습니다. 그래서 그것은 일정한 순서입니다.

Answer 2

삭제 작업 방식에 따라 다릅니다. 가장 일반적인 방법은 노드의 후계자를 찾은 다음 노드를 그 후임자로 교체하는 것입니다. 이 작업은 O (h)에서 수행 할 수 있습니다. 여기서 h는 트리의 높이입니다. 최악의 경우 이것은 O (n)이지만 균형 잡힌 트리에서는 최악의 경우 O (lg n)입니다.

Answer 3

여기서 "최악 검색 시간은 최대 O (N)"가됩니까? 그것은 BST에서 결코 일어나서는 안됩니다. 최악의 경우 검색 및 삭제에는 최대 O (h) 여야합니다. 여기서 'h'는 트리의 높이입니다. 이 부분은 helpful article입니다.

Answer 4

예 최상의 경우 복잡성 O (logn) (때 완벽하게 균형) 및
최악의 경우 복잡성 (n)은
1 O입니다 - 2 - 3 - BST 삭제 4

그러나 주요 문제 (Hibbard 삭제)는 대칭이 아니라는 것입니다. 많은 삽입 및 삭제 후에 BST는 균형이 약합니다. 연구자들은 나무의 무작위 삽입 및 삭제 높이가 충분히 길면 sqrt (n)이된다는 것을 증명했습니다. 그래서 지금은 모든 작업 (검색, 삽입, 삭제)은 sqrt (n)과 비교하여 좋지 않은 시간이 걸릴 것입니다.

BST를위한 효율적인 대칭 삭제 문제가 매우 오래 지속되어 (약 50 년) 열려 있습니다. 균형 잡힌 나무를 보장하기 위해 우리는 RedBlack Tree 등을 사용해야합니다.