Trees

이번 글은 서강대학교 소정민 교수님의 강의와 Ellis Horowitz의「Fundamentals of Data Structures in C」를 바탕으로 작성했음을 밝힙니다.

From Textbook

A tree is a finite set of one or more nodes such that:

1. There is a special designated node called the root.

2. The remaining nodes are partitioned into $n \geq 0$ disjoint sets $T_1, T_2, ... , T_n$ where each of these sets is a tree

   • We call $T_1, T_2, ... , T_n$ the subtrees of the root.

From Wiki

트리 구조(tree)란 그래프의 일종으로, 여러 노드가 한 노드를 카리킬 수 없는 구조이다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다.
트리에서 최상위 노드를 루트 노드(root node) 라고 한다. 또한, 노드 A가 노드 B를 가리킬 때 A를 B의 부모 노드(parent node), B를 A의 자식 노드(child node) 라고 한다. 자식 노드가 없는 노드를 잎 노드(leaf node)라고 한다. 잎 노드가 아닌 노드를 내부 노드(internal node)라고 한다.

1.1 Terms

Node

• A node is a basic unit of a tree. A node contains data and also may link to other nodes

1.1.1 Degree

• A degree of a node is the number of subtrees of the node.
• A degree of a tree is the maximum degree of the nodes in the tree.
• A node with degree zero is a leaf or terminal node

1.1.2 Subtree

• A node that has subtrees is the parent of the roots of the subtrees, and the roots of the subtrees are the children of the node.
• Children of the same parent are called siblings.

1.1.3 Height

• The height of a node
  • length of the path from a particular node to the farthest leaf node.
• The height of a tree
  • the length of the path from the root to the deepest node in the tree

1.1.4 Depth

• The depth of a node
  • reverse of height
  • length of the path from the root node
• The depth of a tree
  • depth of the deepest node

교과서마다, 또 사람마다 height와 depth의 정의가 다릅니다. 이는 맨 처음을 0으로 볼 것인가, 1로 볼 것인가에 대한 차이인데요.
이 교과서에선 leaf node의 height를 0, root node의 depth를 0으로 간주하여 height/depth를 0부터 세게 되지만, 어떤 교과서에서는 leaf node의 height를 1부터 세게 됩니다. 따라서 이에 대해 항상 주의해야 합니다.

1.1.5 Level

1.2 Representation

1.2.1 Generalized List

Linked List를 이용하여 Tree를 구현하는 방법

첫 번 째 list를 root node를 뜻하고, 그 node의 포인터는 root node의 subtrees를 가리킵비다.
또, 그 subtrees의 포인터는 각각의 root node를 가르키고, 또 recursive 하게 그 node의 포인터는 root node의 subtree를 가리킵니다.

1.2.2 Direct Representation

Struct에 node의 data와, child에 대한 포인터를 여러 개 두어서 tree를 구현하는 방법

직관적으로 이해하기 쉽지만, 기본적으로 어떤 node가 child를 무수히 많이 가질 수 있는 시스템으로 만들어야 해, 동적으로 할당을 하더라도 child가 많아질 경우 비효율적이라는 단점이 있습니다. A라는 node에 child가 100개, B node에 1개씩 있을 경우, 모든 node가 100개의 포인터씩을 가지고 있어야 합니다.

1.2.3 Left-Child-Right Sibling

Struct에 node의 data와, 포인터는 단 두 개만 두어서 tree를 구현하는 방법

모든 node의 포인터 하나는 가장 왼쪽의 child를 가리키고, 다른 하나는 자신의 sibling을 가리킵니다.