[DATA STRUCTURE] 09. 트리(Tree)

아래는 C++로 구현된 이진 트리(Binary Tree)의 소스 코드다.
연결리스트처럼 노드 개념이 존재하고 자료의 계층 구조를 나타낼 때 사용하며
뿌리(root), 가지(branch), 잎(leaves) 등의 개념을 사용하여 데이터를 구성한다.
 

//Tree.h 내용
#pragma once
#include <iostream>
#include <queue>

struct Node {

	char data;
	Node* left;
	Node* right;

	Node(char d) :data(d),left(nullptr), right(nullptr){}
};

void preorder(Node* node) { //전위 순회

	if (node) {

		std::cout << node->data << ", ";
		preorder(node->left);
		preorder(node->right);
	}
}

void inorder(Node* node) { //중위 순회

	if (node) {
    
		inorder(node->left);
		std::cout << node->data << ", ";
		inorder(node->right);
	}
}

void postorder(Node* node) { //후위 순회

	if (node) {
    
		postorder(node->left);
		postorder(node->right);
		std::cout << node->data << ", ";
	}
}

void levelorder(Node* node) { //레벨 순서 순회

	std::queue<Node*> q;
	q.push(node);

	while (!q.empty()) {

		auto curr = q.front();
		q.pop();

		std::cout << curr->data << ", ";
	
		if (curr->left) {

			q.push(curr->left);
		}

		if (curr->right) {

			q.push(curr->right);
		}
	}
}

void delete_tree(Node* node) {

	if (node) {
    
		delete_tree(node->left);
		delete_tree(node->right);
		delete node;
	}
}

 

//main.cpp 내용
#include "tree.h"

int main() {

	Node* root = new Node('a');
	root->left = new Node('b');
	root->right = new Node('c');
	root->left->left = new Node('d');
	root->left->right = new Node('e');
	root->right->right = new Node('f');

	preorder(root);
	std::cout << std::endl;

	inorder(root);
	std::cout << std::endl;
	
	postorder(root);
	std::cout << std::endl;
	
	levelorder(root);
	std::cout << std::endl;

	delete_tree(root);
}

 

주요 특징

 
1. 노드(Node) : 트리의 기본 요소로, 데이터를 저장하는 데 사용되는 단일 요소이다.
노드는 뿌리 노드(Root Node), 부모 노드(Parent Node), 자식 노드(Child Node), 리프 노드(Leaf Node) 등
여러 유형으로 나눌 수 있다.
(상황에 따라 node라는 키워드 대신 vertex라는 키워드를 사용하기도 한다.)
 
2. 뿌리 노드(Root Node) : 트리의 시작점이며, 모든 다른 노드는 뿌리 노드로부터 직간접적으로 연결된다.
 
3. 부모 노드(Parent Node) : 어떤 노드의 바로 위에 연결된 노드를 가리킨다.
 
4. 자식 노드(Child Node) : 어떤 노드의 바로 아래에 연결된 노드를 가리킨다.
 
5. 리프 노드(Leaf Node) : 어떤 노드의 자식이 없는 노드를 말하며
리프 노드는 트리의 끝점에 위치하고 하위 노드를 가지지 않는다.
(상황에 따라 leaf라는 키워드 말고도 terminal 또는 external이라는 키워드를 사용하기도 한다.)
 
6. 엣지(Edge) : 트리에서 노드들을 연결하는 선을 가리킨다.
엣지는 노드 간의 관계를 나타내며, 각 노드는 하나의 뿌리 노드에 연결된 엣지를 따라 내려갈 수 있다.
(상황에 따라 edge라는 키워드 대신 link라는 키워드를 사용하기도 한다.)
 
 

장점

 
1. 계층적 구조 : 트리는 데이터를 계층적으로 구조화할 수 있는 이상적인 방법이다.
이러한 계층 구조는 많은 응용 프로그램에서 유용하며, 파일 시스템, XML 문서, HTML 문서와 같이
계층적 데이터를 표현하기에 적합하다.
 
2. 검색 속도 : 이진 탐색 트리(Binary Search Tree)와 같은 특수한 종류의 트리는 데이터를 빠르게 검색할 수 있는
자료 구조이며, 데이터가 정렬되어 저장되고 관리되므로 검색 시간이 O(log N)으로 제한된다.
 
3. 정렬된 데이터 : 이진 탐색 트리와 B-트리와 같은 트리 구조는 데이터를 정렬된 상태로 유지하므로
정렬된 데이터에 대한 작업이 효율적이다.
 
4. 데이터 삽입과 삭제 : 적절한 트리 구조를 사용하면 데이터의 삽입과 삭제를 효율적으로 수행할 수 있다.
특히, AVL 트리나 Red-Black 트리와 같은 균형 트리는 삽입과 삭제에 대한 균형을 유지하므로 최악의 상황에도
O(log N)의 성능을 제공한다.
 
 

단점

 
1. 메모리 사용 : 트리는 노드와 포인터를 사용하여 데이터를 저장하므로 메모리 사용이 상대적으로 높을 수 있으며
대규모 트리의 경우 메모리 사용이 문제가 될 수 있다.
 
2. 시간 복잡도 : 일부 트리 작업은 트리의 높이에 의존하며, 최악의 상황에는 선형 시간(O(n))이 걸릴 수 있다.
보통 이런 경우는 트리가 균형을 잃고 한쪽에만 데이터가 몰려 편향이 생기면 발생할 수 있다.
 
3. 삽입 및 삭제 복잡도 : 일반 이진 탐색 트리의 경우 삽입 및 삭제 연산의 성능은 트리의 균형에 크게 의존하며,
최악의 상황에는 트리가 편향될 수 있으며, 이에 따라 삽입 및 삭제 연산의 시간 복잡도가 O(n)이 될 수 있다.
 
4. 구현 복잡도 : 트리를 구현하고 유지하기 위해서는 트리 노드 관리, 균형 유지, 회전 작업 등과 같은
복잡한 알고리즘 및 데이터 구조를 구현해야 하므로 구현이 복잡할 수 있다.