여기에서 높이 균형 좌파 나무(HBLT)가 무엇인지 살펴보겠습니다. 외부 노드라고 하는 특수 노드가 있는 바이너리 트리를 생각해 보세요. 각 빈 하위 트리를 대체합니다. 다른 모든 노드를 내부 노드라고 합니다. . 일부 외부 노드가 일부 이진 트리와 함께 추가되면 이를 확장된 이진 트리라고 합니다. . 이 트리의 잎 가장자리를 고려하지 않으면 그것이 실제 이진 트리입니다. 확장된 바이너리 트리입니다. 이제 s(x) 노드 x에서 하위 트리의 외부 노드까지의 최단 경로 길이입니다. x가 외부 노드인 경우 s(x) 값은 0입니다.

Max HBLT에 삽입은 Max Meld 작업을 사용하여 수행할 수 있습니다. 이 연산은 두 개의 Max HBLT를 하나의 Max HBLT로 병합하는 데 사용됩니다. H라고 하는 하나의 최대 HBLT에 x를 삽입하고 싶다고 가정해 보겠습니다. x를 사용하여 작은 HBLT를 만든 다음 이를 H와 혼합한 다음, 혼합 후 H는 x를 포함한 모든 요소를 ​​보유합니다. 따라서 HBLT에 대한 삽입 작업을 수행하려면 멜딩 작업이 필요합니다.

Max HBLT에서 루트는 루트에 위치합니다. 루트가 삭제되면 최대 2개의 HBLT, 즉 왼쪽과 오른쪽이 분리됩니다. 이 두 개의 Max HBLT를 다시 합쳐서 하나로 병합할 수 있습니다. 따라서 병합 후 삭제된 요소를 제외한 모든 요소가 거기에 있습니다.

혼합 전략은 재귀를 사용하여 쉽게 수행됩니다. A와 B가 융합될 두 개의 HBLT라고 가정합니다. 그 중 하나가 비어 있으면 최종 결과로 다른 하나를 만드십시오. 빈 HBLT가 없으면 두 루트의 요소를 비교해야 합니다. 요소가 더 큰 루트가 혼합된 HBLT의 루트가 됩니다. A에 더 큰 근이 있다고 가정합니다. 그리고 그것은 왼쪽 서브트리가 L입니다. C가 A와 HBLT B의 오른쪽 서브트리를 결합한 결과인 최대 HBLT라고 가정합니다. 최종 HBLT는 A를 루트로, L과 C를 서브트리로 가질 것입니다. L의 s 값이 C의 값보다

배열 표현은 시간이 지남에 따라 변경될 데이터를 저장할 때 기본적으로 공간을 낭비합니다. 일부 데이터를 저장하기 위해 배열에 여러 값을 저장할 수 있을 만큼 충분히 큰 공간을 할당합니다. 배열의 크기를 늘리기 위해 배열 배가 기준을 사용한다고 가정합니다. 현재 배열 크기가 8192라고 가정합니다. 이것은 가득 찼습니다. 따라서 어레이 더블링 기술을 사용하여 증가시켜야 합니다. 따라서 새 배열 크기는 16384가 됩니다. 그런 다음 이전 배열에서 새 배열로 8192개의 요소를 복사한 다음 이전 배열의 할당을 해제합니다. 이제 우리는

최대 또는 최소 HBLT에서 임의 노드를 삭제하는 것은 표준 작업이 아닙니다. 우선 순위 대기열 또는 HBLT의 경우. HBLT에서 K라는 노드를 삭제하려면 다음 규칙을 따라야 합니다. 트리에서 K에 뿌리를 둔 하위 트리를 분리하고 노드 K의 하위 트리의 혼합으로 대체합니다. K에서 루트까지의 경로에서 s 값을 업데이트하고 HBLT의 속성을 유지하기 위해 필요에 따라 이 경로의 하위 트리를 교체합니다. s 값을 K에서 루트로 업데이트하려면 각 노드에 대한 부모 포인터가 필요합니다. s 값을 위쪽 노드로 업데이트하는

여기서 좌파 트리의 또 다른 변형을 볼 수 있습니다. 여기서 우리는 외부 노드에 대한 루트의 최단 경로 길이보다는 하위 트리의 노드 수를 고려할 것입니다. 여기서 노드 x의 가중치 w(x)를 루트 x가 있는 하위 트리의 내부 노드 수로 정의합니다. x가 외부 노드이면 가중치는 0입니다. x가 내부 노드이면 가중치는 자식의 가중치 합보다 하나 더 큽니다. 다음은 WBLT(Weight Biased Leftist Tree)의 예입니다. - 이진 트리가 다음과 같다고 가정 - 각 노드에 대해 w(x) 값을 계산하면 다음과 같습니다

