[c언어] 트리의 종류

26 Dec 2023

c언어

트리는 계층적인 데이터를 표현하는 데 사용되는 자료 구조입니다. C언어에서는 다양한 종류의 트리를 다룰 수 있습니다. 이 게시물에서는 C언어에서 흔히 사용되는 트리의 종류에 대해 알아보겠습니다.

이진 트리

이진 트리는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 구조입니다. C언어에서는 다양한 방식으로 이진 트리를 구현할 수 있습니다. 이진 트리는 데이터를 계층적으로 저장하고 관리할 수 있는 강력한 자료 구조입니다.

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

이진 탐색 트리

이진 탐색 트리는 이진 트리의 한 종류로, 왼쪽 자식 노드는 부모 노드보다 작은 값이고 오른쪽 자식 노드는 부모 노드보다 큰 값을 가지는 특성을 갖습니다. C언어에서는 이진 탐색 트리를 활용하여 효율적인 데이터 검색 및 정렬 알고리즘을 구현할 수 있습니다.

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

AVL 트리

AVL 트리는 이진 탐색 트리의 변형으로, 균형을 유지하면서 데이터를 저장하는 자료 구조입니다. C언어에서는 AVL 트리를 활용하여 데이터의 삽입, 삭제 시에 자동으로 균형을 유지할 수 있습니다.

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
    int height;
};

레드-블랙 트리

레드-블랙 트리는 이진 탐색 트리의 다른 변형으로, 균형을 유지하면서 높은 성능을 제공하는 자료 구조입니다. C언어에서는 레드-블랙 트리를 사용하여 효율적인 데이터 삽입, 삭제, 검색 알고리즘을 구현할 수 있습니다.

enum Color { RED, BLACK };

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
    struct Node* parent;
    enum Color color;
};

위에서 소개된 트리의 종류들은 C언어에서 데이터를 효과적으로 저장, 관리, 검색하기 위한 다양한 옵션을 제공합니다. 각 트리의 특성을 이해하고 적절히 활용하여 프로그램을 작성할 수 있도록 노력해보세요.

목차

이진 트리

이진 탐색 트리

AVL 트리

레드-블랙 트리