[자료구조] #14 Tree(1)

• Tree

 

트리는 계층적인 구조를 나타낼 수 있는 자료구조이다.

부모-자식 관계의 노드들로 이루어져 있다.

 

• 트리의 용어

 

노드(node) : 트리의 구성요소

루트(root) 노드 :  제일 상단에 있는 노드(부모가 없는 노드)

간선(link, edge) : 노드와 노드를 연결하는 선

서브트리(subtree) : 하나의 노드와 자손들로 이루어짐

 

단말노드(terminal, leaf, external) : 자식이 없는 노드

비단말노드(brach, internal) : 자식을 가지는 노드

 

자식, 부모, 형제, 조상 노드

특정 노드를 기준으로 가족 관계를 따진다.

 

노드의 차수(degree) : 노드의 자식 노드 수

노드의 깊이(depth) : 루트 노드에서 특정 노드까지의 간선의 수

노드의 레벨(level) : 트리의 계층 번호로 depth + 1

 

노드의 높이(height) : 특정 노드에서 가장 깊은 리프까지의 간선의 수

트리의 높이 = 루트의 높이

 

빈 트리의 높이는 구현의 편의성을 위해 -1로 정의한다.

 

• 일반적인 트리

 

특정 노드가 임의의 개수 만큼 자식 노드를 가질 수 있다.

 

• 이진 트리(Binary Tree)

 

모든 노드가 최대 2개의 서브트리를 가질 수 있는 트리이다.(모든 노드 차수가 2 이하)

이진 트리의 각 서브 트리는 재귀적으로 이진 트리이다.

 

• 이진 트리의 종류

 

포화 이진 트리(full binary tree)

트리의 각 레벨에 노드가 꽉 차있는 이진 트리이다.

 

완전 이진 트리(complete binary tree)

레벨이 l일때 레벨 1부터 l-1까지는 노드가 모두 채워진다.

마지막 레벨 l에서는 노드가 왼쪽에서 오른쪽으로 순서대로 채워진다.

 

마지막 층에는 값이 다 채워지지 않아도 괜찮다.

 

Degenerate (binary) tree

노드가 n개 있을 때 높이가 n-1인 트리이다.

 

실질적으로 트리가 아니라 리스트의 모양이기 때문에 트리의 이점을 살리지 못한다.

 

• 이진 트리의 성질

 

노드의 개수가 n개라고 하면 간선의 개수는 n-1이다.

(루트 노드에서는 간선이 들어올 가능성이 없기 때문)

노드의 개수가 9개이므로 간선의 수는 8개이다.

 

이진 트리의 높이를 h라고 했을 때, 노드 수의 범위는?

 

Degenerate tree일 때 최소로 h+1개의 노드를 가진다.

Full binary tree일 때 최대로 2^h+1 - 1개의 노드를 가진다.

 

그럼 반대로 이진 트리에 n개의 노드가 있을 때, 높이의 범위는?

 

Degenerate tree일 때 최대로 n-1의 높이를 가진다.

Complete binary tree일 때 최소로 h = [log₂(n+1) - 1]의 높이를 가진다.

 

 

• 이진 트리의 표현

 

배열 표현

각 노드에 번호를 붙여서 그 번호를 배열의 인덱스로 삼아 노드의 데이터를 배열에 저장한다.

 

노드 i의 부모 노드 인덱스 : [i/2]

노드 i의 왼쪽 자식 노드 인덱스 : 2i

노드 i의 오른쪽 자식 노드 인덱스 : 2i + 1

 

링크 표현법

포인터를 이용하여 부모 노드가 자식 노드를 가리키게 하는 방법이다.

 

• 이진 트리의 표현 장단점

 

배열 표현

장점 : 배열 사용 및 단순 인덱스 계산으로 트리를 쉽고 간결하게 구현할 수 있다.

단점 : 배열 크기 이상으로 트리를 구성할 수 없으며 트리에 노드가 몇 개 없는 경우 사용하지 않는 공간 낭비가 있다.

 

링크 표현

장점 : 입력할 수 있는 노드 수의 제한 없이 노드를 추가할 수 있으며 사용하지 않는 공간 낭비가 없다.(필요한 만큼 할당해서 사용)

단점 : 노드 별로 2개의 포인터에 대해 추가적인 메모리가 사용되며 동적 할당에 따른 비용이 발생한다.

 

결국 두 표현 모두 trade off가 존재하게 된다!

 

• 이진 트리의 구현

 

BinaryTree Class

int data를 저장하는 BinaryNode로 구성된 이진 트리

// 이진 트리의 노드를 나타내는 클래스 정의
class BinaryNode{
private:
    int data; // 노드가 저장하는 데이터
    BinaryNode* left; // 왼쪽 자식 노드
    BinaryNode* right; // 오른쪽 자식 노드
public:
    // 생성자: 데이터와 왼쪽, 오른쪽 자식 노드를 설정
    BinaryNode(int data = 0, BinaryNode* left = nullptr, BinaryNode* right = nullptr){
        this->data = data;
        this->left = left;
        this->right = right;
    }
    // 데이터 설정 메서드
    void setData(int data){ this->data = data; }
    // 데이터 반환 메서드
    int getData(){ return this->data; }
    // 왼쪽 자식 노드 설정 메서드
    void setLeft(BinaryNode* left) { this->left = left; }
    // 왼쪽 자식 노드 반환 메서드
    BinaryNode* getLeft(){ return this->left; }
    // 오른쪽 자식 노드 설정 메서드
    void setRight(BinaryNode* right) { this->right = right; }
    // 오른쪽 자식 노드 반환 메서드
    BinaryNode* getRight(){ return this->right; }
    // 리프 노드(자식 노드가 없는 노드)인지 확인하는 메서드
    bool isLeaf(){
        return this->left == nullptr && this->right == nullptr;
    }
};

// 이진 트리를 나타내는 클래스 정의
class BinaryTree{
private:
    BinaryNode* root; // 트리의 루트 노드
public:
    // 생성자: 루트 노드를 nullptr로 초기화
    BinaryTree(){ this->root = nullptr; }
    // 트리가 비어있는지 확인하는 메서드
    bool empty(){ return this->root == nullptr; }
    // 루트 노드 설정 메서드
    void setRoot(BinaryNode* node) { this->root = node; }
    // 루트 노드 반환 메서드
    BinaryNode* getRoot(){ return this->root; }
};

int main() {
    BinaryTree tree; // 이진 트리 객체 생성
    // 각각의 노드 생성
    BinaryNode *d = new BinaryNode('D', nullptr, nullptr); // 데이터 'D'를 가진 리프 노드
    BinaryNode *e = new BinaryNode('E', nullptr, nullptr); // 데이터 'E'를 가진 리프 노드
    BinaryNode *b = new BinaryNode('B', d, e); // 데이터 'B'를 가진 노드로, 왼쪽 자식은 d, 오른쪽 자식은 e
    BinaryNode *f = new BinaryNode('F', nullptr, nullptr); // 데이터 'F'를 가진 리프 노드
    BinaryNode *c = new BinaryNode('C', f, nullptr); // 데이터 'C'를 가진 노드로, 왼쪽 자식은 f
    BinaryNode *a = new BinaryNode('A', b, c ); // 데이터 'A'를 가진 노드로, 왼쪽 자식은 b, 오른쪽 자식은 c
    tree.setRoot(a); // 트리의 루트 노드를 a로 설정
    return 0;
}