동적 손가락 검색 데이터 구조는 손가락 검색 외에도 손가락이 제공하는 위치에서 요소의 삽입 및 삭제를 수행해야 합니다. 핑거 검색 트리는 O(1)개의 움직일 수 있는 손가락만 유지된다는 가정 하에 O(log d) 시간에 손가락 검색을 지원하고 O(1) 시간에 업데이트를 지원하는 B-트리의 변형으로 정의됩니다. 손가락 d개의 위치를 ​​이동하려면 O(log d) 시간이 필요합니다. 핑거 검색 트리(AVL-트리, 레드-블랙 트리를 의미함) 구성은 고정된 고정 수의 핑거를 고려하거나 상각된 일정 시간의 업데이트만 지원합니다. 임의의 손가

이 섹션에서는 (2,4)-트리가 레벨 링크를 도입하여 효율적인 손가락 검색을 지원할 수 있는 방법을 설명합니다. 이 섹션에서 설명하는 아이디어는 b ≥ 2a에 대해 (a, b)-트리로 표시되는 보다 일반적인 높이 균형 트리 클래스에도 구현됩니다. (2,4)-트리는 모든 잎의 깊이가 동일하고 모든 내부 노드의 차수가 2, 3 또는 4인 높이 균형 탐색 트리로 정의됩니다. 요소는 리프에 저장되고 내부 노드는 검색 안내를 위한 검색 키만 저장합니다. 각 내부 노드는 차수가 2 이상이므로 (2,4)-트리는 높이가 O(log n)이고 O(

결정적 탐색 트리에 대한 두 가지 무작위 대안은 무작위 이진 탐색 트리, 트레프 및 건너뛰기 목록입니다. treap과 skip 목록은 모두 우아한 데이터 구조로 정의되며, 여기서 무작위화는 간단하고 효율적인 업데이트 작업을 용이하게 합니다. 이 섹션에서는 트리프와 건너뛰기 목록이 데이터 구조를 변경하지 않고 효율적인 손가락 검색 트리로 구현될 수 있는 방법을 설명합니다. 두 데이터 구조 모두 예상 O(log d) 시간을 소비하여 손가락 검색을 지원합니다. 여기서 예상은 데이터 구조를 구성하는 동안 알고리즘에 의해 생성된 무작위 선

건너뛰기 목록에서는 이 지점 a에서 검색을 계속하기만 하면 요소 b를 포함하는 노드에서 요소를 손가락으로 검색할 수 있습니다. a b이면 정방향으로 검색이 진행된다는 점에 유의하십시오. 백워드 케이스는 스킵 리스트에서 일반 검색과 대칭이지만, 포워드 케이스는 실제로 더 복잡합니다. 일반적으로 스킵 리스트에서의 검색은 리스트의 시작에 있는 센티넬이 가장 높은 노드로 간주되기 때문에 빠를 것으로 예상됩니다. 그러나 우리의 손가락은 높이가 1인 노드와 연관될 수 있습니다. 이 때문에 검색을 시도하는 동안 거의 오르지 않을 수 있

적응형 병합 정렬 적응형 병합 정렬은 정렬된 하위 목록 병합 정렬이 수행하는 병합을 수행합니다. 그러나 초기 하위 목록의 크기는 크기가 1인 하위 목록을 가지지 않고 요소 목록 사이에 순서가 있는지 여부에 따라 다릅니다. 예를 들어 그림의 목록을 고려하십시오. 2개의 정렬된 하위 목록으로 구성됩니다. 요소가 16,15,14,13인 하위 목록 1. 9,10,11,12 요소가 있는 하위 목록 2. 하위 목록 1은 정렬되지만 역순입니다. 따라서 하위 목록 1은 그림과 같이 반전됩니다. 하위 목록이 발

플레이 트리는 최근에 액세스한 요소가 다시 빠르게 액세스할 수 있는 추가 속성이 있는 자체 균형 이진 검색 트리로 정의됩니다. 삽입, 조회 및 제거와 같은 기본 작업은 O(log n) 상각 시간에 splay tree에 의해 수행됩니다. 무작위가 아닌 작업의 많은 시퀀스의 경우 시퀀스의 특정 패턴을 알 수 없는 경우에도 스프레이 트리가 다른 검색 트리보다 더 잘 작동합니다. 이진 검색 트리의 모든 일반 작업은 스플레잉이라고 하는 하나의 기본 작업과 결합됩니다. 각 노드에 대해 실수 키(a)를 저장한다고 가정합니다. 모든 이진 검색

동적 최적성 추측 splay tree에 대한 입증된 성능 보장 외에도 많은 관심을 갖고 있는 입증되지 않은 추측이 있습니다. 동적 최적성 추측은 이 추측을 나타냅니다. B와 같은 이진 탐색 트리 알고리즘이 d(y)+1의 비용으로 루트에서 y까지의 경로를 순회하여 요소 y에 액세스하도록 하고 액세스 간에는 1/1의 비용으로 트리에서 회전을 만들 수 있습니다. 회전. B(s)를 B가 액세스 시퀀스 s를 수행하는 비용이라고 하자. 그러면 동일한 액세스를 수행하기 위한 스플레이 트리의 비용은 O[n+B(s)]입니다. 증명되지 않은 상태

정적 손가락 정리 − f를 finger라고 하는 특정 요소로 취급한다고 하자. 그런 다음 아래 표현식은 시퀀스 재생 비용에 대한 경계입니다. O(m + n log(n) + Σ Sum log (|f - i[j]| + 1))j 참고 − |f-i| 손가락과 항목 i 사이의 항목의 대칭 순서의 거리로 표시됩니다. 여기서 m은 최대 n개의 노드가 있는 트리에 대한 업데이트 또는 액세스 작업의 수로 표시됩니다. 적어도 상각된 의미에서 n 노드를 초과하지 않는 트리에서 처음 m 작업에 걸리는 시간은 AVL 트리, 2-3 트리 등

주어진 숲에 대해 우리는 주어진 가장자리 중 일부를 점선으로 만들고 나머지는 단색으로 유지합니다. 리프가 아닌 각 노드는 자식 중 하나에 대한 단 하나의 솔리드 에지와 연결됩니다. 다른 모든 어린이는 점선의 도움으로 연결됩니다. 더 구체적으로 말하면, 주어진 트리에서 가장 오른쪽에 있는 링크(자식에 대한)는 견고하게 유지되어야 하고, 다른 자식에 대한 다른 모든 링크는 점선으로 생성됩니다. 결과적으로 트리는 솔리드 경로 모음으로 나뉩니다. 솔리드 경로의 루트는 점선으로 다른 솔리드 경로에 연결됩니다. 가상 트리로 표시된 새로운

가상 트리에서 일부 모서리는 솔리드로 처리되고 일부는 대시로 처리됩니다. 일반적인 펼침은 단단한 나무에서만 수행됩니다. 가상 트리의 노드 y에서 재생하기 위해 다음과 같은 방법이 구현됩니다. 알고리즘은 각 패스에서 한 번씩 트리를 세 번 보고 변경합니다. 첫 번째 패스에서는 노드 y에서 시작하여 솔리드 트리에서만 확장되어 y에서 전체 트리의 루트까지의 경로가 점선이 됩니다. 이 경로는 접합에 의해 생성됩니다. 노드 y에서의 마지막 분할은 이제 y 트리의 루트를 생성합니다. 덜 비공식적으로 알고리즘은 다음과 같이 설명됩니다. Spl

허프만 코드 허프만 코드는 무손실 데이터 압축에 일반적으로 사용되는 특정 유형의 최적 접두사 코드로 정의됩니다. 이러한 코드를 찾거나 구현하는 프로세스는 David A. Huffman이 Sc.D.에 있을 때 개발한 알고리즘인 Huffman 코딩을 통해 진행됩니다. MIT 학생이며 1952년 논문 A Method for the Construction of Minimum Redundancy Codes에 게재되었습니다. Huffman 알고리즘의 출력은 소스 기호(예:파일의 문자)를 인코딩하기 위한 가변 길이 코드 테이블로 표시될 수

간단한 알고리즘 n개의 초기 허프만 트리 모음이 준비되며, 각 트리는 단일 리프 노드입니다. 가중치(빈도)별로 구성된 우선 순위 대기열에 n개의 트리를 유지합니다. 처음 두 트리(가중치가 가장 작은 트리)를 제거하거나 삭제합니다. 이 두 나무를 결합하여 루트가 두 나무와 자식으로 연결되고 가중치가 두 자식 나무의 가중치 합인 새 나무를 만듭니다. 이 새 나무를 우선 순위 대기열에 보관하십시오. 모든 부분적인 Huffman 트리가 하나로 결합되지 않을 때까지 2-3단계를 반복합니다. 욕심 많은 알고리즘입니다. 각 반복에서 알고리

높이 제한 또는 깊이 제한 허프만 트리의 다이어그램은 다음과 같습니다. 트리 깊이 제한은 대부분의 실제 Huffman 구현에서 처리해야 하는 사소한 문제입니다. Huffman 구조는 높이나 깊이를 제한하지 않습니다. 그렇다면 최적이 될 수 없습니다. 물론, 허프만 트리의 가장 큰 깊이는 피보나치 수열에 의해 제한되지만 원하는 것보다 더 큰 깊이를 위한 충분한 공간을 남깁니다. Huffman 트리 깊이를 제한하는 이유는 무엇입니까? Fast Huffman 디코더는 룩업 테이블을 구현합니다. 메모리 비용을 줄이기 위해 여러 테

동일하지 않은 문자 비용에 대한 최적의 프리픽스 없는 코드를 찾는 문제는 인코딩 알파벳이 길이가 α 및 β인 동일하지 않은 비용(길이) 문자로 구성된 최소 비용 프리픽스 없는 코드를 계산하는 것으로 구성되며, 여기서 α ≤ β입니다. 우리는 바이너리 트리로 제한됩니다. 코드는 허프만 트리가 허프만 코딩 문제의 솔루션을 나타내는 것과 유사한 방식으로 편향된 트리로 표시됩니다. 유사성에도 불구하고 편지 비용이 같지 않은 경우는 고전적인 허프만 문제보다 훨씬 어렵습니다. 문제에 대한 풍부한 문헌에도 불구하고 일반적인 편지 비용에 대해

버킷팅은 해시 테이블을 1차원 배열 대신 2D 배열로 빌드합니다. 배열의 모든 항목은 크기가 커서 M 항목을 담기에 충분합니다(M은 데이터 양이 아니라 상수임). 문제 많은 낭비되는 공간이 생성됩니다. M이 초과되면 다른 전략을 구현해야 합니다. 메모리 기반 구현에서는 그다지 좋은 성능을 발휘하지 못하지만 버킷이 디스크 기반이면 가능합니다. 1은 최소 1회의 충돌이 있음을 보장합니다(비둘기 구멍 원리). 그러면 실행 시간과 버킷 부족 가능성이 모두 향상됩니다. M개의 위치와 각 위치의 Y 버킷의 해시 테이블의 경우 성공적인

다변수 단면 데이터(예:시계열 또는 반복 측정이 아님)는 각 열이 변수(특성)이고 각 행이 케이스 또는 레코드인 직사각형 데이터로 표시됩니다. 직사각형 데이터를 표현하는 첫 번째 절차는 이를 고차원의 포인트 데이터에 매핑하고 그리드 파일, PR 쿼드트리, 포인트 쿼드트리, k-d-트리와 같은 포인트 기반 데이터 구조 절차를 사용하는 것입니다. 직사각형 데이터를 4차원 점으로 매핑하는 절차는 반대쪽 모서리의 x 및 y 좌표 또는 한 모서리의 x 및 y 좌표와 너비 및 높이 등과 같은 숫자 기법으로 수행할 수 있습니다. 직사각형 데이

계산 기하학의 경우 평면 직선 그래프, 줄여서 PSLG(또는 직선 평면 그래프 또는 평면 직선 그래프)는 다음과 같이 평면에 평면 그래프를 삽입하기 위해 구현된 용어로 정의됩니다. 가장자리는 직선 세그먼트로 매핑됩니다. Fáry의 정리(1948)에 대한 진술은 모든 평면 그래프에 이러한 종류의 포함이 있다는 것입니다. 계산 기하학의 경우, PSLG는 세분화가 다각형이라는 가정 또는 주장과 함께 평면 세분화라고 하는 경우가 많습니다. 1차 정점이 없으면 PSLG는 평면을 다각형 영역으로 세분화하거나 그 반대로 정의합니다. 1차 정

소개 템플릿 매개변수 또는 하프에지 데이터 구조에 대한 HDS(HalfedgeDS로 약칭)는 평면 맵, 다면체 또는 기타 방향성 있는 2차원과 같은 꼭짓점, 가장자리 및 면의 입사 정보를 유지할 수 있는 가장자리 중심 데이터 구조로 정의됩니다. 임의의 차원에 포함된 표면. 각 모서리는 방향이 반대인 두 개의 절반 모서리로 나뉩니다. 각 하프 에지는 하나의 입사면과 하나의 입사 정점을 저장합니다. 각 면과 각 정점에 대해 하나의 입사 하프 에지가 저장됩니다. 하프에지 데이터 구조의 변형을 줄이면 면의 하프에지 포인터나 면의 저장과

범위 트리는 포인트 목록을 보유하는 정렬된 트리 데이터 구조로 정의됩니다. 주어진 범위 내의 모든 포인트를 효율적으로 검색할 수 있도록 하며 일반적으로 2차원 이상으로 구현됩니다. O(logd의 쿼리 시간이 더 빠르다는 점을 제외하고는 kd-tree와 동일합니다. n + k) 그러나 O(n logd-1의 더 나쁜 저장) n), d는 공간의 차원을 나타내고, n은 트리의 포인트 수를 나타내고, k는 주어진 쿼리에 대해 검색된 포인트 수를 나타냅니다. 범위 트리는 간격 트리로 구분할 수 있습니다. 포인트를 저장하고 주어진 범위의 포인트

쿼드트리는 2차원 공간에서 포인트 데이터를 효율적으로 저장하기 위해 구현된 트리입니다. 이 트리에서 각 노드에는 최대 4개의 자식이 있습니다. 다음 단계를 구현하는 2차원 영역에서 쿼드트리를 구축할 수 있습니다. 현재 2차원 공간은 4개의 상자로 나뉩니다. 상자가 그 안에 하나 이상의 점으로 구성된 경우 자식 개체를 만들어 상자의 2차원 공간에 저장합니다. 상자에 포인트가 포함되어 있지 않은 경우 해당 상자에 대해 어린이를 만들지 마십시오. 각 자식에 대해 재귀를 수행합니다. 쿼드트리는 이미지 압축으로 구현되며 각 노드는 각