13-1. 2-3 트리

01. 2-3트리

2-3트리(2-3tree)

- 차수가 2또는 3인 내부 노드를 갖는 탐색 트리

- 2-노드와 3-노드만으로 구성되는 특수한 형태의 B트리임

- 2-노드 혹은 3-노드라는 제약이 내부 노드에만 해당함

   → 모든 잎 노드는 같은 레벨에 있어야 한다는 제약만 존재함

 

2-3트리(2-3tree) 조건

① 각각의 내부 노드는 2-노드이거나 3-노드이다. 2-노드는 1개의 키값을,3-노드는 2개의 키값을 갖는다.

② lchild,mchild 를 각각 2-노드의 왼쪽 자식 및 중간 자식이라 하고,lkey 가 이 노드의 키값이라 하자.그러면 루트가 lchild인 모든 2-3서브 트리 키값은 lkey보다 작고,루트가 mchild인 모든 2-3서브 트리 키값은 lkey보다 크다.

③ lchild,mchild및 rchild를 각각 3-노드의 왼쪽,중간 및 오른쪽 자식이라 하고,lkey및 rkey를 이 노드의 두 키값이라 하면,다음이 성립한다.

   a. lkey < rkey

   b. 루트가 ichild인 모든 2-3 서브 트리 키값은 lkey 보다 작다.

   c. 루트가 mchild인 모든 2-3 서브 트리 키값은 rkey 보다 작고, lkey 보다 크다.

   d. 루트가 rchild인 모든 2-3 서브 트리 데이터는 rkey보다 크다.

④ 모든 잎 노드는 같은 레벨에 있다.

 

 

2-3 트리

 

2-3트리의 탐색

typedef struct two_three *two_three_ptr;
struct two_three {
	int lkey,rkey;
	two_three_ptr lchild,mchild,rchild;
};


two_three_ptr search23(two_three_ptr t,int x){
	while(t)
		switch(compare(x,t)){ // 검색키 x와 노드 t에 있는 키값을 비교
			case1 : t = t -> lchild ; // x가 노드 t의 왼쪽 키값(lchild)보다 작은 경우
				break;
			case2 : t = t -> mchild ; 
          		  // x가 노드 tdml 왼쪽 키값보다 크고 오른쪽 키값보다 작은경우
				break;
			case3 : t = t -> rchild ; // x가 노드 t의 오른쪽 키값(rchild)보다 큰 경우
				break;
			case4 : return(t); } // x가 노드 t의 키값들 중 어느 하나와같은 경우
	return(NULL); }

 

 

2-3트리의 삽입

 

2-3트리의 삽입 알고리즘

void insert23(two_three_ptr t,int y){
	two_three_ptr q,p,r;
	if(!(*t))
		new_root(t,y,NULL);
	else{
		p=find_node(*t,y);
		if(!p){
			fprintf(stderr,"The keyiscurrentlyinthetree\n");
			exit(1); }

q=NULL;
  for(;;)
	if(p->rkey ==INT_MAX){
	  put_in(&p,y,q);
		break;}
	  else{
		split(p,&y,&q);
	      if(p==*t){
			  new_root(t,y,q);
			  break;}
			else
			  p=delete(); }  }  }

 

 

2-3트리의 삭제

- 2-3 트리의 삭제에서 잎 노드가 아닌 노드의 키를 삭제하면 그곳을 다른 키로 대체해야 함

- 일반적으로 삭제한 키의 왼쪽 서브트리에서 가장 큰 키값이나 오른쪽 서브트리에서 가장 작은 키값을 선택하여 대체함