2-3 트리
2–3 tree2-3 트리 | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
유형 | 나무 | ||||||||||||||||||||
발명된 | 1970 | ||||||||||||||||||||
발명된 사람 | 존 홉크로프트 | ||||||||||||||||||||
큰 O 표기법에서의 시간 복잡성 | |||||||||||||||||||||
|
컴퓨터 과학에서 2-3 트리는 나무 데이터 구조로, 자식(내부 노드)이 있는 모든 노드는 자식(내부 노드)이 2명, 데이터 요소가 1명 또는 자식(3노드)이 3명, 데이터 요소가 2명 있다.2-3 트리는 순서 3의 B 트리다.[1]트리 외부에 있는 노드(리프 노드)에는 자식 노드가 없고 데이터 요소가 하나 또는 두 개 있다.[2][3]2-3 그루의 나무는 1970년에 존 홉크로프트에 의해 발명되었다.[4]
2-3 그루의 나무가 균형을 이루어야 하는데, 이는 각 잎이 같은 수준이라는 것을 의미한다.노드의 각 오른쪽, 중앙 및 왼쪽 하위 트리는 동일한 양의 데이터를 포함하거나 거의 같은 양의 데이터를 포함하고 있다.
정의들
우리는 내부 노드가 1개의 데이터 요소와 2개의 자식 요소를 가지고 있다면 2-노드라고 말한다.
우리는 내부 노드가 2개의 데이터 요소와 3개의 자식 요소를 가지고 있다면 3-노드라고 말한다.
3개의 데이터 요소가 있는 4노드는 트리 조작 중에 일시적으로 생성될 수 있지만 트리에는 절대 끈질기게 저장되지 않는다.
우리는 T가 다음 중 하나의 진술이 유지되는 경우에만 2–3 나무라고 말한다.[5]
- T는 비어 있다.즉, T에는 노드가 없다.
- T는 데이터 요소 a를 가진 2-노드다.T가 좌측 차일드 p와 우측 차일드 q를 가진 경우
- p와 q는 같은 높이의 2-3그루의 나무다.
- a는 p의 각 요소보다 크다.
- a는 q의 각 데이터 요소보다 작다.
- T는 데이터 요소 a와 b가 있는 3-노드(여기서 a <b)이다.T가 p, q중, q중, r중, r중간, r중간인 경우
- p, q 및 r은 높이가 같은 2–3의 나무다.
- a는 p의 각 데이터 요소보다 크고 q의 각 데이터 요소보다 작다.
- b는 q 단위의 각 데이터 요소보다 크고 r 단위의 각 데이터 요소보다 작다.
특성.
- 모든 내부 노드는 2-노드 또는 3-노드다.
- 모든 잎이 같은 높이에 있다.
- 모든 데이터는 정렬된 순서대로 보관된다.
운영
검색 중
2-3 트리에서 항목을 검색하는 것은 이진 검색 트리에서 항목을 검색하는 것과 유사하다.각 노드의 데이터 요소를 정렬하기 때문에 검색 기능은 올바른 하위 트리와 결국 항목이 포함된 올바른 노드로 향하게 된다.
- T를 2-3 트리가 되게 하고 우리가 찾고자 하는 데이터 요소가 되게 하라.T가 비어있으면 D가 T에 없고 우리는 끝이다.
- T의 근원이 되자.
- t가 잎이라고 가정하자.
- d가 t에 없으면 d는 T에 있지 않다.그렇지 않으면 d는 T에 있다.우리는 더 이상의 조치가 필요없고 우리는 끝이다.
- t가 좌측 차일드 p와 우측 차일드 q를 포함하는 2-노드라고 가정한다. a를 t의 데이터 요소가 되도록 한다.다음과 같은 세 가지 경우가 있다.
- 만약 d가 a와 같다면, 우리는 T에서 d를 찾았고 우리는 끝이다.
- 인 경우 T를 2–3 트리인 p로 설정하고 2단계로 돌아가십시오.
- > 인 경우 T를 q로 설정하고 2단계로 돌아가십시오.
- t가 왼쪽 자식 p, 중간 자식 q 및 오른쪽 자식 r을 가진 3-노드라고 가정하자.a와 b를 t의 두 데이터 요소(여기서 < a로 한다.다음과 같은 네 가지 경우가 있다.
- 만약 d가 a나 b와 같다면 d는 T에 있고 우리는 끝이다.
- 가 인 경우 T를 p로 설정하고 2단계로 돌아가십시오.
- < 경우 T를 q로 설정하고 2단계로 돌아가십시오.
- > 인 경우 T를 r로 설정하고 2단계로 돌아가십시오.
삽입
삽입은 나무의 균형 잡힌 속성을 유지한다.[5]
2-노드에 삽입하기 위해 새 키가 적절한 순서로 2-노드에 추가된다.
3노드에 삽입하기 위해서는 3노드의 위치에 따라 더 많은 작업이 필요할 수 있다.트리가 3-노드로만 구성된 경우, 노드는 적절한 키와 하위 키를 가진 3개의 2-노드로 분할된다.
대상 노드가 부모 노드가 2노드인 3노드인 경우 3노드에 키를 삽입해 임시 4노드를 만든다.그림에서 키 10은 6과 9로 2노드에 삽입된다.중간 키는 9이며, 상위 2노드로 승격된다.이로써 3노드는 6과 10의 3노드가 남으며, 2노드는 부모 3노드의 자녀로 보유하게 된다.
대상 노드가 3노드이고 상위 노드가 3노드일 경우, 임시 4노드가 생성된 후 위와 같이 분할된다.이 과정은 나무에서 뿌리까지 계속된다.루트를 분할해야 하는 경우, 단일 3노드의 프로세스가 뒤따른다. 즉, 임시 4노드 루트는 3개의 2노드로 분할되며, 그 중 하나는 루트로 간주된다.이 작전은 나무의 높이를 하나씩 키운다.
병렬 연산
2-3그루의 나무는 적색-흑색 나무와 구조가 비슷하기 때문에 적색-흑색 나무의 병렬 알고리즘도 2~3그루의 나무에도 적용할 수 있다.
참고 항목
참조
- ^ Knuth, Donald M (1998). "6.2.4". The Art of Computer Programming. Vol. 3 (2 ed.). Addison Wesley. ISBN 9780201896855.
The 2–3 trees defined at the close of Section 6.2.3 are equivalent to B-Trees of order 3.
- ^ Gross, R. Hernández, J. C. Lázaro, R. Dormido, S. Ros (2001). Estructura de Datos y Algoritmos. Prentice Hall. ISBN 84-205-2980-X.
- ^ Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley., pp.p.p.p.145–145.
- ^ Cormen, Thomas (2009). Introduction to Algorithms. London: The MIT Press. pp. 504. ISBN 978-0262033848.
- ^ a b Sedgewick, Robert; Wayne, Kevin. "3.3". Algorithms (4 ed.). Addison Wesley. ISBN 9780321573513.