[Data Structure] Tree (트리)

Tree (트리)

 

트리 개념

트리는 non linear data structure이다. 앞서서 배운 리스트, 배열, 벡터는 모두 linear data structure이고 이런 선형 자료구조들은 원소들 간에 전/후 관계가 있다.
그러나 non linear data structure, 즉 비선형 자료구조는 원소들 간에 상/하 관계를 가지고 있다. 이런 것을 계층적 관계라고한다.

 

일반 트리 (General Tree)

 

트리는 보통 general tree와 binary tree로 구분하는데, general tree는 자식노드의 수가 제한이 없는 트리를 말한다.
binary tree는 말 그대로 이진트리로, 자식 노드가 딱 2개만 제한이 되는 트리이다. 굳이 말하면 이진트리도 일반트리에 포함되어있다.
트리는 노드들간의 부모-자식 관계로 이루어진 것들이다.

 

 

• root : root node란 그림 상 가장 꼭대기에 있는 노드를 가리키며 정의로는 부모가 없는 노드를 말한다.
• Internal node : Internal node는 자식이 적어도 1개는 있는 노드를 말한다. 그림 상으로 보면 A, B, D, E가 있다.
• External node (Leaf node) : External node라고도 하고 Leaf node라고도 한다. Internal node와 반대로 자식이 없는 노드를 말한다. 보통 리프 노드라고 한다. 그림 상에서는 C, F, G, H, I, J가 있다.
• Ancestor : 조상 노드라고도 한다. 일반적으로는 본인을 포함한 루트 노드까지 경로에 있는 모든 노드들을 조상 노드라고 한다. 예를 들어 설명해보면, E노드의 조상은 E, B, A이다.
• Descendant : 후손 노드라고도 한다. 후손 노드는 해당 노드를 통해 갈 수 있는 모든 노드를 후손노드라고 일컫는다. 예를 들어 설명하면 그림 상 B노드의 후손은 E, F, G, I, J이다.
• depth of node : depth는 일반적으로 node에 대한 정의를 나타내며 자신을 제외한 조상 노드의 수를 말한다. 일반적으로 자기 조상의 depth + 1로 나타낸다.
  depth에서 나온 개념 중 하나가 level인데, 같은 depth를 가진 node들을 level이라고 한다.
• height : height는 node와 tree 어디에 붙여서 설명하냐에따라 약간씩 달라진다. tree의 height라고 말하면 트리의 높이를 말한다. 일반적으로 해당 트리의 노드 중 가장 큰 depth 값을 tree의 height로 한다.
  node의 height는 특정 노드를 루트 노드로 하는 subtree의 height를 말한다.
• sibling : 남매, 형제 노드라고도 하며 해당 노드와 같은 부모를 둔 노드들을 말한다.
• degree : 특정 노드의 children의 개수이다. 즉 직계 자식 노드들의 개수를 말한다.

 

Tree traversal (트리 순회)

트리에서 중요한 것은 트리의 탐색 방식이다. 일반적인 트리에서는 전위, 후위 순회밖에 없다.

이진트리로 가면 중위 순회도 존재한다. 오늘은 전위, 후위 순회를 설명한다.
참고로 순위를 진행할 때는 해당 노드를 방문했다는 표시를 해주는데, 이를 보통 visit으로 설정한다. 이는 순회 과정 중에 하나에 속하므로 중요한 작업이다.

 

Preorder Traversal (전위 순회)

전위순회란 자식 노드를 탐색하기전에 자신을 우선 방문하고 자식 노드를 방문하는 방식의 순회 방법이다. 전위순회는 일반적으로 재귀로 구현을 한다.
나->자식 순서라고 생각하면 되면 편하다. 

 

< pseudo code >

Algorithm preOrder(v)
	visit(v)
    
    for each childd w of v
    	preOrder(w)

 

전위순회의 의사코드는 위와 같다. 일반적으로 visit의 소요시간을 \(O(1)\)이라고 하면, 전체 순회에 걸리는 시간은 \(O(n)\)시간이 걸린다.

순회에 걸리는 시간은 visit의 소용시간이 결정한다.

 

Postorder Traversal (후위 순회)

후위순회란 자식노드를 먼저 탐색을하고 자신을 탐색하는 순회 방법이다. 사실 후위순회도 재귀로 구현한다.

후에 그래프 혹은 트리 탐색 알고리즘인 DFS가 후위순회의 원리이다.
자식->나 순서로 생각하면 된다.

 

< pseudo code >

Algorithm postOrder(v)
	for each child w of v
    	postOrder(w)
       
	visit(v)