05-4 이진 탐색 트리

※ 이진 탐색 트리(Binary Search Tree) 란?

 - 이진 트리는 트리를 효율적으로 사용하기 위해 일정한 형태로 정의한 것. 탐색을 위한 자료구조로 이진 트리를 사용할 때

   저장할 데이터의 크기에 따라 노드의 위치를 정의한 것이 이진 탐색 트리

 

※ 이진 탐색 트리의 정의

1. 모든 원소는 서로 다른 유일한 키를 갖는다.
2. 왼쪽 서브 트리에 있는 원소의 키는 그 루트의 키보다 작다.(즉 작은건 왼쪽에 붙인다.)
3. 오른쪽 서브 트리에 있는 원소의 키는 그 루트의 키보다 크다.(즉 큰건 오른쪽에 붙인다.)
4. 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리이다.

※ 이진 탐색 트리의 탐색 연산

 - 이진 탐색 트리 탐색은 3가지 경우로 나눌 수 있다.

1. 키값 = 루트노드의 키값 : 탐색 성공
2. 키값 < 루트노드의 키값 : 왼쪽노드로 이동
3. 키값 > 루트노드의 키값 : 오른쪽노드로 이동

※ 이진 탐색 트리의 삽입 연산

1. 이진 탐색 트리에 같은 값이 있나 탐색해 본다. (있다면 종료, 없다면 삽입)
2. 만약 같은 값이 없다면 루트노드부터 크기를 비교해 삽입하려는 값이 작다면 왼쪽 합입하려던 값이 크다면 오른쪽으로 이동
3. 2번작업을 통해 단말노드까지 내려오면 단말노드의값과 비교해서 삽입값이 작다면 왼쪽, 크다면 오른쪽에 연결

※ 이진 탐색 트리의 삭제 연산

 - 노드를 삭제한 후에도 여전히 이진 탐색 트리를 유지해야 하기 때문에 각각의 경우에 대해 트리를 유지하기 위한 후속처리가 필요하다.

1. 삭제할 노드가 단말 노드인 경우(차수가 0인 경우)

          - 노드를 삭제하고, 부모 노드의 링크 필드를 null로 설정

            

2. 삭제할 노드가 한 개의 자식노드를 가진 경우(차수가 1인 경우)

          - 남겨진 자식노드가 부모노드의 자리를 물려받는다.

            

3. 삭제할 노드가 두 개의 자식노드를 가진 경우(차수가 2인 경우)

          - 자식노드가 두개인 부모노드를 삭제할 경우 부모노드의 자리를 두 자식중 하나에게 물려 주어야 한다.

            노드가 삭제되고 자손에게 물려조도 이진 탐색 트리가 유지가 되려면 선택된 자손 노드의 키값은 이진 탐색

트리의 특성에 따라 왼쪽 서브 트리에 있는 노드들 보다 커야 하고, 오른쪽 서브 트리에 있는 노드들 보다는 작아야 된다. 그렇기 때문에 왼쪽 자식에게 물려주려면 왼쪽에서 가장 큰 수, 오른쪽 자식에게 물려줄 거라면 오른쪽 자식중 가장 작은 수를 가진 노드에게 물려주어야 된다.

            이진 탐색 트리의 특성상 오른쪽에 큰값, 왼쪽에 작은값을 붙이므로 왼쪽 서브트리의 가장 오른쪽에 있는 노드나,

            오른쪽 서브트리의 가장 왼쪽에 있는 노드를 선택해서 물려주어야 된다.