이진탐색트리

이진트리 탐색 시에 원활하게 하는 방식이 더 있는데

root를 기준으로 왼쪽은 root보다 작은 값들을, 오른쪽은 root보다 큰 값들이 오게 하는 것이다.

 

그래서 찾는 값을 봤을 때 root보다 크면 오른쪽에서 작으면 왼쪽에서만 찾게되어 더 빠르게 찾을 수 있게 된다.

 

function binarySearch(int n)
{
	node_t node = binarySearch.root; // root를 가져온다
    while(node != NULL && node.data != n){
    	if(node.data > n) node = node.left;
        else node = node.right;
    }
    if(node == NULL) fprintf(stderr, "error");
    return node;
}

 

 

이진탐색트리 삽입

 

삽입 시에도 이런 규칙을 지켜야하기 때문에

case를 나누어서 삽입을 하게 된다. 

 

1. 트리에 노드가 전혀 없는 경우 -> 부모 노드가 null 이므로 이진탐색트리의 root를 node(x) 즉, 넣으려는 노드로 한다.
2. 트리에 노드가 있지만 부모에 적혀있는 노드 값보다 삽입하려는 값이 큰 경우 -> 부모노드의 오른쪽으로 가줘야한다.
3. 트리에 노드가 있지만 부모에 적혀있는 노드 값보다 삽입하려는 값이 작은 경우 -> 부모노드의 왼쪽으로 가줘야한다.

이 방식을 탐색 노드가 null이 나올때까지 간 후에 null이 나오게 되면 삽입한다.

void binaryTreeInsert(node_t n)
{
    node_t node = binarySearch.root; // 탐색 노드
    node_t parent = binarySearch.root; // 값을 비교할 부모 노드

    while(node != NULL){
        parent = node;
        if(parent.data > n.data){
            node = node.left;
        } else {
            node = node.right;
        }
    }

    if(parent == NULL){
        binarySearch.root = n;
    } else if(parent.data > n.data){
        parent.left = n;
    } else {
        parent.right = n;
    }
}

이진탐색트리의 삭제

 

• 값을 찾았을 때 어떻게 처리해줘야하는지가 관건이다.
• 값을 찾았을 때, 왼쪽 노드가 비어있다면 오른쪽 노드를 위로 올려준다.
• 값을 찾았을 때, 오른쪽 노드가 비어있다면 왼쪽 노드를 위로 올려준다.
• 값을 찾았을 때, 왼쪽 오른쪽 모두 차 있다면 -> successor를 찾아주어야 한다. successor은 현재 노드 기준으로 더 크면서 가장 작은 값이다. 찾은 값이 지워질 것이기 때문에 이진탐색트리 successor은 이진탐색트리 규칙에 맞게 해당 자리에 들어 갔어도 왼쪽 값보다는 크고 오른쪽 값보다는 작아야한다.

node_t BinarySearch(int n)
{
    node_t node = binarySearchTree.root;
    while(node != NULL && node.data != n){
        if(node.data > n){
            node = node.left;
        } else {
            node = node.right;
        }
    }
    return node;
}
node_t binarySearchTreeMinimum(node_t tree)
{
    node_t node = tree;
    while(node.left != NULL){
        node = node.left;
    }
    return node;
}
node_t delete(node_t n)
{
    note_t node = BinarySearch(n.data);
    if(node.left == NULL){
        node = node.right;
    } else if(node.right == NULL){
        node = node.left;
    } else {
        node_t successor = binarySearchTreeMinimum(node.right);
        if(node.right == successor){
            node = successor;
        } else {
            node.data = successor.data;
            successor = successor.right; // successor 은 오른쪽 노드에서 가장 작은 값이므로 왼쪽 자식이 없다
        }
    }