이진 정렬 트리

균형 이진 트리

B-트리(B-트리)

B-트리

기본 속성: 주어진 키워드를 기반으로 테이블 내 키워드의 주소를 계산합니다.

공법

갈등 처리 방법

버블 정렬: ① 인접한 요소를 비교합니다. 첫 번째 요소가 두 번째 요소보다 크면 두 요소를 모두 교체합니다. ② 첫 번째 쌍에서 시작하여 마지막 쌍으로 끝나는 인접한 요소의 각 쌍에 대해 동일한 작업을 수행합니다. 이때 마지막 요소는 가장 큰 숫자가 되어야 합니다. ③ 마지막 요소를 제외한 모든 요소에 대해 위 단계를 반복합니다. ④ 비교할 숫자 쌍이 없을 때까지 점점 더 적은 요소에 대해 위 단계를 계속 반복합니다.

단순 선택 정렬: 정렬된 순서의 레코드 수가 n개라고 가정합니다. i는 1, 2,...,n-1을 취하고, 모든 n-i개의 1개 레코드(Ri, Ri 1,..., Rn) 중에서 정렬 코드가 가장 작은 레코드를 찾아 i번째 레코드와 교환합니다. n-1번 실행하면 레코드 순서 정렬이 완료됩니다.

직접 삽입 정렬: 먼저 첫 번째 데이터의 순위가 매겨진 다음 각 패스에서 정렬할 데이터 조각이 키 크기에 따라 정렬된 레코드 그룹의 적절한 위치에 삽입됩니다. 정렬할 모든 데이터가 삽입되었습니다.

Hill 정렬: 먼저 n보다 작은 정수 d1을 첫 번째 증분으로 취하고 파일의 모든 레코드를 그룹화합니다. 거리가 d1의 배수인 모든 레코드는 동일한 그룹에 배치됩니다. 먼저 각 그룹 내에서 직접 삽입 정렬을 수행한 다음 두 번째 증분 d2<d1을 취하고 dt=1 증분(dt<...<d2<d1)이 될 때까지 위의 그룹화 및 정렬을 반복합니다.

힙 정렬: 이진 트리로 정렬할 시퀀스를 구성한 후 모든 하위 노드가 상위 노드보다 작도록 전치 조정을 수행합니다. 이때 루트 노드 값은 최대값이 되어야 합니다. 다시 이진 트리를 구축하고 위의 작업을 반복하세요.

양방향 병합 정렬: ① 여러 개의 바이너리 그룹을 형성하고 그룹 내에서 순서대로 조정합니다. ② 정렬된 바이너리 그룹을 하나의 그룹으로 병합하고 그룹 내에서 순서대로 조정합니다. ③ 모든 데이터를 하나의 그룹으로 병합하여 정렬을 완료합니다.

기수 정렬: 0 공백, 1 공백,..., 9 공백이라는 이름의 공백을 10개 설정합니다. 먼저 순서의 레코드를 각 주요 공백에 한 자리 값에 따라 하나씩 대응시켜 각 공백에 배치합니다. 각 공간에서 정렬을 완료한 후 0번 공간에서 각 레코드를 꺼내어 새로운 시퀀스를 형성한 다음 가장 높은 비트 정렬이 완료될 때까지 상위 비트에서 작업을 반복합니다.

병합 정렬: 초기 시퀀스를 m개의 더 작은 레코드 세그먼트로 나누고, 이러한 레코드 세그먼트를 정렬하고, 정렬이 완료될 때까지 각 레코드 세그먼트의 가장 작은 끝부터 최소값을 지속적으로 비교합니다.

패자 트리(Loser tree): 병합 정렬이 최소값을 감지할 때 패자 트리를 사용하지 않는 경우 k-1번 읽은 k 값을 비교하면 되며, 이를 사용한 후에는 시간 복잡도만 수행하면 됩니다. 최적의 값을 선택하는 방법은 O(log2k)이고, 트리 구축 시간 복잡도는 O(klog2k)이며, 패자 트리 높이는 [log2k] 1입니다.

교체 선택 정렬: 버퍼 크기에 따라 외부 메모리에서 레코드를 읽어 버퍼가 가득 차면 가장 작은 레코드를 선택하여 외부 메모리에 다시 씁니다. 레코드를 읽고 출력 레코드는 병합된 세그먼트의 일부가 됩니다. 새로 입력된 레코드가 병합 세그먼트로 꺼낸 레코드보다 작은 경우 다른 초기 병합 세그먼트를 대체하여 생성됩니다. 위의 작업을 반복하세요.

최적의 병합 트리: 교체 선택 정렬을 통해 서로 다른 길이의 병합 세그먼트를 얻습니다. 각 세그먼트는 길이에 따라 허프만 트리에 배치됩니다(방법은 트리 장 참조). 노드가 통과한 Edge 수의 합의 2배가 최적 병합 트리에 해당하는 I/O 수(최소 I/O 수)입니다.