핵심 요약
Microsoft Developer의 글은 부모 포인터를 합성해 이진 트리를 상수 공간에서 비재귀적으로 삭제하는 방법과 포인터 재사용 트릭을 제시합니다.
구현 방법
- 구조체 Node{ Node* left; Node* right; Data d; }를 사용
- 왼쪽으로 내려가며 left를 임시 부모로 바꾸고 현재 부모를 저장하기 위해 std::exchange를 활용
- 더 이상 왼쪽이 없으면 node->left에 부모를 연결하고 오른쪽으로 진행
- 바닥에 도달하면 노드를 삭제하고 상위로 복귀하는 루프를 반복
- 상위로 복귀 시 왼쪽/오른쪽에서 왔는지 추적하는 안전한 포인터 관리 필요
주요 결과
- 비재귀적 이진 트리 삭제가 가능하다는 구현 아이디어 제시
- 포인터 재사용으로 추가 공간 의존도 감소
- Code Golf의 다른 접근 방식과의 차이도 논의될 수 있음
