초안:2-3 트리
틀:초안 컴퓨터 과학에서 2–3 트리(2–3 tree)는 자료 구조에서의 트리 구조의 일종으로, 1970년에 존 홉크로프트가 발명했다. 기존의 이진 트리가 하나의 부모 노드에 자식 노드가 2개인 형태라면, 이 트리는 하나의 노드에 값이 2개까지 들어갈 수 있고, 자식 노드를 3개까지 둘 수 있는 것이 특징이다. 2–3 트리는 B 트리의 order 3에 해당된다.[1] 리프 노드에는 자식 노드가 존재하지 않고, 데이터가 1개 또는 2개가 있다.
정의
2–3 트리에서 하나의 데이터 요소에 자식 노드가 2개 있다면, 2-노드, 2개의 데이터 요소에 자식 노드가 3개가 있으면, 3-노드로 부른다.
3개의 데이터 요소가 존재하는 4-노드의 경우에는 트리를 만드는 동안에 일시적으로 존재할 수 있지만, 영구적이지 않으며, 최종적으로는 분리된 형태를 띈다.
-
2-노드 -
3-노드
속성
- 모든 내부 노드는 2노드 또는 3노드다.
- 모든 이파리 노드는 같은 레벨에 존재한다.
- 모든 데이터는 정렬된 순서로 유지된다.
과정
탐색
2-3 트리에서 항목을 탐색하는 것은 이진 탐색 트리에서 항목을 탐색하는 알고리즘과 유사하다. 각 노드의 데이터 요소는 순서가 지정되어 있으므로 탐색 기능은 올바른 하위 트리로 이동하고 최종적으로 항목을 포함하는 올바른 노드로 이동한다.
- 틀:Mvar를 2-3 트리라고 하고 틀:Mvar를 찾아야 하는 데이터 요소로 했을 때, 만약 틀:Mvar가 비어 있다면, 틀:Mvar는 틀:Mvar에 없는 것으로 작업이 완료된다.
- 틀:Mvar를 틀:Mvar의 근이라고 가정한다.
- 틀:Mvar가 이파리 노드라고 가정한다.
- 틀:Mvar가 왼쪽 자식 틀:Mvar와 오른쪽 자식 틀:Mvar가 있는 2-노드라고 가정을 하자. 틀:Mvar가 틀:Mvar의 데이터 요소일 때. 3가지의 경우가 있다.
- Suppose 틀:Mvar is a 3-node with left child 틀:Mvar, middle child 틀:Mvar, and right child 틀:Mvar. Let 틀:Mvar and 틀:Mvar be the two data elements of 틀:Mvar, where . There are four cases:
삽입
삽입은 트리의 균형 잡힌 속성을 유지한다.[2]
2-노드에 데이터를 삽입하려면 새로운 키가 순서에 맞게 2-노드에 추가된다.
3-노드에 삽입하려면 3-노드의 위치에 따라 더 많은 작업이 필요할 수 있다. 트리가 3-노드로만 구성되었을 경우에 해당 노드는 적절한 키와 자식이 있는 3개의 2-노드로 분할된다.
대상 노드가 3-노드이고 부모가 2-노드인 경우에는 키를 3-노드에 삽입하여 임시로 4-노드를 생성한다. 그림에서 10은 6과 9가 있는 2-노드에 삽입된다. 중간 키는 9이며, 상위 2-노드로 승격된다. 이렇게 하면 6과 10의 3-노드가 남고, 부모 3-노드의 자식으로 유지되는 2개의 2-노드로 분할된다.
대상 노드가 3-노드이고 상위 노드가 3-노드인 경우 임시 4-노드를 생성한 후 위와 같이 분할한다. 이 과정은 트리에서 루트까지 계속된다. 루트를 분할해야 할 경우에는 단일 3-노드 프로세스를 따른다. 임시 4-노드 루트가 3개의 2-노드로 분할되고 그 중 하나가 루트로 간주된다. 이러한 작업은 트리의 높이를 1씩 증가시킨다.
병렬 과정
틀:참고 2-3 트리는 레드-블랙 트리와 구조가 유사하기 때문에 레드-블랙 트리의 병렬 알고리즘은 2-3 트리에도 똑같이 적용될 수 있다.