[자료구조] 2-3트리

2-3 트리란?

트리 내부노드의 자식수(=차수)가 2 or 3인 완전균형탐색트리입니다.

 

차수가 2인 노드는 2-노드 / 3인 노드는 3-노드라고 부릅니다.

해당 노드의 다리 개수로 판단하면 됩니다.

완전균형탐색트리란?

1)루트로부터 각 리프노드(=이파리노드)까지 경로길이가 모두 같음

2)모든 리프노드가 같은 층에 있는 탐색트리

- 1),2)는 같은 말입니다.

 

2-3 트리의 탐색연산

case 1) 현재노드가 2-노드(키1개, 자식2개) 인 경우

if 탐색노드 < 현재노드(2-노드)라면 왼쪽자식으로,

else if 탐색노드 > 현재노드(2-노드)라면 오른쪽자식으로,

else 탐색노드 = 현재노드라면 탐색완료.

 

case2) 현재노드가 3-노드(키2개, 자식3개) 인 경우 k1,k2와 비교함.

if 탐색노드 < k1 이면 왼쪽자식으로,

else if (k1< 탐색노드 < k2) 이면 중간자식으로,

else k2 < 탐색노드 이면 오른쪽 자식으로.

 

2-3 트리의 삭제연산