- 임의의 노드의 키 값은 자신의 왼쪽 자식 노드의 키 값보다 크고 오른쪽 자식의 키 값보다 작음
이진 검색 트리 검색 방법
1. 키 x를 가진 노드를 검색
2. 트리에 키 x를 가진 노드가 존재하면 해당 노드를 리턴함
3. 존재하지 않으면 NIL을 리턴
treeSearch(t, x) //t : 서브 트리의 루트 노드, x 검색하고자 하는 키
{
if (t = NIL or key[t]=x) then return t;
if (x < key[t])
then return treeSearch(left[t], x);
else return treeSearch(right[t], x);
}
- n개의 원소가 불규칙하게 저장된 배열에서 i번째 작은 원소(큰 원소)를 찾는 문제를 해결하기 위한 알고리즘
- 정렬과 비슷
- 두 가지 알고리즘
1. 평균적으로 선형 시간이 소요되는 알고리즘
2. 최악의 경우에 선형 시간이 소요되는 알고리즘
평균 선형시간 선택 알고리즘
- 퀵 정렬처럼 분할한 후 자기 호출 방법을 이용하여 평균적으로 선형시간 i번째 작은 원소를 찾는 것
배열 A에서 i번째 요소 찾기
- 경우 1. 워소가 하나뿐인 경우 하나 리턴
- 경우 2. 원소가 다수인 경우, 파티션을 통해 중간값이 몇번째인지 확인
- 경우 3. 중간값이 i와 같은 경우, A[파티션을 통해 얻은 중간] 값을 리턴
- 경우 4. 중간 값이 i보다 클 경우, 오른쪽 그룹으로 범위를 좁혀 재귀적으로 실행
- 경우 5. 중간 값이 i보다 작을 겨웅, 왼족 그룹으로 범위를 좁혀 재귀적으로 실행
평균 선형시간 선택 알고리즘 작동 예
- 2번째 작은 원소 찾기
- 기준 원소를 r이라 지정하고 분할 수행
- 15와 31을 비교, 15와 8을 비교 ... 15를 기준으로 큰 수는 15 뒤 작은 수는 15 앞
- r을 3으로 지정하여 다시 분할 수행
유사 코드
select(A, p, r, i) //배열 A[p ... r]에서 i번째 작은 워소를 찾는다
{
if (p = r) then return A[p]; //원소가 하나 뿐인 경우 i는 반드시 1
q <- partition(A, p, r);
k <- q - p + 1; //k : 기준 원소가 전체에서 k번째 작은 원소임을 의미
if (i < k) then return select(A, p, q-1, i); // 왼쪽 그룹으로 범위를 좁힘
else if (i = k) then return A[q]; // 기준 원소가 바로 찾는 원소임
else return select(A, q+1, r, i-k); // 오른쪽 그룹으로 범위를 좁힘
}
최악의 경우 선형시간 선택 알고리즘
- 평균 선형 시간 선택 알고리즘의 단점
-> 분할 균형이 맞지 않고, 찾고자 하는 원소가 운나쁘게 큰 그룹에 속하는 일이 반복하는 경우 성능이 보장되지 않음
- 분할 균형이 나빠보여도 일정한 상수비를 유지하면 점근적 복잡도는 항상 Theta(n)이 됨
- 균형을 맞추기 위한 오버헤드가 너무 커져버리면 최악의 경우 선형시간 선택 알고리즘이 될 수 없음.
linearSelect(A, p, r, i) //배열 A[p ... r]에서 i번째 작은 원소를 찾는다
{
1. 원소 총 수가 5개 이하면 원하는 원소를 찾고 알고리즘을 끝냄
2. 전체 원소들을 5개씩 원소를 가진 [n/5]개의 그룹으로 나눔
- 원소의 총 수가 5의 배수가 아니면 이 중 한 그룹은 5개 미만이 됨.
3. 각 그룹에서 중앙값(원소가 5개이면 3번째 원소)을 찾임
- 이렇게 찾은 중앙값들을 m1, m2, .., m_{n/5}라 함
4. m1, m2 ..., m_{n/5}들의 중앙값 M을 재귀적으로 구함
- 홀수면 중앙값이 하나이므로 문제없고, 원소의 총 수가 짝수인 경우 두 중앙값중 아무거나 임의로 선택
-> call linearSelect()
5. M을 기준 원소로 삼아 전체 원소를 분할함
- M보다 작거나 같은것은 M의 왼쪽에 M보다 큰 것은 M의 오른쪽에 오도록 함
6. 분할 된 두 그룹 중 적합한 쪽을 선택하여 단계 1 ~ 6을 재귀적으로 반복함 -> call linserSelect()
}
