2-3-4 나무

2–3–4 tree
2-3-4 나무
유형나무
큰 O 표기법에서의 시간 복잡성
알고리즘. 평균 최악의 경우
공간 O(n) O(n)
검색 O(log n) O(log n)
삽입하다 O(log n) O(log n)
삭제 O(log n) O(log n)

컴퓨터 과학에서 2–3–4 트리(일명 2–4 트리)는 사전을 구현하는 데 사용할 수 있는 자기 균형 데이터 구조다.숫자는 하위 노드(내부 노드)가 있는 모든 노드가 2개, 3개 또는 4개의 하위 노드를 갖는 트리를 의미한다.

  • 2-노드는 하나의 데이터 요소를 가지며, 내부에 2개의 하위 노드가 있는 경우
  • 3-노드는 2개의 데이터 요소를 가지며, 내부에는 3개의 하위 노드가 있는 경우,
  • 4-노드는 3개의 데이터 요소를 가지며, 내부에 4개의 하위 노드가 있는 경우

  • 2노드

  • 3노드

  • 4노드

2–3–4 트리는 순서 4의 B-tree이다.[1] 일반적인 B-tree와 마찬가지로 O(log n) 시간에 검색, 삽입 및 삭제할 수 있다.2–3–4 트리의 한 가지 속성은 모든 외부 노드가 동일한 깊이에 있다는 것이다.

2–3–4 트리는 적색-흑색 트리와 이형성이며, 이는 동등한 데이터 구조임을 의미한다.즉, 모든 2-3-4 트리에 대해 동일한 순서로 데이터 요소를 가진 최소 1개의 적색 흑색 트리가 존재한다.또한 노드 확장, 분할 및 병합이 발생하는 2–3–4 나무의 삽입 및 삭제 작업은 적색-흑색 나무의 색상 플립 및 회전과 동일하다.적색-흑색 나무에 대한 소개는 개념적으로 더 단순하기 때문에 보통 2-3-4 그루의 나무를 먼저 소개한다.그러나 2–3–4의 트리는 트리의 운영에 관련된 특수 사례가 많기 때문에 대부분의 프로그래밍 언어에서 구현하기 어려울 수 있다.적색-흑색 나무는 구현이 더 간단하기 때문에 대신 사용하는 경향이 있다.[2]

특성.

  • 모든 노드(리프 또는 내부)는 2-노드, 3-노드 또는 4-노드로, 각각 1개, 2개 또는 3개의 데이터 요소를 보유한다.
  • 모든 잎은 같은 깊이(하단 레벨)에 있다.
  • 모든 데이터는 정렬된 순서대로 보관된다.

삽입

값을 삽입하려면 2-3-4 트리의 루트부터 시작하십시오.

  1. 현재 노드가 4-노드인 경우:
    • 중간 값을 제거하고 저장하여 3노드를 얻으십시오.
    • 나머지 3노드를 2노드 쌍으로 분할한다(현재 누락된 중간값은 다음 단계에서 처리됨).
    • 루트 노드(따라서 상위 노드가 없는 경우):
      • 중간 값은 새로운 루트 2 노드가 되고 트리 높이가 1씩 증가한다.뿌리로 올라가다.
    • 그렇지 않으면 중간 값을 상위 노드에 밀어 넣으십시오.상위 노드로 이동하십시오.
  2. 간격에 삽입할 값이 포함된 어린이를 찾으십시오.
  3. 하위 항목이 리프인 경우 하위 노드에 값을 삽입하고 마침표를 작성하십시오.
    • 그렇지 않은 경우, 아이로 내려가서 1단계부터 반복하십시오.[3][4]

예

이 2-3-4 트리에 "25" 값을 삽입하려면:

2-3-4-tree-insertion-stage-1.svg
  • 뿌리(10, 20)에서 시작하여 가장 오른쪽 아이를 향해 하강한다(22, 24, 29). (그 간격(20, ∞)은 25를 포함한다.)
  • 노드(22, 24, 29)는 4-노드여서 그 중간 요소 24가 상위 노드로 밀려난다.
2-3-4-tree-insertion-stage-2.svg
  • 나머지 3노드(22, 29)는 2노드(22), 2노드(29) 쌍으로 나뉜다.새로운 부모(10, 20, 24)로 다시 올라간다.
  • 가장 오른쪽의 아이(29)를 향해 하강한다. (이 간격(24, contains)에는 25가 포함된다.)
2-3-4-tree-insertion-stage-3.svg
  • 노드(29)는 가장 왼쪽의 아이가 없다. (간격의 아이(24, 29)는 비어 있다.)여기서 멈추고 값 25를 이 노드에 삽입하십시오.
2-3-4-tree-insertion-stage-4.svg

