정적 조회 테이블

동적 조회 테이블

n: 조회 테이블의 길이

Pi: i번째 요소를 찾을 확률(보통 1/n)

Ci : i번째 요소를 찾는 데 필요한 비교 횟수

평균 성공 길이 찾기: (n 1)/2

평균 검색 실패 기간: n 1

평균 성공 길이 찾기: (n 1)/2

실패한 검색의 평균 길이: n/2 n/(n 1)

정렬된 시퀀스 목록에만 적용 가능하며, 키를 중간 위치 요소와 비교한 다음 검색이 성공하거나 실패할 때까지 크기에 따라 중간 위치 요소의 전반부 또는 후반부를 재귀적으로 비교합니다.

반탐색 과정을 설명하는 데 사용됩니다.

인덱스 시퀀스 검색이라고도 합니다. 조회 테이블을 여러 블록으로 나눕니다. 이전 블록의 키워드는 다음 블록의 키워드보다 작지만 블록의 요소는 무질서할 수 있습니다. 각 항목은 각 블록의 최대 키워드와 주소를 나타냅니다. 첫 번째 요소의 인덱스 테이블은 순서대로 키워드로 구성됩니다.

검색 시 인덱스 테이블에서 검색할 레코드가 위치한 블록을 먼저 확인한 후(순차 또는 반검색 인덱스 테이블 사용) 블록 내에서 순차적으로 검색합니다.

순서대로 모두 검색

인덱스 테이블은 블록 내에서 절반 검색과 순차 검색을 사용합니다.

이진 정렬 트리(이진 검색 트리라고도 함)는 빈 트리이거나 다음 속성을 갖는 이진 트리입니다.

1) 왼쪽 하위 트리가 비어 있지 않으면 왼쪽 하위 트리에 있는 모든 노드의 값이 루트 노드의 값보다 작습니다.

2) 오른쪽 하위 트리가 비어 있지 않으면 오른쪽 하위 트리에 있는 모든 노드의 값이 루트 노드의 값보다 큽니다.

3) 왼쪽과 오른쪽 하위 트리도 각각 이진 정렬 트리입니다.

이진 정렬 트리에서 순차 순회를 수행하여 증가하는 순서의 시퀀스를 얻습니다.

1) 키워드 k가 루트 노드 값보다 작으면 왼쪽 하위 트리에 삽입하고, 그렇지 않으면 오른쪽 하위 트리에 삽입합니다.

2) 삽입된 노드는 새로 추가된 리프 노드여야 하며 검색 실패 시 검색 경로에서 방문한 마지막 노드의 왼쪽 또는 오른쪽 자식이어야 합니다.

3) 이진 정렬에서 동일한 노드를 삭제하고 삽입합니다. 노드가 원래 리프 노드인 경우 이전 및 후속 이진 트리는 변경되지 않고, 균형 잡힌 이진 트리의 경우 삭제된 원래 노드가 리프 노드인지 여부에 관계없이 유지됩니다. 리프 노드 여부, 노드, AVL 전후가 변경될 수 있습니다(또는 변경되지 않을 수 있음)

건설 과정

연산

①삭제된 노드가 리프 노드인 경우에는 직접 삭제하면 됩니다.

②삭제된 노드 z에 왼쪽 하위 트리 또는 오른쪽 하위 트리가 하나만 있는 경우 해당 하위 트리를 z의 상위 노드의 하위 트리로 만듭니다.

③z가 왼쪽과 오른쪽 두 개의 하위 트리를 가지고 있는 경우, z의 직접 후속 노드(순서대로 계산) 또는 직접 선행 노드를 z로 대체한 후 후속 노드를 삭제하여 이전 상황으로 전환합니다.

1) 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1을 초과하지 않는 것, 즉 균형 이진 트리

2) 오른쪽(왼쪽) 자식만 있는 단일 트리

1) 이진 정렬 트리의 검색 성능은 데이터의 입력 순서와 관련이 있으며 최상의 경우에만 검색 성능이 이진 검색과 동일합니다.

