핵심 요약
Microsoft Developer가 이진 트리의 노드를 상수 공간으로 비재귀적으로 삭제하는 알고리즘을 제시했다.
구현 방법
- 포인터 조작 기반의 C++ 구현으로, 루트에서 시작해 왼쪽most 노드를 찾고 오른쪽 서브트리를 왼쪽most의 왼쪽에 접목한다.
- 루트를 삭제하고 왼쪽 자식을 새 루트로 승격하는 과정을 트리가 남아 있는 동안 반복한다.
- 각 노드 삭제 시 왼쪽 포인터를 두 번, 오른쪽 포인터를 한 번씩 순회한다.
- 보너스: 루트에 오른쪽 자식이 없으면 null이 접목되어도 동작에 영향이 없다.
주요 결과
- 시간 복잡도: O(n) — 각 노드 한 번 삭제, 오른쪽 링크 한 번 접목, 왼쪽 링크 두 번 순회
- 공간 복잡도: 상수 공간 사용
- 구현이 간결하고 프리오더 유사한 삭제 순서를 보장한다.
