[자료구조] Tree

[Keywords]

DAG(Directed Acyclic Graph- 방향성이 있는 비순환 그래프),

이진 트리, 노드, 부모노드, 자식노드, O(logN)

 

Q. 자료구조 형태 중 트리 구조에 대해서 설명해보시오

트리는 나무를 의미하는데 데이터를 이러한 나무의 형태로 저장한다는 의미이다. 나무에 잎과 뿌리가 있듯이, 자료구조 트리에도 leaf, root 가 존재한다.  트리는 부모노드와 자식노드로 구성된다. 부모는 상단에 위치하고 자식은 하단에 위치한다. 최상단 부모노드는 root 이고 최하단 자식노드들은 leaf 라고 한다. 각 노드는 0개 이상의 자식노드를 가질 수 있다. 또한 트리는 하나의 루트를 가진다. 트리는 노드와 노드 사이를 연결하는 edge 로 구성되어 있다. 즉, 노드들과 그것들을 잇는 edge 로 이뤄진 자료구조이다. 주의해야 할 점이 있는데 트리는 사이클이 존재할 수 없다. 

Q. 왜 트리구조를 사용하는지 말해보시오

빠르다. N개의 데이터를 탐색하는데 O(logN) 의 시간복잡도를 가진다.

이진 탐색 트리에서 탐색, 삽입, 삭제 연산의 시간 복잡도는 트리의 높이를 h라고 했을 때 h에 비례한다. 최선의 경우는 이진 트리가 균형적으로 생성되어 있는 경우 (h = logN) 이고 최악의 경우는 (h=n)이다. 이때 순차탐색과 시간복잡도가 같다.

Q. 트리 구조의 장점을 활용한 사례를 말해보시오.

인덱스 트리는 트리의 노드들에 인덱스가 있다고 가정하고 자식 노드들에 값이 저장 될때 해당하는 부모노드에 자식노드들의 값의 합을 저장하는 것을 말한다. 이럴 경우, 연산의 속도가 빨라지는데 왜냐하면, 현재노드의 값은 자식노드들의 구간의 합이기 때문에 매번 자식노드들의 합을 구할 필요없이 사용이 가능하기 때문이다. 

또한, 정렬 상태를 유지할 수 있다. 정렬상태를 유지하기 위해서 내부적으로 heap(내부의 데이터에서 최소 혹은 최대의 값을 리턴한 후 남은 데이터들을 자동 정렬하여 저장하는 방식)형태의 트리구조를 사용하는데 이 덕분에 정렬을 유지할 수 있다. 이를 활용하여 priorty queue 와 같이 항상 정렬상태를 유지하는 구조에 활용 가능하다.

 

[map 을 사용한 트리구현 (c++)]

c++ 은 map을 사용하는게 쉽다.

 #include <iostream>
 #include <map>
 using namespace std;

 map <char, pair<char, char>> tree;

 void search(int cur, int depth) {
     printf("%d: %c\n", depth, cur);
     if(tree[cur].first == '.' && tree[cur].second == '.')
         return;

     if(tree[cur].first != '.')
         search(tree[cur].first, depth+1);

     if(tree[cur].second != '.')
         search(tree[cur].second, depth+1);
 }

 int main() {
     tree['A'] = make_pair('B', 'C');
     tree['B'] = make_pair('D', '.');
     tree['D'] = make_pair('.', '.');
     tree['C'] = make_pair('E', 'F');
     tree['E'] = make_pair('.', '.');
     tree['F'] = make_pair('.', 'G');
     tree['G'] = make_pair('.', '.');

     search('A', 0);

     /**
     0: A
     1: B
     2: D
     1: C
     2: E
     2: F
     3: G
     **/
 }

 

[배열을 사용한 트리 구현 (c++)]

 #include <iostream>
 #include <vector>
 using namespace std;

 class Tree {
     public:
         vector <char> nodes;
     public:
         Tree(int node_size, char root_data) {
             nodes.resize(node_size);
             nodes[0] = root_data;
         }
         void setLeft(char data, int parents_node) {
             nodes[parents_node * 2 + 1]  = data;
         }
         void setRight(char data, int parents_node) {
             nodes[parents_node * 2 + 2]  = data;
         }
         void PrintTree() {
             for(auto n: nodes) {
                 printf("%c ", n);
             }
         }
 };

 int main() {

     Tree t(7, 'A');

     t.setLeft('B', 0);
     t.setRight('C', 0);

     t.setLeft('D', 1);
     t.setRight('E', 1);

     t.setLeft('F', 2);
     t.setRight('G', 2);

     t.PrintTree();

 }