Avl 트리 삭제에서 더 높은 우선 순위를 가진 하위 트리

Question

Avl 트리에서 2 명의 자식이있는 노드를 삭제할 때 .. 그 후속 노드 (오른쪽 하위 트리의 최소값) 또는 선행 작업 (왼쪽 하위 트리의 최대 값).

내 질문은 : 표준에서 어떤 서브 트리를 노드와 교환합니까? 후임자 또는 전임자입니까?

감사합니다. :)

Answer 1

이후에 필요한 모든 조정을 수행하면 두 알고리즘 중 하나를 사용할 수 있습니다. 알고리즘은 어느쪽으로 든 작동합니다.

당신이 정말로 영리하고 싶다면, 나중에 가장 적은 재조정을 요구하는 것을 기반으로 어느 하나를 선택할 수 있습니다. 그보다 더 큰 또는 다음 작은 키를 선택하는 것보다 훨씬 복잡합니다.