데이터구조 - (9) 색인과 이진 검색 트리

색인

레코드는 개체에 대한 모든 정보가 들어 있다.

예시로 사람 레코드에는 주민번호, 이름, 집주소 등의 정보가 포함되어 있다.

이들 각각의 정보를 나타내는 부분은 필드라고 한다.

​

색인의 결국 개체의 레코드를 검색하는 것을 의미한다.

레코드를 구분할 수 있는 필드를 색인으로 사용하는데 키라고 한다.

색인은 key+해당 레코드의 page 번호로 구성하곤 한다.

​

배열에 키를 정렬시켜 색인을 만들면 검색에선 빅세타 lonN,

삽입과 삭제에선 빅세타 N만큼 시간이 들어 색인의 크기가 크면 사용할 수 없다.

그래서 이를 구현할 때 검색 트리가 사용된다.

 

검색 트리

출처 : 쉽게 배우는 자료구조 with 파이썬

검색 트리는 이진 검색 트리와 다진 검색 트리, 균형 검색 트리로 나누어지는데

이번 포스팅에서는 이진 검색 트리를 다룰 것이다.

 

이진 검색 트리

이진 검색 트리는 한 노드에서 최대 2개까지만 분기할 수 있는 나무를 말한다.

다진 검색 트리는 3개 이상 분기할 수 있는 형태의 나무를 말한다.

또한 검색 트리가 저장되는 장소에 따라 내장, 외장 검색 트리로 나눈다.

​

검색 트리의 형태는 자신의 왼쪽 아래 노드는 작고, 오른쪽 아래는 큰 형태이다.

아래는 이진 검색 트리의 예시이다.

출처 : 쉽게 배우는 자료구조 with 파이썬

​

추가로 이진 트리를 사용하여 수식을 표현할 수도 있다.

 

출처 : 쉽게 배우는 자료구조 with 파이썬

​

이진 검색 트리의 객체 구조는 아래와 같다.

중요한 기능은 역시 검색, 삽입, 삭제이다.

출처 : 쉽게 배우는 자료구조 with 파이썬

​

- 검색

출처 : 쉽게 배우는 자료구조 with 파이썬

검색은 간단히 구현할 수 있다.

계속해서 검색하고자 하는 값을 item과 비교하며 왼쪽 혹은 오른쪽으로

내려가는 형태이다. 그렇기에 중간에 찾은 경우와 맨 아래까지 내려가 찾은 경우 등으로

수행 시간이 나뉜다.

​

​

​

- 삽입

출처 : 쉽게 배우는 자료구조 with 파이썬

출처 : 쉽게 배우는 자료구조 with 파이썬

 

삽입하는 것은 실패하는 검색을 하는 것과 같다.

이는 맨 아래까지 찾아가 값이 없는 곳의 아래에 값을 삽입하는 방식이다.

​

​

- 삭제

출처 : 쉽게 배우는 자료구조 with 파이썬

삭제는 3가지 경우로 나누어서 한다. 1,2번은 비교적 간단하지만 3번이 조건이 많이 필요한 편이다.

1번은 삭제할 값이 리프 노드인 경우이고, 2번은 r의 자식이 하나만 존재할 경우이다.

3번은 r의 자식이 2개 존재하여, r의 오른쪽 자식 중에 가장 최소의 값을 찾아가는 과정이다.

​

출처 : 쉽게 배우는 자료구조 with 파이썬

출처 : 쉽게 배우는 자료구조 with 파이썬

최종적으로 총 n개의 노드를 가진 이진 검색 트리는 검색 시간이 평균적으로 빅세타 log n이 걸린다.

 

 

이진 검색 트리 순회

1. 전위 순회 : 루트 -> 좌서브 트리 -> 우서브 트리
2. 중위 순회 : 좌서브 트리 -> 루트 -> 우서브 트리
3. 후위 순회 : 좌서브 트리 -> 우서브 트리 -> 루트

​

출처 : 쉽게 배우는 자료구조 with 파이썬

전위 순회는 위와 같이 구현된다. 중위와 후위도 각각의 순서에 맞게 위 코드에서 배치만 다시하면 된다.

참고로 중위 순회는 이진 검색 트리를 정렬 순서로 방문한다.

​

예시로 A-B-C-D-E-F-G 형태의 구조가 있으면

전위 순회를 진행하면 A-B-D-E-C-F-G,

중위 순회는 D-B-E-A-F-C-G,

후위 순회는 D-E-B-F-G-C-A이다.

​

출처 : 쉽게 배우는 자료구조 with 파이썬

이진 검색 트리 작업의 효율은 위와 같다.