이진 탐색 트리

  하나의 노드에 여러개의 노드를 연결하는 자료구조를 트리 구조라고 하며, 그 중 차수가 2개 이하로 구성되어 있는 트리구조를 이진 트리라고 한다. 이진 트리에는 왼쪽 자식노드의 주소와 오른쪽 자식노드의 주소를 저장하는 포인터가 노드에 생성되어 있으며, 검색하는 방식에 따라 전위 순회, 중위 순회, 후위 순회로 나뉜다.

typedef struct TreeNodeType {
	element data; //데이터 필드
	struct TreeNodeType* right; //오른쪽 서브트리
	struct TreeNodeType* left;  //왼쪽 서브트리
}treeNode;

 

이진 탐색 트리

 이진 트리중에서 아래의 조건을 만족하는 이진트리가 있다. 그리고 이러한 이진트리를 이진 탐색 트리라고 한다.

1. 모든 노드의 데이터 필드에는 서로 다른 유일한 데이터가 저장되어 있다.
2. 어떤 노드를 기준으로 왼쪽 서브트리의 노드의 모든 키 값(데이터 값)은 기준인 노드의 키 값 보다 작아야 한다.
3. 어떤 노드를 기준으로 오른쪽 서브트리의 노드의 모든 키 값(데이터 값)은 기준인 노드의 키 값 보다 커야 한다.
4. 왼쪽  서브 트리와 오른쪽 서브트리도 위의 조건을 만족 해야 한다.

 위의 그림은 이진검색트리의 예시로 키값이 "7"인 데이터를 보면 왼쪽 자식노드의 키 값이 "5,2,6"으로 "7"보다 낮으며, 오른쪽 자식노드의 키값이 "10, 9, 11"로 "7"보다 큰 것을 확인할 수 있다. 즉, 어떤 노드를 기준으로 왼쪽 트리의 모든 값은 전부 낮으며, 오른쪽 트리의 모든 값은 전부 큰 것을 확인 할 수 있다. 

 

이진 탐색 트리 알고리즘

 이진탐색트리는 왼쪽 자식노드는 부모노드보다 작은 키 값을 가져야 하며, 오른쪽 자식노드는 부모노드보다 큰 키 값을 가져야 한다. 그래서 이진 탐색 트리는 노드의 키 값에 따라 저장되는 위치가 정해져 있다.

 

• 트리 순회 방식

 일단 트리의 순회하는 방법을 결정해야 한다. 순회하는 방법에는 전위순회, 중위순회, 후위순회가 있으며, 전위순회는 부모노드 → 왼쪽 자식노드 → 오른쪽 자식노드, 중위순회는 왼쪽 자식노드 → 부모노드 → 오른쪽 자식노드, 후위순회는 왼쪽 자식노드  → 오른쪽 자식노드 → 부모노드순으로 순회한다. 이때, 이진탐색트리는 왼쪽 자식노드 → 부모노드 → 오른쪽 자식노드 순으로 낮은 키 값을 가지고 있기에 오름차순으로 정령하기 위해서는 중위순회를 사용한다.

