[알고리즘] Tree

# 서론 

 

자료구조론에서 잘 못했던 트리를 다시 배운다. 중간고사까지는 거의 복습을 하는데 1학기 내용을 다 하니 좀 힘들지도...

 

후반부 부터는 하나도 모르는데 큰일났다...

 

교수님이 자료 구조 복습을 조금 시켜주셨다. 배열과 링크드 리스트라는 자료구조가 있다.

 

정렬된 배열의 경우에 삽입 삭제는 O(N)이 걸린다. 옮겨주어야 하기 때문이다.

바이너리 서치를 하면 탐색의 시간은 O(log(N))이 된다. 

 

정렬된 링크드 리스트 삽입 삭제는 그냥 O(1)이지만 탐색을 할 때는 헤드에서 넘어가야 해서 O(N)이다. 

 

때문에 서로 장단점이 있다. 이 때,  둘 다 괜찮게 나오는게 Tree이다. 

 

물론 상황에 맞게 사용해야겠지만 말이다. 

 

# Binary Search Tree

 

Graph G = (V, E)  이때 조건을 만족하면 트리라고 한다.

 

트리는 a connected acyclic undirected graph 이다. acyclic은 사이클(순환)이 없는 것이다. 

 

rooted tree < free tree < graph

 

rooted tree가 우리가 관심있는 자료구조이다. 

 

## Binary tree terminology 

 

가정, 키 값이 모두 다름.

 

왼쪽 자식, 오른쪽 자식, 부모, 후손, 조상 등등이 있음. c++로 구현할 때는 구조체로 만들고 저장하면 됨.

left child, right child, parent를 저장하고 후손, 조상은 계산하자. 

마지막에 있는 노드들을 리프노드라고 한다. 이때 자식에 NIL을 넣어준다.

 

## Binary Search Tree

 

노드 x의 모든 왼쪽 후손들은 x보다 작다. 

3, 4, 5, 8, 1, 7, 2 가 있으면 

 

루트가 5라고 한다면

왼쪽에는 3, 4, 1, 2 : 오른쪽에는 7, 8 

 

다시 왼쪽 트리 정렬 오른쪽 트리 정렬하면 됨.

예를 들어 왼쪽 3이 5의 왼쪽 자식이면 다시 왼쪽 1, 2 오른쪽 4가 됨. 

오른쪽 자식이 7이면 7의 오른쪽 자식은 8이 됨. 

 

더이상 남은 데이터가 없을 때 까지 이 작업을 반복해서 함. 근데 이게 모든 노드에서 만족해야 함!

 

Quick Sort와 비슷함. 이건 처음 알았네 ㄷㄷ... 

 

## 탐색은 어떻게 할까?

 

루트 노드에서 시작해서 작으면 왼쪽 크면 오른쪽으로 가자!

 

그러면 O(log(n))만큼의 시간이 걸릴 것이다. 삽입은 탐색하고 노드를 달아주기만 하면 되기 때문에 O(log(n))이 된다. 

 

그래서 둘 다 O(log(n))이라는 시간이 나오는 것이다. 

 

하지만 지울 떄가 문제이다. 리프 노드이면 그냥 지우면 된다. 

하지만 자식이 있는 경우가 문제이다. 자식이 하나면 지우고 자식을 올리면 된다. 

 

하지만 자식이 2이라면 조금 문제가 있다. 왼쪽 자식을 올릴까? 오른쪽 자식을 올릴까?

어떻게 해야 균형이 깨지지 않을까?

 

정답은 오른쪽 자식의 서브트리 중에서 가장 작은 값을 올리는 것이다. 그렇게 하면 깨지지 않는다. 

오른쪽에 있는 것을 모두 그 노드보다 크고 왼쪽은 그 노드보다 작다. 걔는 오른쪽 자식은 있을 수 있어도 왼쪽은 없다. 

왜냐고? 서브트리에서 가장 작으니까이다. 

 

## 코드

#include <iostream>
using namespace std;

struct node{
	int key;
    struct node *left, *right;
};

struct node *newNode(int item){
	struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

struct node *insert(struct node *node, int key) {
 if (node == NULL) return newNode(key);
 
 if (key < node->key)
 	node->left = insert(node->left, key);
 else
 	node->right = insert(node->right, key);
 return node;
}

struct node *search(struct node* node, int key) {
	if(node==NULL) return NULL;
    if(key == node->key) return node;
    else if(key<node->key) return search(node->left);
    else if(key>node->key) return search(node->right);
}

struct node *deleteNode(struct node *root, int key) {
	if (root==NULL) return root;
    if (key < root->key)
    	root->left = deleteNode(root->left, key);
    else if (key>root->key)
    	root->right = deleteNode(root->right, key);
    else {
    	if (root->left==NULL) {
        	struct node *temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
        	struct node *temp = root->left;
            free(root);
            return temp;
        }
        struct node *temp = minValueNode(root->right);
        root->key = temp->key;
        root->right = deleteNode(root->right, temp->key);
    }
    return root;
}

struct node *minValueNode(struct node *node) {
	struct node *current = node;
    while(current && current->left != NULL)
    	current = current->left;
    return current;
}

 

코드는 다음과 같다. 일단 탐색이다! 탐색의 시간 복잡도는 트리의 높이에 의존적인데 O(log(n))이다. 

 

하지만 몰려있으면? 최악의 상황이라면? 밸런스를 맞추어 주어야 할 것이다.

최악에서 탐색은 O(n)이다.......