여기에서 다양한 Max-WBLT 작업이 무엇인지 확인할 수 있습니다. HBLT에는 삽입, 삭제 및 초기화와 같은 다양한 작업이 있습니다. 그들은 또한 WBLT와 매우 유사합니다. 그러나 단일 위에서 아래로 통과하는 병합 작업을 수행할 수 있습니다. WBLT에 대해 단일 패스 멜드 작업이 가능합니다. 내려가는 길에 w 값을 찾을 수 있기 때문입니다. 필요에 따라 w 값을 업데이트하고 하위 트리를 교체할 수 있습니다. HBLT의 경우 트리로 내려가는 도중에 s 값을 찾을 수 없습니다. 단일 위에서 아래로 병합이 수행될 수 있으므로

이 섹션에서는 Robin-Hood 해싱 방식이 무엇인지 살펴보겠습니다. 이 해싱은 개방형 주소 지정 기술 중 하나입니다. 이것은 더 공정한 충돌 해결 전략을 사용하여 요소의 검색 시간을 균등화하려고 시도합니다. 삽입을 시도하는 동안 위치 xi에 요소 x를 삽입하려는 경우 요소 y가 이미 yj에 배치되어 있습니다. =xi , 그러면 두 요소 중 더 작은 요소가 계속 이동해야 합니다. 따라서 i ≤ j이면 xi+1 위치에 x를 삽입하려고 합니다. , xi+2 등등. 그렇지 않으면 xi 위치에 x를 저장합니다. , 위치 yj+1에 y를

추상 데이터 유형 사전을 구현하려고 하면 노드가 값과 연결됩니다. 사전은 기본적으로 전체 순서에서 가져온 요소여야 하는 키 집합입니다. 각 키와 관련된 추가 정보가 있을 수 있지만 개념적 이해로 이어지지는 않습니다. 사전이 트리를 사용하여 구현된 경우 각 노드는 고유한 키를 보유합니다. 여기에서 트리의 각 노드 u에 대해 모든 키는 u.l입니다. u.l은 u.k보다 엄격하게 작습니다. 그리고 u.r의 모든 키는 영국보다 엄격하게 큽니다. 트리는 이진 검색 트리라고 하는 이 불변량에 따라 구성됩니다. 이 불변의 주요 이점 중 하나

병합 알고리즘은 두 개의 정렬된 목록을 하나의 목록으로 병합하는 데 사용됩니다. 이 알고리즘은 다양한 경우에 사용됩니다. 병합 정렬을 수행하려면 분류기 목록을 더 큰 목록으로 병합해야 합니다. 접근 방식은 간단합니다. 우리는 두 개의 목록을 가져옵니다. 두 개의 포인터가 있을 것입니다. 첫 번째 항목은 첫 번째 목록의 요소를 가리키고 두 번째 항목은 두 번째 목록의 요소를 가리킵니다. 값에 따라 이 두 목록 중 하나에서 더 작은 요소를 가져온 다음 해당 목록의 포인터를 늘립니다. 이 작업은 하나의 목록이 소진될 때까지 수행됩니다.

여기서 B-트리가 무엇인지 살펴보겠습니다. B-트리는 특화된 m-way 탐색 트리입니다. 이것은 디스크 액세스에 널리 사용될 수 있습니다. 차수가 m인 B-트리는 최대 m-1개의 키와 m개의 자식을 가질 수 있습니다. 이것은 단일 노드에 많은 수의 요소를 저장할 수 있습니다. 그래서 키가 상대적으로 작습니다. 이것이 B-트리의 큰 장점 중 하나입니다. B-Tree는 하나의 m-way tree의 모든 속성을 가지고 있습니다. 다른 속성이 있습니다. B-Tree의 모든 노드는 최대 m개의 자식을 보유합니다. 루트와 잎을 제

여기서 우리는 R-Trees 데이터 구조를 볼 것입니다. R-트리는 효율적인 방식으로 특수 데이터 인덱스를 저장하는 데 사용됩니다. 이 구조는 특별한 데이터 쿼리 및 스토리지를 보유하는 데 매우 유용합니다. 이 R-트리에는 실제 응용 프로그램이 있습니다. 다음과 같습니다 - 다차원 정보 인덱싱 게임 데이터 처리 지리 공간 좌표 유지 가상 지도 구현 R-Tree의 한 예는 아래와 같습니다. 해당 R-트리는 아래와 같습니다 - R-트리의 속성 R-트리는 단일 루트, 내부 및 리프 노드로 구성됩니

이 섹션에서는 Red-Black Tree가 무엇인지 볼 것입니다. Red-Black Tree는 자체 균형 이진 탐색 트리입니다. 각 노드에는 몇 가지 조건이 있습니다. 다음과 같습니다 - 각 노드에는 색상이 있습니다. 빨강 또는 검정 루트는 항상 검은색입니다. 인접한 두 개의 레드 노드가 없습니다. 노드(루트 포함)에서 하위 NULL 노드까지의 모든 경로에는 동일한 수의 블랙 노드가 있습니다. 적흑나무의 예 잎에 널 노드가 있는 레드-블랙 트리 AVL 트리와의 비교 AVL 트리는 Red-Black

