[Data Structure] 2-3 Tree

2-3 Tree

차수가 2 또는 3인 노드를 가지는 트리이다.

완전 균형 트리이다.

많이 쓰이진 않지만, B/B+ 트리, T 트리의 기본 구조이다.

 

2 Node	3 Node

Search(탐색)

2 Node

X = key → 탐색 종료

X < key → 왼쪽 서브 트리 탐색

X > key → 오른쪽 서브 트리 탐색

3 Node

X = 왼쪽 key or 오른쪽 key → 탐색 종료

X < 왼쪽 key → 왼쪽 서브 트리 탐색

X > 왼쪽 key and X < 오른쪽 key → 중간 서브 트리 탐색

X > 오른쪽 key → 오른쪽 서브 트리 탐색

Insertion(삽입)

2 Node에 삽입할 경우

2 노드는 3 노드가 되고 작은 데이터가 왼쪽 데이터, 큰 데이터가 오른쪽 데이터가 된다.

3 Node에 삽입할 경우

3 노드가 2개의 2 노드로 분리된다. 가장 작은 데이터는 왼쪽 2 노드, 가장 큰 데이터는 오른쪽 2 노드, 중간 데이터는 부모 노드로 간다. 이때 만약 부모 노드도 3 노드라면 계속해서 분리된다.

Deletion(삭제)

3 Node의 데이터를 삭제할 경우

3 노드가 리프 노드일 경우: 그냥 데이터를 삭제한다.

3 노드가 리프 노드가 아닐 경우

왼쪽과 오른쪽 자식 노드가 둘 다 2 노드인 경우: 두 자식 노드를 머지하고 데이터를 삭제한다.

왼쪽과 오른쪽 자식 노드 중 하나가 3 노드인 경우

삭제할 데이터가 왼쪽 데이터라면 왼쪽 데이터를 왼쪽 서브 트리 중 제일 큰 데이터 or 중간 서브 트리 중 가장 작은 데이터와 바꾸고 데이터를 삭제한다

삭제할 데이터가 오른쪽 데이터라면 오른쪽 데이터를 중간 서브 트리 중 가장 큰 데이터 or 오른쪽 서브 트리 중 가장 작은 데이터와 바꾸고 데이터를 삭제한다.

2 Node의 데이터를 삭제할 경우

형제 노드 중 3 노드가 있을 경우

2 노드가 왼쪽에 있을 경우

중간 형제 노드가 3 노드라면 부모 데이터 중 가장 작은 데이터를 2 노드로 옮기고 중간 형제 노드 데이터 중 가장 작은 데이터를 부모 노드로 옮긴다.

중간 형제 노드가 2 노드라면 부모의 데이터 중 가장 작은 데이터를 중간 형제 노드로 옮긴다.

2 노드가 오른쪽에 있을 경우

중간 형제 노드가 3 노드라면 부모 데이터 중 가장 큰 데이터를 2 노드로 옮기고 중간 형제 노드 데이터 중 가장 큰 데이터를 부모 노드로 옮긴다.

중간 형제 노드가 2 노드라면 부모의 데이터 중 가장 큰 데이터를 중간 형제 노드로 옮긴다.

2 노드가 중간에 있을 경우

왼쪽 형제 노드가 3 노드라면 부모 데이터 중 가장 작은 데이터를 2 노드로 옮기고 왼쪽 형제 노드 데이터 중 가장 큰 데이터를 부모 노드로 옮긴다.

오른쪽 형제 노드가 3 노드라면 부모 데이터 중 가장 큰 데이터를 2 노드로 옮기고 오른쪽 형제 노드 데이터 중 가장 작은 데이터를 부모 노드로 옮긴다.

형제 노드 중 3 노드가 없을 경우

부모 노드의 데이터를 2 노드의 왼쪽이나 오른쪽 형제 노드로 옮긴다.