void displayInorder(treeNode* root) {
	if (root) {
		displayInorder(root->left);
		printf("%c", root->data);
		displayInorder(root->right);
	}

 

• 데이터 삽입
  1. 기능
     • 트리의 현 위치에 어떠한 노드가 없을경우 : 새 노드생성후 데이터 삽입
     • 삽입하려는 데이터가 현 위치의 키값보다 작을경우 :
       1. 왼쪽 자식노드로 이동
       2. 왼쪽의 노드가 없을경우 : 새 노드 생성후 데이터 삽입
       3. 왼쪽의 노드가 있을경우 : 해당 노드에 있는 키 값과 비교 후, 위치변환 
     • 삽입하려는 데이터가 현위치의 키값보다 클 경우
       1. 오른쪽 자식노드로 이동
       2. 오른쪽의 노드가 없을경우 : 새 노드 생성후 데이터 삽입
       3. 오른쪽의 노드가 있을경우 : 해당 노드에 있는 키 값과 비교 후, 위치변환 
     • 삽입하려는 데이터가 있는 경우 : "같은 키가 존재!" 출력
  2. 함수의 자료형 : treeNode*
  3. 매개변수 : 사용할 트리의 루트노드, 저장할 데이터

알고리즘

1. 트리의 현 위치에 어떠한 노드가 없을경우(포인터 값 == NULL) :  노드생성후 데이터 삽입 2. 삽입하려는 데이터가 현 위치의 키값보다 작을경우( 새로운 데이터 값 < 저장된 데이터값)      1. 현 위치를 왼쪽 노드로 변경하고, 삽입 함수를 실행     2. 현 위치의 값은 변경이 되지 않기에, 리턴 값은 현 위치 노드의 주소로 설정 3. 삽입하려는 데이터가 현 위치의 키값보다 클 경우( 새로운 데이터 값 > 저장된 데이터값)      1. 현 위치를 오른쪽 노드로 변경하고, 삽입 함수를 실행     2. 현 위치의 값은 변경이 되지 않기에, 리턴 값은 현 위치 노드의 주소로 설정

treeNode* insertBSTNode(treeNode* p, element x) {
	treeNode* newNode;
	if (p == NULL) {									
		newNode = (treeNode*)malloc(sizeof(treeNode));
		newNode->data = x;
		newNode->left = NULL;
		newNode->right = NULL;
		return newNode;
	}
	else if (x < p->data) {								
   		p->left = insertBSTNode(p->left, x);			
    	return p;
	}
	else if (x > p->data) {								
    	p->right = insertBSTNode(p->right, x);			
    	return p;
	}
	else {
		printf("\n 같은 키가 존재! \n"); 
		return p;
	}


}

 

• 데이터 삭제
  1. 기능
     • 삭제할 데이터를 갖는 노드의 자식노드가 없는 경우
       • 삭제할 데이터를 갖는 노드가 루트노드가 아닐경우
         1. 부모노드의 왼쪽노드가 삭제할 데이터를 갖는 노드일 경우 : 부모노드의 왼쪽 자식노드 삭제
         2. 부모노드의 오른쪽노드가 삭제할 데이터를 갖는 노드일 경우 : 부모노드의 오른쪽 자식노드 삭제
       • 삭제할 데이터를 갖는 노드가 루트노드일 경우 : 루트노드 삭제
     • 삭제할 데이터를 갖는 노드의 하나의 자식노드가 있는경우
       • 삭제할 데이터를 갖는 노드가 루트노드가 아닐경우
         1. 부모노드의 왼쪽노드가 삭제할 데이터를 갖는 노드일 경우 : 부모노드의 왼쪽노드에 삭제할 데이터를 갖는 노드의 자식노드의 주소 저장
         2. 부모노드의 오른쪽노드가 삭제할 데이터를 갖는 노드일 경우 : 부모노드의 오른쪽노드에 삭제할 데이터를 갖는 노드의 자식노드의 주소 저장
       • 삭제할 데이터를 갖는 노드가 루트노드일 경우 : 루트노드 자리에 자식노드의 주소 저장
     • 삭제할 데이터를 갖는 노드의 두개의 자식노드가 있는경우
       1. 삭제할 데이터를 갖는 노드를 기준으로 왼쪽 서브트리에서 오른쪽 자식 노드가 없을 때 까지 오른쪽 자식노드로 이동
       2. 서브 트리의 루트 노드의 왼쪽 자식노드에  오른쪽 자식노드가 없는 경우 
          1. 이동노드의 왼쪽 자식노드의 주소를 이동 노드의 부모 노드의 왼쪽 자식 노드 포인터 변수에 저장
          2. 이동 노드의 데이터를 삭제할 데이터의 노드에 저장
       3. 서브 트리의 루트 노드의 왼쪽 자식노드에  오른쪽 자식노드가 있는 경우
          1. 이동노드의 왼쪽 자식노드의 주소를 이동 노드의 부모 노드의 오른쪽 자식 노드 포인터 변수에 저장
          2. 이동 노드의 데이터를 삭제할 데이터의 노드에 저장
  2. 함수의 자료형 : void
  3. 매개변수 : 삭제할 데이터, 삭제할 트리의 루트노드
  4. 필드 내에서 사용할 변수 : 자식 노드 주소 1개 저장할 포인터 변수(child) , 현 위치의 부모 노드(parent), 현 위치 노드(p), 이동 노드(succ), 이동한 노드의 부모노드(succ_parent)

삭제할 데이터를 갖는 노드의 자식노드가 없는 경우

삭제할  데이터를 갖는 노드의 하나의 자식노드가 있는경우

삭제할  데이터를 갖는 노드의 두개의 자식노드가 있는경우

알고리즘

1. 루트노드를 현 위치 노드에 저장, 현위치의 부모 노드를 NULL로 저장 2. 삭제 데이터와 맞는 노드를 현 위치 노드에 저장     - 삭제 데이터가 삭제할 데이터보다 작을경우, 왼쪽으로 이동     - 삭제 데이터가 삭제할 데이터보다 클 경우, 오른쪽으로 이동 3. 삭제할 노드의 자식노드의 수에 따라 노드 데이터 변경 3-1. 삭제할 노드의 자식노드가 없는 경우 1. 삭제할 노드가 루트노드가 아닐경우     1. 부모노드의 왼쪽노드가 현 위치 노드와 같은경우 : 부모 노드의 왼쪽 자식 노드 삭제     2. 부모노드의 오른쪽노드가 현 위치 노드와 같은경우 : 부모 노드의 오른쪽 자식 노드 삭제 2. 삭제할 노드가 루트노드일 경우 : 루트 노드 삭제 3-2 삭제할 노드의 자식노드가 1개 일 경우 1. 자식노드의 주소를 "child"에 저장 2. 삭제할 노드가 루트노드가 아닐경우     1. 부모노드의 왼쪽노드가 현 위치 노드와 같은경우 : 부모노드의 왼쪽노드에 child에 저장된 주소를 저장     2. 부모노드의 오른쪽노드가 현 위치 노드와 같은경우 : 부모노드의 오른쪽노드에 child에 저장된 주소를 저장 3. 삭제할 노드가 루트노드일 경우 : 루트 노드 삭제 3-3 삭제할 노드의 자식노드가 2개 일 경우 1. 이동한 노드의 부모노드에 현 위치 노드의 주소를 저장, 이동 노드에 현 위치의 왼쪽 자식 노드의 주소를 저장 2. 왼쪽 서브 트리에서 오른쪽 자식 노드가 없을 때 까지 오른쪽 자식노드로 이동  - 서브트리의 루트 노드가 오른쪽 자식노드를 가지고 있지 않은 경우, 해당 루트 노드의 왼쪽 자식 노드의 주소를 삭제할 데이터를 가진 노드의 왼쪽 노드에 저장   -서브트리의 루트 노드가 오른쪽 자식노드를 가지고 있는 경우, 이동한 부모 노드(succ_parent)의 오른쪽 포인터변수에 이동한 노드의 왼쪽 자식노드의 주소를 저장 4. 삭제할 노드의 데이터를 이동한 노드의 데이터로 변경 5. 이동한 노드의 메모리 주소 삭제

void deleteBSTNode(treeNode* root, element data) {
	treeNode* parent, * p, * succ, * succ_parent;	//부모노드, 현위치 노드, 임시 현위치, 임시 부모노드
	treeNode* child;	//자식노드

	parent = NULL;
	p = root;
	while ((p != NULL) && (p->data != data)) {		
		parent = p;
		if (data < p->data) {						
        p = p->left; 
		}
		else {										
        p = p->right;
		}
	}

	if (p == NULL) {
		printf("\n 찾는 키가 이진 트리에 없습니다!!");
		return;
	}
//0개
	if ((p->left == NULL) && (p->right == NULL)) {	
		if (parent != NULL) {						
			if (parent->left == p) {				
				parent->left = NULL;				
			}
			else {									
				parent->right = NULL;				
			}
		}
		else {
			root = NULL; 
		}
	}
//1개
	else if ((p->left == NULL) || (p->right == NULL)) { 
		if (p->left != NULL) {							
			child = p->left;							
		}
		else {											
			child = p->right;							
		}

		if (parent != NULL) {							
			if (parent->left == p) {					
				parent->left = child;					
			}
			else {									
				parent->right = child;					
			}
		}
		else {											
			root = child;								
		} 
	}
//2개
	else {												
		succ_parent = p;
		succ = p->left;									
		while (succ->right != NULL) {					
			succ_parent = succ;							
			succ = succ->right;
		}
		if (succ_parent->left == succ) {				
			succ_parent->left = succ->left;				
		}
		else { 
				succ_parent->right = succ->left;			
			}
		p->data = succ->data;							
        p = succ;										
	}
	free(p);
}

 

• 데이터 검색
  1. 기능
     • 출력하려는 데이터가 기존의 키값보다 작은경우 : 왼쪽으로 이동
     • 출력하려는 데이터가 기존의 키값보다 큰경우 : 오른쪽으로 이동
     • 출력하려는 데이터가 기존의 키값과 같은 경우 : 해당 위치를 결과값
     • 출력하려는 데이터가 없는 경우 : "찾는 키가 없습니다!" 출력
  2. 함수의 자료형 : treeNode*
  3. 매개변수 : 검색하려는 트리, 검색하려는 데이터
  4. 필드에서 사용하는 변수 : 현 위치 포인터 변수  

알고리즘

1. 현위치 포인터 변수에 루트 노드의 주소값 저장 2. 데이터간의 크기를 비교해서 해당 데이터가 저장되어 있는 노드로 이동후 출력     - 출력하려는 데이터가 기존의 키값보다 작은경우 : 왼쪽으로 이동     - 출력하려는 데이터가 기존의 키값과 같은 경우 : 해당 위치를 결과값     - 출력하려는 데이터가 기존의 키값보다 큰 경우(그 외) : 오른쪽으로 이동

treeNode* searchBST(treeNode* root, element x) {
	treeNode* p;
	p = root;
	while (p != NULL) {
		if (x < p->data) {								
			p = p->left;
		}
		else if (x == p->data) {						
			return p; 
		}
		else p = p->right;								
	}
	printf("\n 찾는 키가 없습니다!");
	return p;
}