2) 테이블의 질서를 유지하는 측면에서 이진 트리는 노드를 이동할 필요가 없으며 삽입 및 삭제 작업을 완료하기 위해 포인터만 수정하면 되며 시간 복잡도는 O(log2n)입니다. O(n)이 있는 경우 시퀀스 테이블이 정적 조회 테이블인 경우 시퀀스 테이블과 이진 검색을 사용하는 것이 적합합니다. 동적인 경우 논리적 구조로 이진 정렬 트리를 사용하는 것이 적합합니다.

노드의 왼쪽과 오른쪽 하위 트리 사이의 높이 차이를 균형 인자(왼쪽 높음 - 오른쪽 높음)로 정의하면 균형 이진 트리 노드의 균형 인자는 0, 1, -1, 즉 높이만 될 수 있습니다. 모든 노드의 왼쪽 하위 트리와 오른쪽 하위 트리 간의 차이는 1 이하입니다.

1) 이진 정렬 트리와 유사한 노드 삽입

2) 삽입된 노드가 균형을 파괴하면 가장 작은 불균형 하위 트리를 찾아서 회전시킵니다.

1) 이진 정렬 트리 방법을 사용하여 노드 w에 대한 삭제 작업을 수행합니다.

2) 노드 w에서 시작하여 위쪽으로 추적하여 첫 번째 불균형 노드 z(즉, ​​가장 작은 불균형 하위 트리)를 찾습니다. y는 노드 z의 높이가 가장 높은 하위 노드입니다. x는 노드 y의 높이입니다.

3) 그런 다음 x, y 및 z의 가능한 4개 위치가 있는 루트로 z를 사용하여 하위 트리의 균형을 맞춥니다.

검색 과정은 이진 정렬 트리와 동일하며 평균 검색 길이는 O(log2n)입니다.

레드-블랙 트리는 다음 레드-블랙 속성을 만족하는 이진 정렬 트리입니다.

①각 노드는 빨간색이거나 검은색입니다.

②루트 노드는 검은색이다.

③리프 노드(가상의 외부 노드, NULL 노드)는 모두 검은색입니다.

④ 인접한 두 개의 레드 노드가 없습니다(즉, 레드 노드의 부모 노드와 자식 노드가 모두 블랙입니다).

⑤ 각 노드에 대해 해당 노드에서 리프 노드까지의 단순 경로에는 동일한 수의 검정색 노드가 포함됩니다.

1. 루트 노드에서 리프 노드까지의 가장 긴 경로는 최단 경로의 두 배를 넘지 않습니다.

2. n개의 내부 노드가 있는 레드-블랙 트리의 높이

이진 검색 트리 삽입 방법을 사용하여 삽입하고 새 노드 z를 빨간색으로 색칠합니다.

1) 삭제 과정은 먼저 이진 탐색 트리의 삭제 방법을 실행하며, 삭제하려는 노드에 자식이 2개 있으면 순서대로(즉, 오른쪽 하위 트리에서 가장 작은 노드) 후속 노드와 교환한다. 그런 다음 삭제로 변환됩니다. 이 후속 노드에는 최대 하나의 자식이 있으므로 삭제되는 노드에는 자식이 없거나 하나만 있는 상황으로 변환됩니다.

2) 삭제할 노드가 오른쪽 자식 또는 왼쪽 자식만 있는 경우 해당 노드는 블랙 노드이고 자식은 레드 노드여야 함을 속성에서 알 수 있습니다.

3) 삭제하려는 노드에 자식이 없는 경우

해시 함수는 두 개 이상의 서로 다른 키워드를 동일한 주소에 매핑할 수 있으며, 이를 충돌이라고 합니다. 이러한 서로 다른 키워드를 동의어라고 합니다. 한편으로, 잘 설계된 해시 함수는 그러한 충돌을 최소화해야 하는 반면, 그러한 충돌은 항상 불가피하므로 이를 처리하는 방법을 설계해야 합니다.

