자료구조...65

이진 탐색 트리의 삭제 연산

삭제 연산의 경우 삭제되는 노드가 가진 자식의 수에 따라 연산이 달라지게 된다.

• 자식 노드가 없는 경우 대상 노드를 제거하고 연산을 종료한다.
• 자식 노드가 하나인 경우 대상 노드를 제거하고 자식 노드와 위치를 바꾼다.
• 자식 노드가 두 개인 경우 왼쪽 자식을 선택할지 오른쪽 자식을 선택할지에 따라 연산이 달라진다.
  • 왼쪽 자식에게 계승하는 경우 대상 노드 삭제 후 왼쪽 서브 트리에서 가장 큰 값을 가진 노드와 위치를 바꾼다.
  • 오른쪽 자식에게 계승하는 경우 대상 노드 삭제 후 오른쪽 서브 트리에서 가장 작은 값을 가진 노드와 위치를 바꾼다.