트리
트리는 스택, 큐 등의 선형적인 자료구조가 아니라, 계층적인 구조의 자료구조이다. 컴퓨터의 폴더 구조, 가계도, 회사의 조직도 등 계층적인 관계들을 표현한 자료구조이다.
이 외에도 인공지능에서 사용되는 결정 트리도 트리라고 할 수 있겠다. 트리는 위의 그림과 같이, 1개 이상의 노드로 이루어져 있다.
트리 용어
노드(Node) : 트리를 구성하는 요소들로 그림에서 A, B, C, D, E, F, G, H, I 를 말한다.
루트(Root) 노드 : 트리에서 가장 높은 곳에 있는 노드. 위 그림에서 A가 루트 노드이다.
서브 트리(Subtree) : 루트 노드에서 갈라져 나온 트리.
간선(Edge) : 루트와 서브트리 사이에 연결된 선.
부모 노드(Parent node) : 자식 노드와 직접 연결된 상위 노드. D의 부모 노드는 B, C의 부모 노드는 A이다.
자식 노드(Child node) : 부모 노드와는 반대. D는 B의 자식 노드이다.
단말 노드(Leaf node 또는 Terminal node) : 자식 노드가 없는 노드.
비단말 노드(Nonterminal node) : 단말 노드가 아닌 노드.
차수(Defree) : 한 노드가 가지고 있는 자식 노드의 수. A의 차수는 2이고, C의 차수는 3이다.
트리의 차수 : 트리에서 가장 큰 차수. C의 차수가 3으로 가장 크므로 트리의 차수는 3이다.
레벨(Level) : 트리의 층. 루트의 레벨부터 하나씩 증가해 나간다.
높이(Height) : 트리의 최고 레벨. 층이 총 4층으로 트리의 높이는 4이다.
이진 트리(Binary Tree)
자식 노드의 수가 항상 2개 이하인 트리를 이진 트리라고 한다. 모든 노드는 차수가 2를 넘을 수 없으며, 서브 트리들도 모두 이진 트리여야한다. 이때, 서브 트리가 공집합이어도 된다.
이진 트리는 다음과 같은 성질을 가진다.
노드가개인 이진 트리의 간선의 수는 n 개이다. n−1
노드가개인 이진 트리의 높이는 최소 n , 최대 n이다. log2(n+1)
높이가인 이진 트리는 최소 h 개, 최대 h 개의 노드를 가진다. 2h−1
특히, 높이가
순회
트리의 각 노드를 한 번씩 방문해서 데이터를 처리하는 것을 순회라고 한다. 트리를 출력하려면 이 또한 순회가 필요하다. 노드를 방문할 때 루트와 왼쪽 서브트리, 오른쪽 서브트리를 방문하는 순서에 따라 전위 순회, 중위 순회, 후위 순회로 나뉜다.
전위 순회(Preorder) : 루트 → 왼쪽 서브트리 → 오른쪽 서브트리
중위 순회(Inorder) : 왼쪽 서브트리 → 루트 → 오른쪽 서브트리
후위 순회(Postorder) : 왼쪽 서브트리 → 오른쪽 서브트리 → 루트
다른 방법으로 레벨 순회(Level order)가 있는데, 레벨 순회는 각 노드를 레벨 순서대로 검사하는 방법이다. 동일 레벨에서는 좌에서 우로 방문하게 된다. 이 과정에서 큐를 이용한다. 처음 큐에는 루트 노드를 삽입하고, 큐에서 노드를 꺼낼 때마다 자식 노드들을 큐에 삽입하면 된다.
[배열] 이진 트리 구현
배열 구현은 완전 이진 트리의 순서대로 노드를 저장하면 된다. 한 노드의 인덱스를 알면 부모, 왼쪽 자식, 오른쪽 자식의 인덱스를 바로 알 수 있다.
한 노드의 인덱스가 n일 때,
노드 n의 부모 노드의 인덱스 = n / 2
노드 n의 왼쪽 자식 노드 = 2n
노드 n의 오른쪽 자식 노드 = 2n + 1
#include <iostream>
#include <cstdlib>
using namespace std;
const int MAX_NODE = 16;
class Array_Tree {
int tree[MAX_NODE];
int tsize;
int parent(int i) { return tree[ i / 2 ]; }
int left(int i) { return tree[i * 2]; }
int right(int i) { return tree[i * 2 + 1]; }
public:
Array_Tree() { init(); }
~Array_Tree() {}
void init() { tsize = 0; }
void is_empty() { return tsize == 0; }
void is_full() { return tsize == MAX_NODE - 1; }
// 노드 삽입
void insert(int item) {
if (is_full()) {
cout << "트리 포화 상태" << endl;
exit(1);
}
tsize++;
tree[tsize] = item;
}
/* 삭제, 탐색 */
// 전위 순회
void preorder(int n = 1) {
if (is_empty()) {
cout << "트리 공백 상태" << endl;
exit(1);
}
if (n <= tsize) {
cout << tree[n] << " ";
preorder(2 * n);
preorder(2 * n + 1);
}
}
// 중위 순회
void inorder(int n = 1) {
if (is_empty()) {
cout << "트리 공백 상태" << endl;
exit(1);
}
if (n <= tsize) {
inorder(2 * n);
cout << tree[n] << " ";
inorder(2 * n + 1);
}
}
// 후위 순회
void postorder(int n = 1) {
if (is_empty()) {
cout << "트리 공백 상태" << endl;
exit(1);
}
if (n <= tsize) {
postorder(2 * n);
postorder(2 * n + 1);
cout << tree[n] << " ";
}
}
// 레벨 순회
void levelorder(int n = 1) {
if (is_empty()) {
cout << "트리 공백 상태" << endl;
exit(1);
}
for (int i = n; i <= tsize; i++) {
cout << tree[i] << " ";
}
}
// 노드의 수
int count() { return tsize; }
// 단말 노드의 수
int count_leaf(int n = 1) {
if (tsize <= 1) {
return 0;
}
return tsize - 1;
}
// 트리의 높이
int count_height() { return (int)ceil(log2(tsize + 1)); }
};
[연결리스트] 이진 트리 구현
아래와 같이 노드 구조체를 선언 해주자.
struct Node {
int data;
Node* left; // 왼쪽 자식 노드
Node* right; // 오른쪽 자식 노드
};Node 포인터 n이 있다면 n->left는 n의 왼쪽 자식 노드, n->right는 n의 오른쪽 자식 노드가 된다.
#include <iostream>
#include <queue>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
};
class Linked_Tree {
Node* root;
public:
Linked_Tree() { root = NULL; } // init()과 동일
~Linked_Tree() {}
bool is_empty() { return root == NULL; }
void set_root(int item, Node* l, Node* r) { root = create_tree(item, l, r); }
Node* get_root() { return root; }
// 노드 삽입
Node* create_tree(int item, Node* l, Node* r) {
Node* node = new Node;
node->data = item;
node->left = l;
node->right = r;
return node;
}
// 전위 순회
void preorder(Node* n) {
if (n != NULL) {
cout << n->data << " ";
preorder(n->left);
preorder(n->right);
}
}
// 중위 순회
void inorder(Node* n) {
if (n != NULL) {
inorder(n->left);
cout << n->data << " ";
inorder(n->right);
}
}
// 후위 순회
void postorder(Node* n) {
if (n != NULL) {
postorder(n->left);
postorder(n->right);
cout << n->data << " ";
}
}
// 레벨 순회
void levelorder(Node* root) {
Node* n;
queue<Node*> q;
if (root != NULL) {
q.push(root);
while (!q.empty()) {
n = q.front();
q.pop();
if (n != NULL) {
cout << n->data << " ";
q.push(n->left);
q.push(n->right);
}
}
}
}
// 노드의 수
int count(Node* n) {
if (n == NULL) {
return 0;
}
else {
return 1 + count(n->left) + count(n->right); //루트 노드 1개 더해줌
}
}
// 단말 노드의 수
int count_leaf(Node* n) {
if (n == NULL) {
return 0;
}
if (n->left == NULL && n->right == NULL) {
return 1;
}
else {
return count(n->left) + count(n->right);
}
}
// 트리의 높이
int count_height(Node* n) {
int left, right;
if (n == NULL) {
return 0;
}
left = count_height(n->left);
right = count_height(n->right);
return (left > right) ? left + 1 : right + 1;
}
};[+] C++ STL에서 큐를 지원합니다. 저는 이 큐를 사용했지만, 본인이 만든 큐를 이용하셔도 무방합니다.
[+] 이진 탐색 트리
https://ggjjdiary.tistory.com/41
[알고리즘] 이진 탐색 트리
컴퓨터에서 탐색은 레코드(record)의 집합에서 특정한 레코드를 찾아내는 작업을 뜻한다. 레코드는 하나 이상의 필드(field)로 구성된다. 예를 들어, 한 학생의 정보를 구조체로 저장한다면, 구조체
ggjjdiary.tistory.com
[Reference]
자료구조 - 교보문고
컴퓨터로 어떤 문제를 해결하기 위해 필요한 자료들을 효율적으로 관리하고 구조화시키기 위한 학문 '자료구조'. 이 책은 자료구조를 보다 명확하게 배울 수 있도록 구성되어 있다. 각 장에서는
www.kyobobook.co.kr
'알고리즘(Algorithm) > Data Structure' 카테고리의 다른 글
| [자료구조] 그래프 (0) | 2022.04.04 |
|---|---|
| [자료구조] 우선순위 큐와 힙 (0) | 2022.03.15 |
| [자료구조] 큐 (0) | 2022.03.04 |
| [자료구조] 스택 (0) | 2022.03.02 |