1) 해시 함수의 도메인에는 저장해야 하는 키워드가 모두 포함되어야 하며, 값 도메인의 범위는 해시 테이블의 크기나 주소 범위에 따라 달라집니다.

2) 해시 함수로 계산된 주소는 전체 주소 공간에 동일한 확률로 고르게 분포되어 충돌 발생을 줄여야 합니다.

3) 해시 함수는 최대한 단순해야 하며, 어떤 키워드에 해당하는 해시 주소를 짧은 시간 내에 계산할 수 있어야 합니다.

직접 주소 지정 방법

나누기 남기기법

디지털 분석

정사각형-중간 방법

정의

증분 순서

삽입과 삭제가 빈번한 상황에 적합한 해시 주소로 고유하게 식별되는 선형 연결 목록에 모든 동의어를 저장합니다.

① 조회 테이블의 Addr 주소에 레코드가 있는지 확인하고 레코드가 있으면 검색 실패를 반환하고, 키 값과 비교하여 반환합니다. 성공 플래그를 검색하고, 그렇지 않으면 ②단계로 진행합니다.

② 주어진 충돌 처리 방법을 사용하여 "다음 해시 주소"를 계산하고 이 주소에 Addr을 설정한 후 ①단계로 이동합니다.

검색 성공

검색 실패

해시 함수

갈등을 처리하는 방법

채우기 요소 α = 테이블의 레코드 수 n/해시 테이블 길이 m

다중 방향 균형 검색 트리라고도 알려진 B-트리는 모든 노드의 최대 자식 수를 B-트리의 차수라고 하며 m으로 표시됩니다. 다음 속성을 만족하는 트리 m-ary 트리:

1) 트리의 각 노드에는 최대 m개의 하위 트리가 있습니다. 즉, 최대 m-1개의 키워드를 포함합니다.

2) 루트 노드가 터미널 노드가 아닌 경우 하위 트리가 2개 이상 존재

3) 루트 노드를 제외한 모든 비리프 노드에는 최소한 "m/2]개의 하위 트리가 있습니다. 즉, 최소한 "m/2]-1개의 키워드를 포함합니다.

4) 모든 리프가 아닌 노드의 구조는 다음과 같습니다.

5) 모든 리프 노드는 동일한 수준에 나타나며 정보를 전달하지 않습니다(즉, 외부 노드, 이러한 노드에 대한 포인터는 비어 있음).

1) 노드의 자식 수는 노드의 키워드 수에 1을 더한 것과 같습니다.

2) 루트 노드에 키워드가 없으면 하위 트리가 없으며 이때 B-트리는 비어 있습니다. 루트 노드에 키워드가 있으면 해당 하위 트리는 하위 트리의 수가 2보다 크거나 같아야 합니다. 는 키워드 수에 1을 더한 것과 같습니다.

3) 루트 노드를 제외한 모든 비종단 노드는 최소 "m/2]-1=3개의 하위 트리와 최대 5개의 하위 트리(즉, 최대 4개의 키워드)를 갖습니다.

4) 노드의 키워드는 왼쪽에서 오른쪽으로 증가하는 순서로 되어 있습니다. 키워드 양쪽에 하위 트리에 대한 포인터가 있습니다. 왼쪽 포인터가 가리키는 하위 트리의 키워드는 모두 키워드보다 작습니다. 오른쪽 포인터 기준은 키워드보다 작습니다. 모든 키워드는 이 키워드보다 큽니다.

5) 모든 리프 노드는 4번째 수준에 있으며 검색이 실패한 위치를 나타냅니다.

1) B-트리의 각 노드는 최대 m개의 하위 트리와 m-1개의 키워드를 갖습니다. 따라서 높이가 h인 m-차 B-트리의 키워드 수는 n≤(m-1)(1)을 만족해야 합니다. m m^2 … m^(h-1))=m^h-1