산술식을 작성하는 방법을 표기법이라고 합니다. 산술 표현식은 세 가지 다르지만 동등한 표기법으로 작성할 수 있습니다. 즉, 표현식의 본질이나 출력을 변경하지 않고 말입니다. 이러한 표기법은 - 중위 접두사 접미사 중위 표기법은 다른 수학적 표현을 작성할 때 사용하는 일반적인 표기법입니다. 접두사와 접미사 표기법이 상당히 다릅니다. 접두사 표기법 이 표기법에서 연산자는 접두사입니다. 피연산자에, 즉 연산자는 피연산자보다 먼저 작성됩니다. 예:+ab . 이것은 중위 표기법 a + b와 동일합니다. . 접두사 표기

여기에서 토너먼트 트리, 승자 및 패자 트리를 볼 수 있습니다. 토너먼트 트리는 n개의 외부 노드와 n – 1개의 내부 노드가 있는 완전한 이진 트리입니다. 외부 노드는 플레이어를 나타내고 내부 노드는 두 플레이어 간의 경기 승자를 나타냅니다. 이 트리는 선택 트리라고도 합니다. 토너먼트 트리에는 몇 가지 속성이 있습니다. 다음과 같습니다 - 이 나무는 뿌리가 있습니다. 따라서 트리의 링크와 부모에서 자식으로의 경로를 지정하고 부모가 없는 고유한 요소가 있습니다. 부모 값은 모든 비교 연산자에 대해 해당 노드보다 작거나

여기서 우리는 루팅되지 않은 바이너리 트리가 무엇인지 볼 것입니다. 이 트리는 순환 없이 연결된 무방향 그래프입니다. 이웃이 하나인 꼭짓점은 나무의 잎사귀입니다. 나머지 정점은 내부 노드입니다. 정점의 차수는 이웃의 수입니다. 노드가 두 개 이상인 트리에서 잎은 차수가 1인 꼭짓점입니다. 자유 트리는 모든 내부 노드가 정확히 차수가 3인 이진 트리의 한 유형입니다. 컴퓨터 과학에서 이진 트리는 데이터 구조로 사용될 때 종종 루트가 지정되고 정렬되지만 계층적 클러스터링 및 진화적 트리 재구성에서 루트가 지정되지 않은 이진 트리의 적

이 섹션에서는 뿌리가 있는 나무와 뿌리가 없는 나무의 차이점을 살펴보겠습니다. 처음에는 뿌리 및 뿌리가 없는 나무의 몇 가지 예를 볼 것입니다. 뿌리 나무의 예 - 뿌리 없는 나무의 예 - 뿌리 나무와 뿌리 내리지 않은 나무의 기본 차이점 루트 트리에서 후손이 있는 각 노드는 유추된 후손의 가장 최근 공통 조상을 나타냅니다. 일부 나무에서는 가장자리 길이가 예상 시간으로 해석될 수 있습니다. 뿌리가 없는 나무에는 조상 뿌리가 없습니다. 뿌리가 없는 나무는 분기 순서를 나타내지만 마지막 공통 조상의 위치의 뿌리를 나타내지는

모든 해시 함수에 대해 테이블 ​​크기 m이 유니버스 크기 u보다 훨씬 작으면 해시 함수 h에 대해 동일한 값을 갖는 U의 일부 큰 하위 집합이 있다고 말할 수 있습니다. 해시 값. 이 문제를 없애기 위해 우리는 해시 함수 세트가 필요합니다. 여기서 S에 대해 잘 작동하는 것을 선택할 수 있습니다. 대부분의 해시 함수가 S에 더 좋다면 임의의 해시 함수를 선택할 수 있습니다. ℌ가 해시 함수의 집합이라고 가정합니다. 각 x, y ∈ U에 대해 h(x) =h(y)가 최대 |ℌ|/𝑚인 경우 h ∈ ℌ의 수가 ℌ이라고 할 수 있습니

이 섹션에서는 연결을 사용한 해싱이 무엇인지 볼 것입니다. Chaining은 충돌 해결 기술 중 하나입니다. 충돌을 피할 수는 없지만 충돌을 줄이고 동일한 해시 값에 대해 여러 요소를 저장하려고 할 수 있습니다. 이 기술은 우리의 해시 함수 h(x)가 0에서 6까지라고 가정합니다. 따라서 7개 이상의 요소에 대해서는 같은 방 안에 위치할 몇 가지 요소가 있어야 합니다. 이를 위해 우리는 그에 따라 저장할 목록을 만들 것입니다. 매번 O(1) 시간에 삽입을 수행하기 위해 목록의 시작 부분에 추가합니다. 더 나은 아이디어를 얻기 위