2-3 트리

2-3 트리
2-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노드는 트리 조작 중에 일시적으로 생성될 수 있지만 트리에는 절대 끈질기게 저장되지 않는다.

2절
3노드

우리는 $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$ 를 찾았고 우리는 끝이다.
- $d<a$ 인 경우 $T$ 를 2–3 트리인 $p$ 로 설정하고 2단계로 돌아가십시오.
- $d>a$ > ${\displaystyle d>a$ 인 경우 $T$ 를 $q$ 로 설정하고 2단계로 돌아가십시오.
$t$ 가 왼쪽 자식 $p$ , 중간 자식 $q$ 및 오른쪽 자식 $r$ 을 가진 3-노드라고 가정하자. $a$ 와 $b$ 를 $t$ 의 두 데이터 요소(여기서 < $a<b$ ${\displaystyle$ a $<b$ 로 한다.다음과 같은 네 가지 경우가 있다.
- $만약$ $d$ 가 $a$ 나 b와 같다면 $d$ 는 $T$ 에 있고 우리는 끝이다.
- $d<a$ 가 ${\displaystyle d$ 인 경우 $T$ 를 $p$ 로 설정하고 2단계로 돌아가십시오.
- $a<d<b$ $a<d<b$ < $a<d<b$ ${\dyle a<d$ 경우 $T$ 를 $q$ 로 설정하고 2단계로 돌아가십시오.
- $d>b$ > $d>b$ ${\displaystyle d>b$ 인 경우 $T$ 를 $r$ 로 설정하고 2단계로 돌아가십시오.

삽입

삽입은 나무의 균형 잡힌 속성을 유지한다.^[5]

2-노드에 삽입하기 위해 새 키가 적절한 순서로 2-노드에 추가된다.

3노드에 삽입하기 위해서는 3노드의 위치에 따라 더 많은 작업이 필요할 수 있다.트리가 3-노드로만 구성된 경우, 노드는 적절한 키와 하위 키를 가진 3개의 2-노드로 분할된다.

2-3 트리에 숫자를 삽입하여 3가지 가능한 경우

대상 노드가 부모 노드가 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.

외부 링크

2-3 Tree 상세 설명

[1] 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.

[2] 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.

[3] 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.

[4] Cormen, Thomas (2009). Introduction to Algorithms. London: The MIT Press. pp. 504. ISBN 978-0262033848.

[A4-5] Sedgewick, Robert; Wayne, Kevin. "3.3". Algorithms (4 ed.). Addison Wesley. ISBN 9780321573513.

[1]

[2]

[3]

[4]

[5]

v t 트리 데이터 구조
나무 검색 (이중 세트/관련 배열)	2–3 2–3–4 AA (a,b) AVL B B+ B* B^x (최적) 이진 검색 춤 HTree 간격 오더통계 (좌편향) 빨강-검은색 희생양 스플레이 T 트레프 UB 무게균형
힙스	이진수 이항체 브로달 피보나치 좌익 페어링 스큐 판 엠드 보아스 약한
시도하다	씨트리 C-트리(압축 ADT) 해시 라딕스 접미사 3차 검색 X-fast Y-fast
공간 데이터 분할 트리	볼 BK BSP 카르테시안 힐베르트 R k-d(일반적으로 k-d) M 미터법 MVP 옥트리 PH 우선 순위 R 쿼드 R R+ R* 세그먼트 부사장 X
다른 나무들	커버 지수적 펜윅 손가락 프랙탈 트리 지수 퓨전 해시 캘린더 아이 디스턴스 케이애리 왼손잡이 우시블링 링크/컷 로그 구조 병합 머클 p q. 범위 SPQR 톱

v t 잘 알려진 데이터 구조
종류들	컬렉션 컨테이너
추상적	연관 배열 멀티맵 검색 데이터 구조 리스트 쌓다 큐 더블엔드 큐 우선 순위 대기열 이중 종료 우선 순위 대기열 세트 멀티셋 디스조인트
배열	비트 배열 원형완충기 동적 배열 해시 테이블 해시드 배열 트리 희소 행렬
연결됨	연관 리스트 링크 리스트 목록 건너뛰기 연결 해제 목록 XOR 연결 목록
나무들	B-트리 이진 검색 트리 AA 나무 AVL 트리 붉은-검은 나무 자기균형나무 스플레이 트리 힙 이진 힙 이항 힙 피보나치 더미 R-트리 R* 트리 R+ 트리 힐베르트 R 트리 트라이 해시 트리
그래프	이진결정도 방향 아세클릭 그래프 지시된 반복 단어 그래프
데이터 구조 목록

Search

2-3 트리

네임스페이스

더

목차

정의들

특성.

운영

검색 중

삽입

병렬 연산

참고 항목

참조

외부 링크