2) 루트 노드에는 최소한 2개의 하위 트리가 있고, 루트가 아닌 노드에는 최소한 "m/2]-1 키워드가 있으며, h 1단계에는 최소한 2("m/2])^(h-1) 노드는 포인트이고 리프 노드의 수는 n 1입니다.

①B-트리에서 노드 찾기

②노드에서 키워드 찾기

1) 삽입 후 노드 키워드 개수가 m개 미만인 경우 직접 삽입 가능

2) 그렇지 않은 경우에는 중간 위치("m/2])에 있는 노드를 가져와 원래 노드의 상위 노드에 삽입하면 원래 노드가 두 조각으로 분할됩니다. 상위 노드가 오버플로되면 루트 노드에 도달할 때까지 계속 분할하여 B-트리의 높이를 1만큼 증가시킵니다.

1) 삭제된 키워드 k가 단말 노드(최하위 비리프 노드)에 없으면 k를 k의 선행자(또는 후임자) k'로 대체한 후, 해당 노드에서 k'를 삭제한다(k'는 반드시 떨어져야 한다). 터미널 노드에서)

2) 삭제된 키워드 k가 터미널 노드에 있는 경우

1) 각 분기 노드에는 최대 m개의 하위 트리(자식 노드)가 있습니다.

2) 리프가 아닌 루트 노드는 적어도 2개의 하위 트리를 갖고, 다른 가지 노드는 적어도 "m/2]개의 하위 트리를 갖는다.

3) 노드의 하위 트리 수는 키워드 수와 같습니다.

4) 모든 리프 노드에는 모든 키워드와 해당 레코드에 대한 포인터가 포함됩니다. 키워드는 리프 노드에 크기 순서로 정렬되고 인접한 리프 노드는 크기 순서로 서로 연결됩니다.

5) 모든 가지 노드(인덱스로 간주될 수 있는 인덱스)에는 각 하위 노드(즉, 다음 레벨의 인덱스 블록)에 있는 키워드의 최대값과 해당 하위 노드에 대한 포인터만 포함됩니다.

1) B-트리에서 n개의 키워드가 있는 노드는 n개의 하위 트리만 포함합니다. 즉, 각 키워드는 하나의 하위 트리에 해당하는 반면, B-트리에서 n개의 키워드가 있는 노드는 n 1개의 하위 트리를 포함합니다.

2) B 트리에서 각 노드(루트가 아닌 내부 노드)에 대한 키워드 개수 n의 범위는 "m/2]<n<m(루트 노드: 2<n<m)입니다. 트리에서 각 노드(루트가 아닌 내부 노드)에 대한 키워드 수 n의 범위는 "m/2]-1<n<m-1(루트 노드: 1≤n≤m-1)입니다.

3) B-트리에서 리프 노드는 정보를 포함하며, 리프가 아닌 모든 노드는 인덱스 역할만 합니다. 리프가 아닌 노드의 각 인덱스 항목에는 해당 하위 트리의 최대 키워드와 하위 트리에 대한 포인터만 포함됩니다. 이 키워드에 해당하는 레코드의 저장 주소는 포함되지 않습니다.

4) B-트리에서 리프 노드에는 모든 키워드가 포함됩니다. 즉, 리프가 아닌 노드에 나타나는 키워드는 B-트리의 리프 노드(가장 바깥쪽 내부 노드)와 리프 노드에 포함된 키워드에도 나타납니다. 다른 노드는 반복되지 않습니다.

① B 트리에는 두 개의 헤드 포인터가 있습니다. 하나는 루트 노드를 가리키고 다른 하나는 가장 작은 키워드가 있는 리프 노드를 가리킵니다. 따라서 B 트리에서는 두 가지 검색 작업을 수행할 수 있습니다. 하나는 순차적 검색 시작입니다. 가장 작은 키워드부터, 다른 하나는 첫 번째는 루트 노드부터 시작하는 다방향 검색입니다.

②B-트리에서 검색할 때 성공 여부에 관계없이 각 검색은 루트 노드에서 리프 노드까지의 경로입니다.