[자료구조] 스레드 이진 트리 및 이진 탐색 트리 정리 및 구현

스레드 이진트리

목적 : 이진트리의 NULL 링크를 이용하여 순환 호출 없이도 트리의 노드들을 순회
용어
- 중위 선행자 : 중위 순회 시에 선행 노드
- 중위 후속자 : 중위 순회 시에 후속 노드
- 스레드(thread) : 실을 이용하여 노드들을 순회 순서대로 연결시켜 놓은 것
장점 : 순회를 빠르게 할 수 있음
단점 : 스레드를 설정하기 위해 삽입이나 삭제 함수가 더 많은 일을 해야 함
구성 방법
- NULL 링크에 중위 순회할 때 후속 노드(중위 후속자)를 저장시켜놓음
  → 이를 스레드 이진트리라고 함

스레드 이진트리 순회 구현

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct TreeNode{
    int data;
    struct TreeNode *left, *right;

    // 오른쪽 자식 링크가 NULL 인지 스레드인지 구분하기 위해 추가
    int is_thread; // 만약 오른쪽 링크가 스레드이면 1 아니면 0
}TreeNode;

TreeNode n1 = {'A',NULL,NULL,1};
TreeNode n2 = {'B',NULL,NULL,1};
TreeNode n3 = {'C',&n1,&n2,0};
TreeNode n4 = {'D',NULL,NULL,1};
TreeNode n5 = {'E',NULL,NULL,0};
TreeNode n6 = {'F',&n4,&n5,0};
TreeNode n7 = {'G',&n3,&n6,0};
TreeNode* test = &n7;

// 후속노드를 찾는 함수
TreeNode* find_successor(TreeNode* p){

    // q는 p의 오른쪽 포인터
    TreeNode* q = p -> right;
    // 오른쪽 포인터가 NULL이거나 스레드이면 오른쪽 포인터를 반환
    if(q == NULL || p -> is_thread == 1) return q;

    // 오른쪽 자식이라면 그 노드로 이동 후
    // 가장 왼쪽 노드로 이동
    while(q->left != NULL) q= q->left;
    return q;
}
// 중위 순회 스레드
void thread_inorder(TreeNode* t){
    TreeNode* q;

    q = t;
    while(q->left)q = q->left; // 가장 왼쪽 노드로 이동
    do{
        printf("%c -> ",q->data);
        q = find_successor(q);
    }while(q); // NULL이 아닐때까지 반복
}

int main(){
    //스레드 설정
    n1.right = &n3;
    n2.right = &n7;
    n4.right = &n6;

    thread_inorder(test);
}

<출력>

A -> C -> B -> G -> D -> F -> E ->

이진 탐색 트리

탐색 작업을 효율적으로 하기 위한 자료구조

이진 탐색 트리 정의

모든 원소의 키는 유일한 키를 가진다.
Key(왼쪽 서브 트리) < Key(루트 노드) < Key(오른쪽 서브트리)
왼쪽과 오른쪽 서브 트리도 이진 탐색 트리다.

탐색 연산

비교한 결과가 같으면 탐색이 성공
주어진 키 값이 루트 노드의 키 값보다 작으면
탐색은 이 루트 노드의 왼쪽 자식을 기준으로 다시 시작
주어진 키 값이 루트 노드의 키 값보다 크면
탐색은 이 루트 노드의 오른쪽 자식을 기준으로 다시 시작

search(x,k)
    if x = NULL
        then return NULL;=
    if k = x -> key
        then return x
    else if k > x -> key
        then return search(x->right,k)
    else return search(x->left,k)

삽입 연산

먼저 탐색을 수행하는 것이 필요
탐색에 실패한 위치가 바로 새로운 노드를 삽입하는 위치

insert_node(root,z)

p <- NULL
t <- root
while t != NULL do
p <- t
if(z -> key < p -> key)
    then t <- p -> lef
    else t <- p -> right

