(191118) 자료구조 - 이진 탐색 트리

이진 탐색 트리 (Binary Search Tree)

이진 탐색 트리.jpg

특징

- 기본적으로 이진 트리이므로 각 노드는 최대 2개의 자식만을 갖는다 (0~2개)

- 모든 노드의 값은 유일하다 (중복된 값이 없다)

- 좌측 하위트리의 값은 상위 노드(부모노드)의 값보다 작은 값이어야 한다.

- 우측 하위트리의 값은 상위 노드(부모노드)의 값보다 큰 값이어야 한다.

- 그리고 하위 트리의 하위 트리들도 같은 특징을 갖는다.

 

이진 탐색 트리의 탐색 방법 

1. 찾고자하는 값을 루트 노드의 값과 비교 한다.

1-1. 비교해서 같으면 루트 노드를 리턴하고 탐색을 마친다.

 

2. 찾고자하는 값이 루트 노드의 값보다 크다면 루트노드 기준으로 오른쪽의 하위 노드를 기준으로 하여 다시 탐색한다.

(1번 과정에서 루트 노드 대신 루트노드의 오른쪽 하위노드를 기준으로 하여 반복)

 

3. 찾고자하는 값이 루트 노드의 값보다 작다면 루트노드 기준으로 왼쪽의 하위 노드를 기준으로 다시 탐색한다.

(위 과정과 동일하게 반복)

 

평균적으로 이진 탐색 트리의 시간복잡도는 O(logN)이 걸린다

-> 왜냐하면 기준 노드를 기준으로 크면 왼쪽 하위노드는 탐색할 필요가 없기 때문 (작으면 반대로)

 

하지만 이진 탐색 트리의 노드들이 한쪽으로 극단적으로 치우친 경우에는 O(N)이 걸릴수도 있다.

(마치 연결 리스트 처럼 되어버려서!!!! 하위 노드들 간에 밸런스가 안 좋은 경우)

-> 이 경우에는 트리에 하위 노드를 넣을 때 보정을 하여 logN이 나오도록 할 수 있다.

(이 부분은 나중에 또 알아볼 기회가 있을 듯!!!!!! 여러 기법이 존재)

 

이진 탐색 트리에서 삽입

1. 먼저 삽입할 값을 루트 노드의 값과 비교한다.

2. 루트 노드의 값보다 작으면 왼쪽 하위 트리로, 크면 오른쪽 하위트리로 이동한다.

3. 하위 트리에서도 마찬가지로 값을 비교하여 작으면 왼쪽 하위트리로, 오른쪽 하위트리로 이동한다. 이 과정을 반복해서

4. 하위 트리가 null이면 그때 기준 노드를 기준으로 작으면 왼쪽, 크면 오른쪽 하위 노드로 삽입한다.

 

이진 탐색 트리에서 삭제

- 삭제하려는 노드가 단말 노드(잎 노드, 자식노드가 없을 경우) - 즉, 자식(하위)노드가 null인 경우

1. 그 노드의 부모 노드를 찾아서 연결을 끊어주면 된다.

 

- 삭제하려는 노드가 하나의 자식노드(하위노드)만 가지는 경우

1. 삭제하려는 노드의 부모 노드를 찾아서 그 부모 노드가 삭제하려는 노드의 자식 노드를 가리키게 하면 된다.

 

- 삭제하려는 노드가 두개의 자식노드(하위노드)를 가지는 경우

이 경우에는 삭제하려는 노드의 왼쪽 하위 트리중 가장 큰 값, 또는 오른쪽 하위 트리중 가장 작은 값 중 하나를 선택하여 삭제하려는 노드를 대체시켜주면 된다.

(오른쪽 하위 트리중 가장 작은 값 기준)

1. 삭제하려는 노드의 오른쪽 하위트리로 이동

2. 그 하위트리에서 계속 왼쪽 하위 트리로 탐색하여 왼쪽 하위트리가 null이 나올 때 까지 탐색

3. null이 나오면 그때의 노드의 부모 노드와 연결을 끊어준다.

3-1. 만약 왼쪽으로 null이 나왔는데 오른쪽에 하위노드가 또 있다면, 그 오른쪽 하위노드는 그 노드의 부모 노드의 왼쪽 하위노드로

4. 삭제하려는 노드의 부모 노드에 그 노드를 왼쪽 하위트리로써 연결하여 준다.

5. 삭제하려는 노드의 왼쪽 하위트리를 그 노드의 왼쪽 하위트리로 연결 / 오른쪽도 마찬가지

 

삽입과 삭제도 평균적으로는 탐색과 같은 시간복잡도를 갖는다!! (탐색을 base로 하기 때문에??)