2-3 트리는 트리의 모든 노드가 2 노드인 데이터 구조의 트리 유형입니다.
또는 3개의 노드. B-Tree의 특수한 유형입니다. 주문 3.
트리의 2 노드는 하나의 데이터 부분과 두 개의 하위 노드가 있는 노드입니다.
트리의 3개 노드는 2개의 데이터 부분과 3개의 하위 노드가 있는 노드입니다.
그림:- 2-3 트리
2-3 트리의 속성:-
-
모든 내부 노드는 2노드 또는 3노드입니다.
-
하나의 데이터 부분을 포함하는 노드는 정확히 2개의 자식이 있는 2 노드 또는 자식이 없는 리프 노드가 될 수 있습니다.
-
2개의 데이터 부분을 포함하는 노드는 정확히 3개의 자식이 있는 3개의 노드일 수 있습니다.
-
모든 리프 노드는 항상 동일한 수준에 있습니다.
-
2-3 트리는 항상 높이 균형 트리입니다.
-
검색 작업은 2-3 트리에서 빠르고 효율적입니다.
2 노드:-
-
정확히 두 자녀입니다.
-
체중이 더 작은 왼쪽 아이.
-
체중이 더 많이 나가는 오른쪽 아이.
-
자식이 없는 리프 노드일 수 있습니다.
3 노드:-
-
정확히 세 자녀입니다.
-
2개의 데이터 값.
-
왼쪽 데이터 값보다 가중치가 작은 왼쪽 자식입니다.
-
두 데이터 값 사이에 가중치가 있는 중간 자식입니다.
-
가중치가 올바른 데이터 값보다 큰 오른쪽 자식입니다.
-
절대 리프 노드가 될 수 없습니다.
2-3 트리의 작업:-
1. 2-3 트리에서 검색
-
데이터가 정렬될 때 이진 검색 트리의 검색 작업과 유사합니다.
-
2-3 트리에서 X를 검색하려면
-
트리가 비어 있으면 → False 반환
-
루트 노드에 도달하면 False를 반환합니다(찾을 수 없음)
-
X가 왼쪽 데이터 부분보다 작으면 왼쪽 하위 트리를 검색합니다.
-
X가 왼쪽 데이터보다 크고 오른쪽 데이터보다 크면 중간 하위 트리를 검색합니다.
-
X가 오른쪽 데이터 부분보다 크면 오른쪽 하위 트리를 검색합니다.
2. 2-3 트리에 노드 삽입
-
2-3 트리에 X를 삽입하려면
-
트리가 비어 있는 경우 → 루트로 X를 추가합니다.
-
X의 올바른 위치를 찾아 리프 노드로 추가합니다.
-
데이터 부분이 하나인 리프 노드가 있는 경우 X를 추가하면 리프 노드가 2 - 노드가 됩니다.
-
리프 노드에 두 개의 데이터 부분이 있는 경우 X를 추가합니다. 임시 3개 노드를 분할하고 정렬 순서에 따라 데이터를 상위 노드로 이동합니다.
2~3개의 트리를 만들고 노드를 순서대로 추가 → 10, 5, 8, 15, 23, 21
3. 2-3 트리에서 노드 삭제
-
2-3 트리에서 X를 삭제하려면
-
트리가 비어 있으면 false를 반환합니다.
-
X의 위치를 찾아 삭제 후 트리를 조정합니다.
-
X가 3 노드의 일부인 경우 X를 삭제하고 왼쪽 값과 중간 값을 조정합니다. 필요한 경우 노드의 조상의 왼쪽과 중간 값도 조정합니다.
-
X가 2개 노드의 일부인 경우 정렬된 순서로 노드를 정렬하는 재귀적 방식으로 트리를 조정하고 분할합니다.