이진 검색 트리
검색트리
자료들을 일정한 순서에 따라 정렬한 상태로 저장해둠
원소의 추가와 삭제 + 특정 원소의 존재 여부 확인 등 다양한 연산을 빠르게 수행할 수 있음
검색트리가 사용될 수 있는 곳 예시
- 이미 가입한 사용자들의 주민등록번호를 저장해두고, 특정 사용자가 이미 가입되었나 찾기
- 사용자의 ID를 사용자 정보로 대응시키는 사전 객체 만들기
- 모든 학생들의 시험 점수를 저장해놓고, 나보다 1등 위인 사람과 1등 아래인 사람 찾기
검색트리 중 가장 흔하게 사용되는 것이 바로 이진 검색 트리이다.
이진 검색 트리
각 노드가 왼쪽과 오른쪽, 최대 두 개의 자식 노드만을 가질 수 있는 트리
왼쪽에는 root보다 작은 값, 오른쪽에는 root보다 큰 값이 들어감
원하는 값을 찾아가는 과정은 배열에서의 이진 탐색과 비슷함. 시간복잡도는 O(lgN)
순회
중위 순회하면 오름차순 정렬을 얻을 수 있음
즉, 첫번쨰 원소는 최소값이고 마지막 원소는 최대값인 것임
자료의 검색
root가 16인 트리에서 15를 찾는다면 왼쪽으로 내려가면 됨
이렇게 한 번 비교하는 것으로 절반을 줄일 수 있다.
=> 이진탐색과 비슷한 속도
조작 ★
이진 검색 트리는 원소를 추가하거나 삭제하는 조작 연산을 할 때 진가를 발휘함
- 추가 : 새 잎 노드 생길 뿐 트리에 영향 X
- 삭제 : 트리의 어디에서도 일어날 수 있음. 합치기를 구현해야함 (책 700p)
이진 검색 트리는 표준 라이브러리에서 지원하지만, 다음 경우에 지원하는 언어는 거의 없음
1) X보다 작은 원소의 수 찾기
2) k번째 원소 찾기
즉, 직접 이진트리를 구현해야함
시간복잡도
최대 호출의 횟수는 트리의 높이 h임
즉, 모든 연산의 시간복잡도는 O(h)임
그러나 이 경우는 기울어진 트리이고, 이런 형태론 이진 검색 트리를 사용한 의미가 사라짐. 사실상 연결리스트와 같아짐.
이상적인 트리는 노드가 들어갈 수 있는 자리가 꽉 차 있는 '평평한' 트리임.
트리의 높이가 1 높아질 때마다 원소의 개수가 대략 두 배 늘어남
=> 트리의 시간복잡도는 O(lgN)이 됨
균형 잡힌 이진 검색 트리 (balanced binary search tree)
항상 트리의 높이가 O(lgN)이 되도록 유지함
ex) 레드-블랙 트리
'IT > Algorithm' 카테고리의 다른 글
그래프 (DFS, BFS) (0) | 2020.08.28 |
---|---|
우선순위 큐와 힙 - 변화하는 중간 값 (0) | 2020.08.24 |
트리 - 트리 순회 순서 변경 (0) | 2020.08.22 |
스택 - 짝이 맞지 않는 괄호 (0) | 2020.08.20 |
선형 자료구조 - 조세푸스 문제 (0) | 2020.08.18 |
댓글