if p = NULL
    then root <- z; // 트리가 비어있을 때
    else if(z -> key < p -> key)
        then p -> left <- z
        else p -> right <- z

삭제 연산

삭제 노드가 단말 노드일 경우

단말 노드의 부모 노드를 찾아 연결을 끊음

삭제 노드가 왼쪽/오른쪽 중 하나의 서브 트리만 가지고 있을 경우
삭제 노드가 서브트리 하나만 가질 경우
- 서브 트리를 부모 노드에 붙여주고 그 노드는 삭제
삭제 노드가 두 개의 서브 트리를 가지고 있는 경우
- 삭제 노드와 가장 비슷한 값을 가진 노드를 삭제노드 위치로 가져옴

이진 탐색 트리 구현

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct TreeNode{
    int key;
    struct TreeNode *left, *right;

    // 오른쪽 자식 링크가 NULL 인지 스레드인지 구분하기 위해 추가
    int is_thread; // 만약 오른쪽 링크가 스레드이면 1 아니면 0
}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;
}

// 새로운 key 노드 추가
TreeNode* insert_node(TreeNode* node, int key){
    // 노드가 없다면 new_node()로 새로운 이진 노드 생성
    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;
}

// root 서브트리에서 지정한 key 노드를 삭제하는 함수 
TreeNode* delete_node(TreeNode* root, int key){
    if(root == NULL) return root;

    if(key < root -> key) delete_node(root -> left,key); // 루트 왼쪽
    else if(key > root -> key) delete_node(root -> right,key); // 루트 오른쪽
    else{
        // 서브트리가 0개 또는 1개인 경우
        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;
        }

        // 서브트리가 2개인 경우

        // 루트 오른쪽 링크로 이동해 min_value_node로 해당 서브트리에서 가장 작은 노드로 이동
        // 해당 노드는 삭제할 key 값과 가장 가까운 key를 가진 노드
        TreeNode* temp = min_value_node(root->right);
        root -> key = temp -> key; // 삭제할 노드 자리의 키 값을 temp 키 값으로 변경

        // temp 노드를 위로 올렸으므로 root->right 서브트리에서 temp 키를 삭제한다.
        root -> right = delete_node(root->right,temp->key); 
    }
    return root;
}
void inorder(TreeNode* root){
    if(root){
        inorder(root -> left);
        printf("[%d] ",root->key);
        inorder(root -> right);
    }
}
int main(){
    TreeNode* root = NULL;
    TreeNode* tmp = NU

<출력>

이진 탐색 트리 중위 순회 결과
[10] [20] [30] [40] [50] [60] 

이진 탐색 트리에서 30을 발견

이진 탐색 트리의 성능

이진 탐색 트리에서 탐색, 삽입, 삭제 연산의 시간 복잡도 → 트리의 높이에 비례
최선의 경우
- 이진트리가 균형적으로 생성되어 있는 경우
- h(트리의 높이) = log_2n 초
최악의 경우
- 한쪽으로 치우진 경사 이진트리의 경우
- h = n → 순차 탐색과 시간 복잡도가 같다.

균형 이진 탐색 트리

이진 탐색과 이진 탐색 트리의 차이
- 이진 탐색(binary search)
  - 자료들이 배열에 저장되어 있으므로 삽입과 삭제에 부담이 큼
    ← 자료를 삽입하거나 삭제 시 앞뒤의 원소들을 이동
- 이진 탐색 트리(binary search tree)
  - 이진트리로 구성
  - 비교적 빠른 시간 안에 삽입과 삭제를 끝마칠 수 있는 구조
시간 복잡도
- 균형 트리 : O(logn)
- 불균형 트리 : O(n)

추가 구현

이진트리가 균형 트리인지 판단

균형 트리 : 이진트리의 서브 트리 높이가 최대 1 차이가 나는 트리

typedef struct TreeNode{
    int data;
    struct TreeNode *left, *right;
}TreeNode;

// 노드 높이 측정
int get_height(TreeNode *node){
    int height = 0;
    if(node != NULL){
        int lHeight = get_height(node -> left);
        int rHeight = get_height(node -> right);
        height = (lHeight >= rHeight)? 1+lHeight : 1+rHeight;
    }
    return height;
}

void isBalanced(TreeNode *node, int cnt, int height){
    if(node != NULL){
        isBalanced(node -> left, cnt+1,height);
        isBalanced(node -> right, cnt+1,height);
    }
    else {
        if(height - cnt > 1) {
            printf("이진트리가 아님");
            exit(1);
        }
    }
}

TreeNode n9 = {13,NULL,NULL};
TreeNode n8 = {13,&n9,NULL};
TreeNode n1 = {1,NULL,NULL};
TreeNode n2 = {4,&n1,NULL};
TreeNode n3 = {16,NULL,NULL};
TreeNode n4 = {25,&n8,NULL};
TreeNode n5 = {20,&n3,&n4};
TreeNode n6 = {15,&n2,&n5};
TreeNode* root = &n6;

int main() {
    int height = get_height(root);
    isBalanced(root,1,height);

    printf("이진트리입니다");
}

<출력>

이진트리가 아님

이진 트리 모든 노드의 합 구하기

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode{
    int data;
    struct TreeNode *left, *right;
}TreeNode;

TreeNode n1 = {1,NULL,NULL};
TreeNode n2 = {4,&n1,NULL};
TreeNode n3 = {16,NULL,NULL};
TreeNode n4 = {25,NULL,NULL};
TreeNode n5 = {20,&n3,&n4};
TreeNode n6 = {15,&n2,&n5};
TreeNode* root = &n6;

int get_total(TreeNode* node){
    int total = 0;
    if(node != NULL){
        total = node -> data + get_total(node -> left) + get_total(node -> right);
    }
    return total;
}

int main(){
    printf("모든 노드의 합 = %d",get_total(root));
}

<출력>

모든 노드의 합 = 81

이진트리에서 자식이 하나만 있는 노드 개수 구하기

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode{
    int data;
    struct TreeNode *left, *right;
}TreeNode;

TreeNode n1 = {1,NULL,NULL};
TreeNode n2 = {4,&n1,NULL};
TreeNode n3 = {16,NULL,NULL};
TreeNode n5 = {20,&n3,NULL};
TreeNode n6 = {15,&n2,&n5};
TreeNode* root = &n6;

int checkOne(TreeNode* node){
    int count = 0;
    if(node != NULL){
        if((node -> left != NULL && node -> right != NULL)
        ||(node -> left == NULL && node -> right == NULL))
        count = checkOne(node -> left) + checkOne(node -> right);

        else if(node -> left != NULL || node -> right != NULL)
        count = 1 + checkOne(node -> left) + checkOne(node -> right);
    }
    return count;
}

int main(){
    int n;
    printf("%d",checkOne(root));
}

<출력>

저작자표시 변경금지

Today :

스레드 이진트리

스레드 이진트리 순회 구현

이진 탐색 트리

이진 탐색 트리 정의

탐색 연산

삽입 연산

삭제 연산

이진 탐색 트리 구현

이진 탐색 트리의 성능

균형 이진 탐색 트리

추가 구현

이진트리가 균형 트리인지 판단

이진 트리 모든 노드의 합 구하기

이진트리에서 자식이 하나만 있는 노드 개수 구하기

티스토리툴바

스레드 이진트리

스레드 이진트리 순회 구현

이진 탐색 트리

이진 탐색 트리 정의

탐색 연산

삽입 연산

삭제 연산

이진 탐색 트리 구현

이진 탐색 트리의 성능

균형 이진 탐색 트리

추가 구현

이진트리가 균형 트리인지 판단

이진 트리 모든 노드의 합 구하기

이진트리에서 자식이 하나만 있는 노드 개수 구하기

검색 태그

티스토리툴바