트리를 삭제하기 전에 트리를 회전하면 어떤 이점이 있습니까?

Question

this article을 통해 읽는 중입니다. 특정 방식으로 회전을 수행 한 다음 트리를 한 방향으로 이동하고 요소를 삭제하여 트리의 한면을 제거 할 수 있다고 언급합니다.

나는 그들이 무엇을하려하는지 이해하지만, 나는 이해할 수 없다. 왜 일까?

단순한 우편 주문 삭제와 비교하여 이러한 유형의 삭제가 제공 할 수있는 이점은 무엇입니까?

내가 생각할 수있는 장점 중 하나는 재귀에 사용되는 메모리를 절약하는 것입니다.하지만 트리를 두 번 통과하는 것과 달리 한 번 회전하고 삭제할 때와 비교하면 무시할 수없는 오버 헤드라고 생각합니다. 내가 여기서 뭔가를 놓치고 있니?

Answer 1

이 방법의 핵심은 재귀 (및 스택 공간 사용)를 피하는 것입니다. "흠 ... 노드를 다시 배열하여 왼쪽 하위 트리가없는 경우 어떻게해야합니까? 그런 다음 스택에있는 모든 것을 추적 할 필요없이 오른쪽으로 내려갈 수 있습니다. "

일반적으로 다른 종류의 메모리가 부족하기 오래 전에 스택 공간이 부족하기 때문에 깊이가 적당하다고 확신 할 수없는 경우 재귀를 피하는 것이 좋습니다. 일부 경우 시스템 재귀를 제한하여 무한 재귀를 일으키는 오류를 catch하도록 설계되었습니다. 그러나 여기에서는 이것이 중요하지 않다고 생각합니다. 동일한 패키지의 다른 루틴에 재귀가 필요하다는 것을 이미 인정한 곳입니다. 또한, 재귀의 깊이는 나무의 깊이에 달려 있으며, 균형 잡힌 나무의 경우 이것은 대략 노드의 수에 대한 로그 일 것이므로 너무 깊어서는 안됩니다.