Binary Search Tree

이진 탐색 트리란 정렬된 이진트리로써 다음과 같은 속성이 있다. 노드의 왼쪽 하위 트리에는 노드의 키보다 작은 키가 있는 노드만 포함된다. 노드의 오른쪽 하위 트리에는 노드의 키보다 큰 키가 있는 노드만 포함된다. 그리고 왼쪽 및 오른쪽 하위 트리도 각각 이진 검색 트리여야 한다. 또한 중복된 키를 허용하지 않는다. 이러한 이진 탐색 트리의 특성때문에 효율적인 검색이 가능하다.

 

검색

이진 탐색 트리에서 검색은 특정 요소의 위치를 찾는 것이다. 과정은 먼저 루트에서 시작하여, 검색 값을 루트와 비교하여 루트보다 작으면 왼쪽에 대해 재귀하고 크면 오른쪽으로 재귀한다. 일치하는 값을 찾을때까지 절차를 반복한다. 검색 값이 없으면 null을 반환한다.

 

이를 구현하면 다음과 같다.

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

 

즉, key가 현재 노드가 가리키는 값보다 작으면 왼쪽 서브트리로 재귀하고, 값보다 크면 오른쪽 서브트리로 재귀한다.

 

삽입

이진 검색트리에 데이터를 삽입하는 작업은 중복은 불가하며, 항상 리프 노드에 삽입된다.

 

삽입 과정은 다음과 같다. 먼저 root에서 시작하고, 삽입 값을 루트와 비교한다. 루트보다 작으면 왼쪽으로 재귀하고, 크다면 오른쪽으로 재귀한다. leaf 노드에 도달한 후에는 노드보다 크면 오른쪽에 삽입하고, 작다면 왼쪽에 삽입한다.

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

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

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

 

삭제

이진 트리에서 특정 노드를 삭제하는 경우에는 3가지 경우의 수가 있다. 먼저 삭제할 노드가 leaf 노드인 경우에는 노드를 삭제하기만 하면 된다. 두 번째로 삭제할 노드에 자식이 하나만 있는 경우에는 노드를 삭제하고 자식 노드를 삭제된 노드의 부모에 직접 연결하기만 하면 된다. 세 번째는 삭제할 노드에 자식이 둘 있는 경우인데, 이때는 successor 노드를 찾는 과정이 추가된다. 여기서 successor 노드란 right subtree에 최소값. 즉, inorder 순회에서 다음 노드를 말한다. 즉, 삭제 과정은 다음과 같다.

1. 삭제할 노드를 찾는다.
2. 삭제할 노드의 successor 노드를 찾는다.
3. 삭제할 노드와 successor 노드의 값을 바꾼다.
4. successor 노드를 삭제한다.

이러한 과정을 구현하면 다음과 같다.

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

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

struct node *deleteNode (struct node *root, int key) {
	if (root == NULL) {
    	return root;
    }
    
    if (key < root->data) {
    	root->left = deleteNode(root->left, key);
    } else if (key > root->data) {
    	root->right = deleteNode(root->right, key);
    } else { // 삭제할 노드가 있는 경우
    	struct node *temp;
        
        // 노드에 자식이 하나이거나 없는 경우
        if (root->left == NULL) {
        	temp = root -> right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
        	temp = root -> left;
            free(root);
            return temp;
        }
        
        // 노드에 자식이 둘 있는 경우, successor 노드를 찾아서 삭제할 노드 키와 바꾼 후 삭제한다.
        temp = minValueNode(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

 

 

인용

https://yoongrammer.tistory.com/71

[자료구조] 이진 탐색 트리 (BST, Binary Search Tree)