삭제

요소를 삭제할 수 있는 가장 간단한 방법은 요소를 그대로 두고 "삭제됨"으로 표시하여 삭제된 요소가 무시되도록 이전 알고리즘을 조정하는 것이다.삭제된 요소는 나중에 삽입할 때 덮어써 다시 사용할 수 있다.그러나 이 방법의 단점은 나무의 크기가 줄지 않는다는 것이다.트리의 원소 중 상당 부분을 삭제하면 트리는 현재 저장된 원소의 크기보다 훨씬 커지게 되며, 삭제된 원소의 경우 다른 조작의 성능에 악영향을 주게 된다.

바람직하지 않은 경우, 다음 알고리즘을 따라 2-3-4 트리에서 값을 제거할 수 있다.

  1. 삭제할 요소를 찾으십시오.
    • 요소가 리프 노드에 없는 경우 위치를 기억하고 요소의 후속 요소가 포함될 리프에 도달할 때까지 검색을 계속하십시오.후계자는 제거할 키보다 작은 키 또는 제거할 키보다 큰 키 중 가장 작은 키가 될 수 있다.발견된 리프 노드가 2노드가 되지 않도록 위에서 아래로 트리를 조정하는 것이 가장 간단하다.그래야 스왑이 끝나면 빈 잎사귀 노드가 생기지 않는다.
    • 요소가 2-노드 리프에 있는 경우 아래에서 조정하십시오.

루트 노드를 제외한 2-노드가 제거하려는 리프로 이동하는 도중에 발견될 경우 다음과 같이 조정하십시오.

  1. 이 노드의 양쪽에 있는 형제가 3-노드 또는 4-노드(키 1개 이상 포함)인 경우 해당 형제를 사용하여 회전하십시오.
    • 이 노드에 가장 가까운 다른 형제들의 키는 두 노드를 간과하는 상위 키로 이동한다.
    • 상위 키는 이 노드로 이동하여 3노드를 형성한다.
    • 원래 회전된 형제 키와 함께 있던 아이는 이제 이 노드의 추가 자식이다.
  2. 부모가 2노드이고 형제자매도 2노드일 경우, 세 요소를 모두 결합하여 새로운 4노드를 형성하고 트리를 단축한다.(이 규칙은 부모 2노드가 루트인 경우에만 트리거할 수 있으며, 도중에 다른 모든 2노드는 2노드가 아닌 것으로 수정될 것이기 때문이다.이것이 이곳의 "나무의 길이를 줄이다"가 균형을 유지하는 이유다. 이것은 또한 핵융합 작용에 있어 중요한 가정이다.)
  3. 부모가 3-노드 또는 4-노드이고 모든 인접 형제자매가 2-노드인 경우 부모 및 인접 형제와 함께 퓨전 작업을 수행하십시오.
    • 인접한 형제와 두 형제 노드가 내려다보이는 부모 키가 함께 모여 4노드를 형성한다.
    • 이 노드로 형제 자식 전송

일단 추구하는 값에 도달하면, 리프 노드에 1개 이상의 키가 있다는 것을 확실히 했기 때문에 이제 제거된 엔트리 위치에 문제없이 배치될 수 있다.

2–3–4 트리의 삭제는 O(log n)이며, 일정한 시간(O(1))에 전송 및 융접을 실행한다고 가정한다.[3][5]

병렬 연산

2–3–4 나무는 적색–흑색 나무와 구조가 비슷하기 때문에 적색–흑색 나무의 병렬 알고리즘을 2–3–4 나무에도 적용할 수 있다.

참고 항목

참조

  1. ^ Knuth, Donald (1998). Sorting and Searching. The Art of Computer Programming. Vol. 3 (Second ed.). Addison–Wesley. ISBN 0-201-89685-0.. 섹션 6.2.4: 다방향 트리, 페이지 481–491.또한 6.2.3 (균형수목) 섹션 476–477 페이지에서는 2-3 그루의 나무를 논한다.
  2. ^ Sedgewick, Robert (2008). "Left-Leaning Red–Black Trees" (PDF). Left-Leaning Red–Black Trees. Department of Computer Science, Princeton University.
  3. ^ a b Ford, William; Topp, William (2002), Data Structures with C++ Using STL (2nd ed.), New Jersey: Prentice Hall, p. 683, ISBN 0-13-085850-1
  4. ^ Goodrich, Michael T; Tamassia, Roberto; Mount, David M (2002), Data Structures and Algorithms in C++, Wiley, ISBN 0-471-20208-8
  5. ^ Grama, Ananth (2004). "(2,4) Trees" (PDF). CS251: Data Structures Lecture Notes. Department of Computer Science, Purdue University. Retrieved 2008-04-10.

외부 링크