이론공부/자료구조
자료구조 공부 #18 (트리연산)
한반가
2021. 5. 19. 15:59
2021.05.16 - [이론공부/자료구조] - 자료구조 공부 #13 (트리순회)
이진트리 노드 갯수 연산
- 탐색 트리안의 노드의 개수를 계산
- 각각의 서브트리에 대하여 순환 호출만 한다음, 반환되는 값에 1을 더하여 반환
int get_node_count(TreeNode* node){
int cout = 0;
if (node != NULL)
count = 1 + get_node_count(node->left) + get_node_count(node->right);
return count;
}
이진 트리 높이 연산
- 서브 트리에 대하여 순환 호출하고 서브트리들의 반환값 중에서 최대값을 구하여 반환
int get_height(TreeNode* node){
int height = 0;
if (node != NULL)
height = 1 + max(get_height(node->left), get_height(node->right));
return height;
}
이진 트리 단말노드 갯수 연산
int get_leaf_count(TreeNode* node){
int count = 0;
if (node != NULL){
if (node->left == NULL && node->right == NULL)
return 1;
else
count = get_leaf_count(node->left) + get_leaf_count(node->right);
}
return count;
}
스레드 이진 트리
- 이진 트리의 NULL 링크를 이용하여 순환 호출 엇이도 트리의 노드들을 순회
- NULL 링크에 중위 순회 시에 후속 노드인 중위 후속자를 저장시켜 놓은 트리가 스레드 이진 트리
스레드 이진 트리 구현
- 단말노드와 비단말노드의 구별을 위해 is_thread 필드 구현
typedef struct TreeNode{
int data;
struct TreeNode*left, * right;
int is_thread;
}TreeNode;
- 중위 후속자를 찾는 함수 구현
TreeNode* find_successor(TreeNode* p){
TreeNode q = p->right;
if(q==NULL || p->is_thread == true)
return q;
while(p->left != NULL) q= q->left;
return q;
}
이진탐색 트리
- 탐색 작업 효율적으로 하기 위한 구조
- 왼쪽 key ≤ 루트 key ≤ 오른쪽 key
- 이진 탐색을 중위순회하면 오름차순으로 정렬된 값을 얻을 수 있음
탐색 연산
- 비교한 결과 같으면 탐색 성공
- 비교한 결과가 주어진 키 값이 루트 노드의 키값 보다 작으면 탐색을 왼쪽 서브트리 기준으로 다시시작
- 비교한 결과가 주어진 키 값이 루트 노드의 키값 보다 크면 탐색을 오른쪽 서브트리 기준으로 다시시작
- 순환으로 탐색 구현
TreeNode* search(TreeNode* node, int key){
if(node == NULL) return NULL;
if(key ==node->key) return node;
else if(key < node->key)
return search(node->left,key);
else
return search(node->right,key);
}
- 반복으로 탐색 구현
TreeNode* search(TreeNode* node, int key){
while(node != NULL){
if(key == node->key) return node;
else if(key < node->key)
node = node->left;
else
node = node->right;
}
return NULL;
}
이진 탐색트리 삽입 연산
- 이진탐색 트리에 원소를 삽입하기 위해서 탐색을 먼저 수행
- 탐색에 실패한 위치가 바로 노드 삽입하는 위치
C 구현 코드
TreeNode *insert_node(TreeNode* node, int key){
if(node == NULL) return new_node(key);
if(key < node->key)
node->left = insert_node(node->left, key);
else if (key > node->key)
node->right = insert_node(node->right, key);
return node;
}
TreeNode *new_node(int item){
TreeNode* temp = (TreeNode*)malloc(sizeof(TreeNode));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
이진탐색 트리 삭제연산
- 3가지 경우
- 삭제하는 노드가 단말 노드인 경우
- 삭제하는 노드가 하나의 왼쪽이나 오른쪽 서브트리중 하나만 가지고 있는 경우
- 삭제하는 노드가 두개의 서브 트리 모두 가지고 있는 경우
TreeNode* delete_node(TreeNode* root, int key){
if (root == NULL) return NULL;
if(key < root->key)
root->left = delete_node(root->left,key);
else if (key > root-key)
root->right = delete_node(root->right,key);
else{
//1 and 2
if(root->left == NULL){
TreeNode* temp = root->right;
free(root);
return temp;
} else if(root->right == NULL){
TreeNode* temp = root ->left;
free(root);
return temp;
}
//3
Treenode* temp = min_value_node(root->right);
root->key = temp->key;
root->right = delete_node(root->right,temp->key);
}
return root;
}
트리연산 전체 C 구현코드
더보기
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int key;
struct TreeNode* left, * right;
}TreeNode;
TreeNode* search(TreeNode* node, int key) {
if (node == NULL) return NULL;
if (key == node->key) return node;
else if (key < node->key)
return search(node->left, key);
else
return search(node->right, key);
}
TreeNode* new_node(int item) {
TreeNode* temp = (TreeNode*)malloc(sizeof(TreeNode));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
TreeNode* insert_node(TreeNode* node, int key) {
if (node == NULL) return new_node(key);
if (key < node->key)
node->left = insert_node(node->left, key);
else if (key > node->key)
node->right = insert_node(node->right, key);
return node;
}
TreeNode* min_value_node(TreeNode* node) {
TreeNode* current = node;
while (current->left != NULL)
current = current->left;
return current;
}
TreeNode* delete_node(TreeNode* root, int key) {
if (root == NULL) return NULL;
if (key < root->key)
root->left = delete_node(root->left, key);
else if (key > root -> key)
root->right = delete_node(root->right, key);
else {
//1 and 2
if (root->left == NULL) {
TreeNode* temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL) {
TreeNode* temp = root->left;
free(root);
return temp;
}
//3
TreeNode* temp = min_value_node(root->right);
root->key = temp->key;
root->right = delete_node(root->right, temp->key);
}
return root;
}
//중위순회
//LVR
void inorder(TreeNode* root) {
if (root) {
inorder(root->left);
printf("[%d]", root->key);
inorder(root->right);
}
}
//전위 순회
//VLR
void preorder(TreeNode* root) {
if (root) {
printf("[%d]", root->key);
preorder(root->left);
preorder(root->right);
}
}
// 후위 순회
//LRV
void postorder(TreeNode* root) {
if (root) {
postorder(root->left);
postorder(root->right);
printf("[%d]", root->key);
}
}
int main(void) {
TreeNode* root = NULL;
TreeNode* tmp = NULL;
root = insert_node(root, 30);
root = insert_node(root, 20);
root = insert_node(root, 10);
root = insert_node(root, 40);
root = insert_node(root, 50);
root = insert_node(root, 60);
printf("이진 탐색 트리 중위 순회 결과 \n");
inorder(root);
printf("\n\n");
if (search(root, 30) != NULL)
printf("이진 탐색 트리에서 30을 발견함\n");
else
printf("이진 탐색 트리에서 30을 발견못함\n");
printf("\n\n");
delete_node(root, 40);
printf("이진 탐색 트리에서 40을 삭제\n");
printf("이진 탐색 트리 중위 순회 결과 \n");
inorder(root);
printf("\n\n");
if (search(root, 40) != NULL)
printf("이진 탐색 트리에서 40을 발견함\n");
else
printf("이진 탐색 트리에서 40을 발견못함\n");
printf("\n\n");
root = insert_node(root, 39);
printf("이진 탐색 트리에서 39을 삽입\n");
printf("이진 탐색 트리 중위 순회 결과 \n");
inorder(root);
printf("\n\n");
return 0;
}이진 트리 성능 분석
- 이진 탐색 트리에서 탐색, 삽입, 삭제, 연산의 시간 복잡도는 트리의 높이를 h 라고 했을때 h에 비례함
2021.05.04 - [이론공부/화일처리및응용] - 화일 처리 및 응용 공부 #12 (탐색 트리)
화일 처리 및 응용에서도 다룬 내용이니 참고하자
탐색트리의 연산 알고리즘, 구현코드를 살펴보자, 복잡도의 비례관계도 알아두자