이진 검색 트리
이진 검색 트리
검색 트리는 연결 리스트나 큐처럼 자료들을 담는 컨테이너이지만 자료들을 일정한 순서에 따라 정렬한 상태로 저장해 둡니다. 검색 트리는 이 점을 이용해 원소의 추가와 삭제만이 아니라 특정 원소의 존재 여부 확인등의 다양한 연산을 빠르게 수행합니다. 검색 트리중 가장 흔하게 사용되는 것이 바로
이진 검색 트리와 그 변종들 입니다. 이진 검색 트리는 아주 널리 사용되기 때문에, 이들의 동작 원리를 꼭 이해할 필요가 있습니다.
이진 검색 트리의 정의와 조작
정의
- 이진 트리란 각 노드가 왼쪽 오른쪽 , 최대 두개의 자식 노드만을 가질 수 있는 트리를 의미한다.
- 각 노드의 왼쪽 서브트리에는 해당 노드의 원소보다 작은 원소를 가진 노드들이 들어간다.
- 각 노드의 오른쪽 서브트리에는 해당 노드의 원소보다 큰 원소를 가진 노드들이 들어간다.
순회
- 중위 순회하면 크기 순서로 정렬된 원소의 목록을 얻을 수 있다.
자료의 검색
- 한 번 원소를 비교하는 것 만으로도 찾아야할 전체 대상의 절반을 줄일 수 있다.
- 실질적으로 이진 탐색과 비슷한 속도로 자료를 찾을 수 있다.
조작
앞서 언급한 특성은 정렬된 배열에 비해 나을 것이 없다. 이진 검색 트리가 진가를 드러내는 곳은 집합에 원소를 추가하거나 삭제하는 조작을 해야 할 때 이다.
시간 복잡도 분석과 균형 잡힌 이전 검색 트리
이진 검색 트리에 대한 모든 연산은 모두 루트에서부터 한 단계씩 트리를 내려가며 재귀 호출을 통해 수행되므로, 최대 재귀 호출의 횟수는 트리의 높이 h와 같습니다.따라서 모든 연산의 복잡도는 O(h)라고 할 수 있습니다. 이진 검색 트리의 높이는 자료들이 어떤 순서로 추가되고 삭제되는지에 따라 크게 달라집니다. 1부터 N까지 숫자를 순서대로 추가하면 결과적으로 높이는 N-1이 되며 이런 트리를 한쪽으로 기울어졌다라고 합니다. 이런 형태의 이진 검색 트리는 사실상 연결 리스트를 쓰는것과 마찬가지 입니다. 우리가 원하는 이상적인 케이스는 평평한 트리입니다. 트리의 최소 높이는 O(logN)이 됩니다.
문제: 너드인가, 너드가 아닌가? 2(NERD2, 중)
- 읽기
균형 잡힌 이진 트리 직접 구현하기
트립은 입력이 특정 순서로 주어질 때 그 성능이 떨어진다는 이진 검색 트리의 단점을 해결하기 위해 고안된 일종의 랜덤화된 이진 검색 트리입니다. 트립은 이진 검색 트리와 같은 성질을 가지고 있지만 트리의 형태가 원소들의 추가 순서에 따라 결정되지않고 난수에 의해 임의대로 결정됩니다.
- 이진 검색 트리의 조건: 모든 노드에 대해 왼쪽 서브트리에 있는 서브트리에 있는 노드들의 원소는 새당 노드의 원소보다 작고, 오른쪽 서브 트리는에 있는 노드들은 해당 노드의 원소보다 크다.
- 모든 노드의 우선 순위는 각자의 자식 노드보다 크거나 같습니다.
문제 : 삽입 정렬 뒤집기
- 읽기
