[자료구조] 이진 탐색 트리 Binary Search Tree

이진 탐색 트리 (Binary Search Tree)

 - 이진 트리에 탐색을 위한 조건을 추가하여 정의한 자료구조

 - 정의

    ㄴ 모든 원소는 서로 다른 유일한 키를 가짐

    ㄴ 왼쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 작음

    ㄴ 오른쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 큼

    ㄴ 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리

 - 연산

    ㄴ 루트에서 시작

    ㄴ 탐색할 키 값을 루트 노드의 키값과 비교한다

        ▶ 키 값 = 루트 노드의 키 값 : 원하는 원소를 찾았으므로 탐색 연산 성공

        ▶ 키 값 < 루트 노드의 키 값 : 루트 노드의 왼쪽 서브 트리에 대해 탐색 연산 수행

        ▶ 키 값 > 루트 노드의 키 값 : 루트 노드의 오른쪽 서브 트리에 대해 탐색 연산 수행

    ㄴ 서브 트리에 대해 순환적 탐색 연산 반복

---

이진 탐색 트리의 삽입 연산

① 탐색 연산 수행 : 삽입할 원소와 같은 원소가 트리에 있으면 삽입할 수 없으므로, 같은 원소가 트리에 있는지 탐색
② 탐색 실패한 위치에 원소를 삽입

---

이진 탐색 트리의 삭제 연산

① 탐색 연산 수행 : 삭제할 노드의 위치를 알아야 하기 때문
② 탐색하여 찾은 노드 삭제
    ㄴ 노드의 삭제 후에도 이진 탐색 트리를 유지해야 하므로 삭제 노드의 경우 후속처리*가 필요
* 후속처리 : 이진 탐색 트리의 재구성 작업
 - 자식 노드가 하나인 노드 (차수 1) : 삭제한 부모 노드의 자리를 자식 노드에게 물려준다.
 - 자식 노드가 둘인 노드 (차수 2) : 삭제한 노드의 자리를 자손 노드 중 하나에게 물려준다.
    ㄴ 방법 1) 왼쪽 서브 트리에 가장 큰 자손 노드에게 물려준다(가장 오른쪽에 있는 노드)
    ㄴ 방법 2) 오른쪽 서브 트리에 가장 작은 자손 노드에게 물려준다(가장 왼쪽에 있는 노드)

삭제한 노드의 자리를 물려받을 수 있는 후계자 노드