Goal
- 트리 기본 용어에 대한 이해
- 트리와 이진 트리의 정의를 말할 수 있다
- 트리와 이진트리의 성질에 따른 특징을 설명할 수 있다
- 이진 탐색 트리에 대한 이해(정의, 연산, 성능, 활용 예시)
- 힙에 대한 이해(정의, 연산, 성능, 활용 예시)
트리의 기본 용어
트리는 그래프의 특수한 형태로 그래프 모양이 나무를 뒤집어 놓은 것 같다고 해서 이름 붙여졌다.
(트리 용어 이전에 그래프에 대한 이해와 관련 용어를 찾아보면 좋다)
루트 노드(Root Node) : 트리에서 부모가 없는 최상위 노드. 트리의 시작점
부모 노드(Parent Node) : 루트 노드 방향으로 직접 연결된 노드
자식 노드(Child Node) : 루트 노드 반대방향으로 직접 연결된 노드
형제 노드(Siblings Node) : 같은 부모 노드를 갖는 노드들
리프 노드(Leaf Node/ Leaf / Terminal Node): 자식이 없는 노드
내부 노드(Internal / Branch Node) : 차수가 0이 아닌 노드 (자식 노드가 있는 노드, 차수 1이상)
조상 노드(Ancestor Node) : 루트 노드에서 해당 노드까지의 경로에 있는 노드
자손 노드(Descendent Node) : 임의의 노드 하위에 연결된 모든 노드
경로(Path): 시작 노드부터 목적 노드까지의 간선의 순서 있는 나열
경로의 길이(Path Length) : 경로에 있는 간선의 수 (경로에 있는 노드 수 – 1)
깊이(Depth): 루트 노드로부터의 경로의 길이 (루트 노드의 깊이는 0)
레벨(Level) : 같은 깊이 값을 가지는 노드들의 집합
트리의 높이(Height) : 트리가 가지고 있는 최대 레벨(또는 최대 깊이)
차수(Degree) : 각 노드의 자식의 개수
트리의 차수(Degree Of Tree) : 노드의 차수 중 가장 큰 차수 값
서브 트리(Sub-Tree) : 트리인 부분 그래프
ex) 왼쪽 또는 오른쪽 자식을 루트로 하는 서브 트리 - left sub tree, right sub tree
트리(Tree)
그래프 이론에서의 트리의 정의는 다음과 같다
connected acyclic graph
수학적으로 다음은 트리와 동치이다.(역도 성립한다는 의미)
connected graph 에서 노드 개수가 n개일 때 간선의 수가 n+1개이면 이 그래프는 트리이다.
트리는 다음과 같이 표현될 수 있다.
루트 노드를 제외한 모든 노드는 단 하나의 부모 노드만 갖는다.
그래서 다음과 같은 특징을 갖는다.
- 노드 개수가 N개일 때 반드시 N-1개의 간선을 갖는다. |N| = |E| - 1 => 루트를 제외(-1)한 모든 노드는 부모 노드와 연결 되어 있다.
- 모든 노드는 연결(connected) 되어 있다. => connected graph
- Cycle이 존재 하지 않는다. (Self-loop도 불가능) => 비순환 그래프(Acyclic Graph)
- 임의의 두 노드에 사이의 경로는 유일하다.
- 트리는 최소 연결(minimal connected) 그래프이다(|N| = |E| - 1). edge를 자르면 disconnected graph가 된다.
- 자식 노드들은 각각 자신을 루트로 하는 서브 트리(Sub-Tree)를 형성한다. => 트리의 재귀적 속성, 트리가 유용하게 사용되는 큰 이유 중 하나이다.
- edge를 자르면 2개의 트리로 분할된다.
다음 그림은 트리가 아닌 경우이다
- Cycle이 존재 (self-loop)
- Cycle이 존재 B->C->E->D
- 1 -> 4로 가는 유일 경로가 존재하지 않는다. (부모 노드가 둘, 2를 거쳐서 가는 경우, 3을 거쳐서 가는 경우)
- 연결 그래프가 아니다. (각각은 트리가 될 수 있으나, 모든 노드사이의 경로가 존재하는 연결 그래프가 아니다.)
트리의 구분
트리는 그자체를 사용하는 경우 보다는, 특정 제한 속성을 갖는 트리를 많이 사용한다.
예를 들면 다음과 같은 제한 속성들이 있을 수 있다.
- 노드가 가질 수 있는 자식 노드 갯수를 제한 - 이진 트리
- 노드간 순서를 제한. (비교 연산을 통해서 부모-자식 또는 형제 노드 등의 순서를 제한한다) - 탐색 트리
- 트리 균형을 유지 시키는지 - 균형 트리
이진 트리(Binary Tree)
노드의 차수가 2이하인 트리
ex) 완전 이진 트리, 이진 힙, 이진 탐색 트리 etc..
탐색 트리(Search Tree)
특정 key를 검색하는데 유리한 트리
ex) 이진 탐색 트리(Binary Search Tree)
검색을 빠르게 하기 위한 트리로 왼쪽 서브트리와 오른쪽 서브트리간의 대소 비교가 가능해야 한다. (왼쪽값 < 오른쪽)
(C++ STL map을 사용할 때, 비교함수를 넘겨주는 이유도 검색을 빨리 하기 위해서이다)
균형 트리(Balanced Tree)
트리가 한쪽 방향으로 치우쳐져 있지 않고 균형을 이루는 트리
ex) AVL-Tree, red-black tree
트리의 노드가 한쪽으로 치우쳐져 있는 트리(사향 트리 - Skewed Tree)의 경우 탐색과 같은 연산을 할 때 안좋은 성능을 낸다. 그렇기 때문에 탐색 속도를 높이려면 트리의 균형을 맞춰야 한다.
자가균형 이진 탐색 트리 : 자체 알고리즘에 의해 트리의 균형을 맞추는 이진 탐색 트리 - AVL-Tree, Red-Black Tree
이외에도 트리 종류가 굉장히 많지만 앞으로 관련 트리 내용을 정리하면서 추가적으로 설명할 예정이다.
이진 트리(Binary Tree)
자식 노드의 개수가 2이하인 트리
이진 트리의 재귀적 정의
- 공집합이거나
- 루트, 왼쪽 서브트리, 오른쪽 서브트리로 구성된 집합. 서브트리는 역시 이진 트리여야한다.
이진 트리의 특징
1) n-1개의 간선을 갖는다. (n은 노드의 개수)
=> 루트를 제외한 모든 자식 노드가 단 하나의 부모 노드를 갖기 때문 (트리의 성질)
2) $h \leq n \leq 2^{h - 1}$ 사이의 노드를 갖는다. (높이 h를 알 때)
설명
h : 레벨당 적어도 1개의 노드를 갖으므로 최소 h개의 노드를 갖는다.
$2^h - 1$ : h레벨까지 모든 노드가 꽉 차있는 경우.
=> i레벨의 노드 개수는 $2^i$개이다. 따라서 h높이 까지의 최대 노드 개수는 1~h레벨 까지의 노드의 합이므로 $\sum_{i=1}^{h}2^{i-1}$ 이 된다. (등비수열의 합 공식을 사용해 유도)
3) $\lceil \log_2 (n+1) \rceil \leq h \leq n$ (노드 개수 n을 알 때 h의 범위)
설명
- $\lceil \log_2 (n+1) \rceil$ : h레벨까지 모든 노드가 꽉 차있는 경우로, $n \leq 2^{h - 1}$ 이므로 $log_2 (n+1) \leq h$이다. 이 로그 값은 실수 값이 나올 수 있으므로, 보다 큰 정수중 최소인 값이 노드 개수가 된다. 따라서 $log_2 (n+1) = h$가 된다.
( $\lceil\ \rceil$ - ceiling : 실수 이상의 최소 정수)
- n : 레벨당 최소 하나의 노드는 있어야 하므로 h가 n을 넘을 순 없다.
4) 차수의 개수에 따라 n0, n1, n2로 나눴을 때 다음 등식이 성립한다. (n은 전체 노드 개수)
n0 = n2 + 1 => leaf node의 개수 = 자식 노드가 2개인 노드 개수 + 1
[증명]
1) n = n2 + n1 + n0 => 차수가 2이하인 노드의 합 = 전체 노드의 합
2) n = (2 * n2) + (1 * n1) + (0 * n0) + 1 => 자식 노드의 합 + 루트노드 = 전체 노드의 합
3) 1), 2)를 n에 대해 연립해서 풀면 n0 = n2 + 1을 구할 수 있다.
5) 노드 개수가 n일 때,
공집합 서브 트리 = n + 1 이다.
즉, leaf node의 NULL 포인터 개수 = n + 1
설명
1) E = 2n (E는 서브트리 개수 - 포인터 개수)
2) 부모와 연결된 서브 트리(간선) = n-1
=> 공집합 개수는 = 2n - (n-1) = n+1
6) 인덱스 계산 (i는 현재 노드 인덱스)
부모 = i/2
왼쪽 자식 = 2 * i
오른쪽 자식 = 2 * i + 1
설명
인덱스 0은 계산 편의상 비워둔 경우이다. (인덱스 1이 루트 노드)
7) 노드 개수 = 1 + 왼쪽 서브 트리 노드 개수 + 오른쪽 서브 트리 노드 개수
8) 트리 높이(height) = 1 + max(Height(Left), Height(Right))
이진 트리의 종류
Full Binary Tree
모든 노드가 0 또는 2개의 자식 노드를 갖는 이진 트리
완전 이진 트리(Complete Binary Tree)
마지막 레벨을 제외한 모든 레벨에서 노드들이 꽉 채워진 이진 트리
- h-1 레벨까지는 모든 노드가 채워져 있다.
- h 레벨에서는 왼쪽에서부터 오른쪽으로 노드가 순서대로 채워져 있다.
$2^{h-1} - 1 \leq n \leq 2^h - 1$
이진 힙(binary heap)이 완전 이진 트리의 대표적인 예이다.
포화 이진 트리(Perfect Binary Tree)
모든 노드가 0개 혹은 2개의 자식노드를 가지며 모든 리프노드가 똑같은 레벨에 있는 경우의 트리이다.
정확히 노드 개수가 $n = 2^h - 1$개이다.
포함관계로 보면 다음과 같다.
full binary tree ⊃ complete binary tree ⊃ perfect binary tree
이진 탐색 트리
효율적인 탐색 작업을 위한 이진트리
(이진 탐색 트리에 대해서는 따로 다룰 예정)
힙(heap)
최소값 또는 최대값을 빠르게 구할 수 있는 형태의 자료구조
일반적으로 힙이라고 하면 이진 힙을 의미한다.
우선 순위 큐를 구현할 때 사용된다.
(이진 힙에 대해서 따로 다룰 예정)
이진트리 구현에 따른 분류
배열
[장점] : 노드의 위치를 쉽게 접근할 수 있다. (인덱스 계산)
[단점] : 특정 트리(한 쪽으로 치우친 트리)에서 기억 공간의 낭비가 심할 수 있다.
연결 리스트
[장점] : 저장 공간을 절약(노드 수 만큼 생성)할 수 있고, 노드의 삽입 삭제가 용이하다.
[단점] : 배열 보다는 탐색하는 알고리즘이 복잡하다.
이진 트리 순회 (Traversal)
노드 방문 순서에 따라 구분 (V : 방문 노드, L : 왼쪽 자식, R : 오른쪽 자식)
- 전위 순회(Pre-Order) : VLR - 깊이 우선 순회(DFS)방식
- 중위 순회(In-Order) : LVR - 사람이 이해하기 편한 순회
- 후위 순회(Post-Order) : LRV – 컴퓨터가 이해하기 좋은 순회
- 레벨 순회(Level-Order) : 낮은 레벨부터 차례로 순회 (너비 우선 순회 - BFS)
트리의 순회 의사 코드(pseudocode)
이진트리 구현 코드
이진 트리 구현 코드(포인터로 구현)
#include <iostream>
#include <queue>
using namespace std;
struct Node
{
Node() : value(0), left(nullptr), right(nullptr) {}
Node(char value, Node* left, Node* right) : value(value), left(left), right(right) {}
char value;
Node* left;
Node* right;
};
class BinaryTree
{
public:
BinaryTree();
~BinaryTree();
void destroy_tree();
// tree traversal
void preorder();
void inorder();
void postorder();
void levelorder();
int getCount();
int getHeight();
void set_root(Node* node);
private:
void destroy_tree(Node* leaf);
void preorder(Node* node);
void inorder(Node* node);
void postorder(Node* node);
int getCount(Node* node);
int getHeight(Node* node);
Node* root;
};
BinaryTree::BinaryTree() : root(nullptr)
{
}
BinaryTree::~BinaryTree()
{
destroy_tree();
}
void BinaryTree::destroy_tree()
{
destroy_tree(root);
}
void BinaryTree::destroy_tree(Node* node)
{
if (nullptr != node)
{
destroy_tree(node->left);
destroy_tree(node->right);
delete node;
}
}
void BinaryTree::preorder()
{
cout << "Preorder : ";
preorder(root);
cout << "\n";
}
void BinaryTree::preorder(Node* node)
{
// V L R
if (nullptr != node)
{
cout << node->value << ",";
preorder(node->left);
preorder(node->right);
}
}
void BinaryTree::inorder()
{
cout << "Inorder : ";
inorder(root);
cout << "\n";
}
void BinaryTree::inorder(Node* node)
{
// L V R
if (nullptr != node)
{
inorder(node->left);
cout << node->value << ",";
inorder(node->right);
}
}
void BinaryTree::postorder()
{
cout << "Postorder : ";
postorder(root);
cout << "\n";
}
void BinaryTree::postorder(Node* node)
{
// L R V
if (nullptr != node)
{
postorder(node->left);
postorder(node->right);
cout << node->value << ",";
}
}
void BinaryTree::levelorder()
{
cout << "Level order : ";
if (nullptr == root)
{
return;
}
queue<Node*> q;
q.push(root);
while (false == q.empty())
{
Node* node = q.front();
q.pop();
cout << node->value << ",";
if (nullptr != node->left)
q.push(node->left);
if (nullptr != node->right)
q.push(node->right);
}
cout << "\n";
}
int BinaryTree::getCount()
{
int count = getCount(root);
printf("Tree node count : %d\n", count);
return count;
}
int BinaryTree::getCount(Node* node)
{
if (nullptr != node)
{
return 1 + getCount(node->left) + getCount(node->right);
}
return 0;
}
int BinaryTree::getHeight()
{
int height = getHeight(root);
printf("Tree height : %d\n", height);
return height;
}
int BinaryTree::getHeight(Node* node)
{
if (nullptr != node)
{
int left = getCount(node->left);
int right = getCount(node->right);
return 1 + (left < right ? right : left);
}
return 0;
}
void BinaryTree::set_root(Node* node)
{
root = node;
}
int main()
{
BinaryTree* tree = new BinaryTree();
Node* d = new Node('D', nullptr, nullptr);
Node* e = new Node('E', nullptr, nullptr);
Node* b = new Node('B', d, e);
Node* f = new Node('F', nullptr, nullptr);
Node* c = new Node('C', f, nullptr);
Node* a = new Node('A', b, c);
tree->set_root(a);
// 트리 순회(tree traversal)
tree->preorder();
tree->inorder();
tree->postorder();
tree->levelorder();
tree->getCount();
tree->getHeight();
delete tree;
}
이진 트리 구현 코드(배열로 구현)
#include <iostream>
#include <queue>
using namespace std;
class BinaryTree
{
public:
BinaryTree();
~BinaryTree();
// tree treaversal
void preorder();
void inorder();
void postorder();
void levelorder();
int getCount();
int getHeight();
void insert_node(int idx, char value);
private:
void preorder(int idx);
void inorder(int idx);
void postorder(int idx);
int getCount(int idx);
int getHeight(int idx);
private:
static const int MAX = 100;
char values[MAX];
int size;
};
BinaryTree::BinaryTree() : values{ 0 }
{
}
BinaryTree::~BinaryTree()
{
}
void BinaryTree::preorder()
{
cout << "Preorder : ";
preorder(0);
cout << "\n";
}
void BinaryTree::preorder(int idx)
{
// V L R
if (0 != values[idx])
{
cout << values[idx] << ",";
preorder(2 * idx + 1);
preorder(2 * idx + 2);
}
}
void BinaryTree::inorder()
{
cout << "Inorder : ";
inorder(0);
cout << "\n";
}
void BinaryTree::inorder(int idx)
{
// L V R
if (0 != values[idx])
{
inorder(2 * idx + 1);
cout << values[idx] << ",";
inorder(2 * idx + 2);
}
}
void BinaryTree::postorder()
{
cout << "Postorder : ";
postorder(0);
cout << "\n";
}
void BinaryTree::postorder(int idx)
{
// L R V
if (0 != values[idx])
{
postorder(2 * idx + 1);
postorder(2 * idx + 2);
cout << values[idx] << ",";
}
}
void BinaryTree::levelorder()
{
cout << "Level order : ";
if (0 == values[0])
{
return;
}
int idx = 0;
using queueType = queue<pair<int, char>>;
queueType q;
q.push(queueType::value_type(0, values[idx]));
while (false == q.empty())
{
int idx = q.front().first;
int val = q.front().second;
q.pop();
cout << val << ",";
int left = 2 * idx + 1;
int right = 2 * idx + 2;
if (0 != values[left])
q.push(queueType::value_type(left, values[left]));
if (0 != values[right])
q.push(queueType::value_type(right, values[right]));
}
cout << "\n";
}
int BinaryTree::getCount()
{
int count = getCount(0);
printf("Tree node count : %d\n", count);
return count;
}
int BinaryTree::getCount(int idx)
{
if (0 != values[idx])
{
int left = 2 * idx + 1;
int right = 2 * idx + 2;
return 1 + getCount(left) + getCount(right);
}
return 0;
}
int BinaryTree::getHeight()
{
int height = getHeight(0);
printf("Tree height : %d\n", height);
return height;
}
int BinaryTree::getHeight(int idx)
{
if (0 != values[idx])
{
int left = getCount(2 * idx + 1);
int right = getCount(2 * idx + 2);
return 1 + (left < right ? right : left);
}
return 0;
}
void BinaryTree::insert_node(int idx, char value)
{
values[idx] = value;
}
int main()
{
BinaryTree* tree = new BinaryTree();
tree->insert_node(0, 'A');
tree->insert_node(1, 'B');
tree->insert_node(2, 'C');
tree->insert_node(3, 'D');
tree->insert_node(4, 'E');
tree->insert_node(5, 'F');
// 트리 순회(tree traversal)
tree->preorder();
tree->inorder();
tree->postorder();
tree->levelorder();
tree->getCount();
tree->getHeight();
delete tree;
}이진 탐색 트리(BST, Binary Search Tree)
탐색에 특화된 이진 트리로 다음과 같은 순환적으로 정의된다.
- 모든 노드는 유일한 키를 갖는다.
- 왼쪽 서브트리의 키들은 루트 키보다 작다.
- 오른쪽 서브트리의 키들은 루트 키보다 크다.
- 좌우 서브 트리는 각각 이진 탐색 트리이다.
이진 탐색 트리(BST)가 중복 값을 허용경우도 있는데, 이 경우 중복값에 대한 처리를 해줘야 한다고한다.(중복이 불가능한것은 아니라는 것만 알고 넘어가자)
Red-Black 트리와 같이 균형을 맞추는 균형 이진 트리의 경우 중복 값에 대한 특별한 처리가 필요하다고 한다.
위와 같은 이진 탐색 트리의 성질 때문에 어느 정도 정렬된 상태를 유지한다.
이진 탐색 트리의 주요 연산
- 검색(search)
- 삽입(insert)
- 삭제(remove)
검색(search/retreiv/find)
각 단계를 진행할 때마다 한쪽 서브 트리에 대한 탐색이 배제되므로 평균적으로 1/2만큼의 탐색 시간이 줄어든다.
여기서 평균적이라고 한 이유는 이진 탐색 트리 자체는 기본적으로 균형 트리가 아니기 때문에 편향(Skewed)트리일 경우 탐색이 선형시간이 나오기 때문이다.
노드 개수가 n, 높이가 h인 이진 탐색 트리인 경우
이진 탐색 트리의 시간 복잡도 : O(h)
- 균형 트리인 경우 : O(logn) - 평균적인 시간 복잡도
- 최악 : O(n) - 선형시간(skewed 트리인 경우)
삽입(insert)
새 노드를 트리의 중간에 위치에 삽입하는 경우 트리의 속성을 깨트릴 수 있기 때문에, 탐색이 끝난 위치에 삽입한다.
삽입 연산 시간 복잡도 : O(h) => 탐색 O(h) + 삽입 O(1)
삭제 연산
Case3의 경우 양쪽 서브트리에서 후계 노드를 정하지 않고 한쪽 서브 트리에서만 정하는 방법도 있다.
삭제 연산 시간 복잡도 : O(h)
삭제 대상 노드 레벨이 d이고 전체 높이가 h라 했을 때,
탐색 O(d), 후계 노드 탐색 O(h-d), 삭제 연산 O(1)
따라서 전체 걸리는 시간은 O(d+(h-d)) + O(1) => O(h)
이진 탐색 트리 구현 코드
이진 탐색 트리 시간 복잡도
이진 탐색 트리의 한계와 균형 이진 트리
이진 탐색 트리의 탐색, 삽입, 삭제에 대한 시간 복잡도는 O(h)이다.
이진 탐색 트리의 연산은 탐색 속도에 영향을 받으며, 탐색은 트리의 높이 h에 따라 성능이 좌우된다. 따라서 트리 높이 h크기를 작게 할 수 있으면 좋은데, 일반적인 이진 탐색 트리에서 트리의 높이 h 크기를 제어할 수가 없다.
이런 이진 탐색 트리의 한계 때문에 트리의 균형을 맞추는 균형 이진 탐색 트리가 제안되었다.
균형 이진 탐색 트리는 말 그래도 트리의 균형을 유지하는 이진 탐색 트리로, 내부 알고리즘에 의해 트리의 높이 h의 크기를 줄일 수 있다. 그 결과 트리의 탐색 성능을 향상 시킬 수 있다.
참고)
https://ratsgo.github.io/data%20structure&algorithm/2017/10/21/tree/
https://mathworld.wolfram.com/Tree.html
https://www.tutorialspoint.com/graph_theory/graph_theory_trees.htm
'알고리즘 > 자료구조' 카테고리의 다른 글
| 힙(heap) (0) | 2020.07.02 |
|---|---|
| 가중치 그래프(Weighted Graph), 최소 신장 트리(MST) (0) | 2020.06.21 |
| 그래프(Graph) (0) | 2020.06.18 |
| 덱(Deque) (0) | 2020.06.18 |
| 큐(Queue) (0) | 2020.06.16 |
