[Algorithm] 4-1. 트리와 이진트리(tree and binary tree)

부경대 IT융합응용공학과 권오흠 교수님의 영리한 프로그래밍을 위한 알고리즘 강좌와 '쉽게 배우는 알고리즘: 관계중심의 사고법 - 문병로'등을 통한 알고리즘 학습 강좌 링크

4-1. 트리와 이진트리

트리(Tree)

• 계층적인 구조를 표현하기 위해 사용하는 자료구조

  • 조직도

  • 디렉토리와 서브디렉토리 구조

  • 가계도

용어

• 루트(Root)

  • 트리는 노드(node)들과 노드들을 연결하는 링크(link)들로 구성된다.

  • 맨 위의 노드를 루트라고 한다.

• 부모-자식(parent-child) 관계

  • 각 노드들의 상하 관계를 부모-자식(parent-child)관계로 나타낸다.

• 형제 관계(sibling)

  • 루트노드를 제외한 트리의 모든 노드들은 유일한 부모노드를 가진다.

  • 부모가 동일한 노드들을 형제 관계라고 부른다.

• 리프(leaf) 노드

  • 자식이 없는 노드들을 leaf노드라고 부른다.

  • 리프노드가 아닌 노드들을 내부(internal)노드라고 부른다.

• 조상-자손(ancestor-descendant) 관계

  • 부모-자식 관계를 확장한 것이 조상-자손 관계이다.

• subtree

  • 트리의 특성상 한 노드의 자손노드들의 집합도 트리이다.

  • 트리에서 어떤 한 노드와 그 노드의 자손들로 이루어진 트리를 subtree라고 부른다.

• 레벨(level)

  • root노드는 level 1

  • root노드의 자식노드들은 level 2

  • ...

• 높이

  • 서로다른 레벨의 수이다.

트리의 기본적인 성질

• 노드가 N개인 트리는 항상 N-1개의 링크(link)를 가진다.

• 트리의 루트에서 어떤 노드로 가는 경로는 유일하다. 또한 임의의 두 노드간의 경로도 유일하다. (같은 노드를 두 번 이상 방문하지 않는다는 조건하에).

이진 트리(binary tree)

• 이진 트리에서 각 노드는 최대 2개의 자식을 가진다.

• 각각의 자식 노드는 자신이 부모의 왼쪽 자식인지 오른쪽 자식인지가 지정된다. (자식이 한 명인 경우에도)

이진 트리 응용의 예: Expression Tree

• 수식을 트리로 구성하여 해석한다.

• 연산자들이 이진연산자라면 이진 트리의 형태로 표현할 수 있다.

이진 트리 응용의 예: Huffman Code

• 파일압축과 관련된 유명한 알고리즘 중 하나인 허프만 코딩을 할 때, 각 문자를 encoding하는데 허프만 tree를 구성한다.

• 추후에, 자세히 살펴본다.

Full and Complete Binary Trees

• 꽉찬 이진트리와 완전이진트리

• 높이가 h인 full binary tree는 2^h-1개의 노드를 가진다.

• 노드가 N개인 full 혹은 complete binary 트리의 높이는 O(logN)이다. (노드가 N개인 이진트리의 높이는 최악의 경우 N이 될 수도 있다.)

이진트리의 표현

• 힙을 표현했을 때는, 완전 이진 트리의 형태 였기 때문에 부모와 자식간의 관계가 배열로 표현하기에 충분했다. 하지만, 완전 이진트리가 아닌 형태라면 아래와 같은 구조의 표현이 필요하다.

• 연결구조(Linked Structure)

  • 각 노드에 하나의 데이터 필드와 왼쪽자식(left), 오른쪽 자식(right), 그리고 부모노드(p)의 주소를 저장(부모노드의 주소는 반드시 필요한 경우가 아니면 보통 생략함)

  

  • 예시

    • 트리상의 노드를 객체로 표현하여 이진트리를 Linked Structure로 표현할 수 있다.

  

  ​

이진트리의 순회(traversal)

• 순회

  • 이진 트리의 모든 노드를 방문하는 일

• 중위(inorder) 순회

• 전위(preorder) 순회

• 후위(postorder)순회

• 레벨오더(level-order) 순회

inorder-중위 순회

• 순회는 본질적으로 recursive한 알고리즘이다.

• 이진트리를 루트노드, left Tree, right Tree로 나누어 생각한다.

• 먼저 left Tree를 inorder로 순회하고,

• root를 순회하고,

• right Tree를 inorder로 순회한다.

• pseudo code

  • x를 루트로 하는 트리를 inorder 순회

  • 시간복잡도 O(n)

INORDER-TREE-WALK(x)
  if x != NULL
    then INORDER-TREE-WALK(left[x])
         print key[x]
         INORDER-TREE-WALK(right[x])

postorder와 preorder순회

• inorder 순회와 다른점은 노드를 방문하는 순서뿐이다. 나머지의 개념은 동일하다.

• 트리를 방문하는 순서만 바뀐다.

• preorder-전위 순회

  • root를 순회하고,

  • 먼저 left Tree를 inorder로 순회하고,

  • right Tree를 inorder로 순회한다.

  
  PREORDER-TREE-WALK(x)
    if x != NULL
      then print key[x]
           PREORDER-TREE-WALK(left[x])
           PREORDER-TREE-WALK(right[x])

• postorder-후위 순회

  • 먼저 left Tree를 inorder로 순회하고,

  • right Tree를 inorder로 순회하고,

  • root를 순회한다.

  
  POSTORDER-TREE-WALK(x)
    if x != NULL
      then POSTORDER-TREE-WALK(left[x])
           POSTORDER-TREE-WALK(right[x])
           print key[x]

Expression Trees

• Expression 트리를 inorder-중위 순회하면 다음과 같이 출력됨

  • x + y * a + b / c

• 각 부트리를 순회할 때 시작과 종료시에 괄호를 추가하면 다음과 같이 올바른 수식이 출력됨

  • (x + y) * ((a + b) /c)

• postorder-후위 순회하면 후위표기식이 출력됨

  • x y + a b + c / *

lever-order 순회

• 레벌 순으로 방문, 동일 레벨에서는 왼쪽에서 오른쪽 순서로 방문

• 큐(queue)를 이용하여 구현

  • 맨 처음 큐에 루트 노드 3을 넣는다.

  • 큐를 꺼내고, 3을 출력한 뒤,

  • 3의 왼쪽자식 1과, 오른쪽자식 5를 큐에 넣는다.

  • 1을 꺼내고 출력한 뒤, 1의 자식인 0과 2를 큐에 넣는다.

  • 다음 순서로 5를 꺼내고 출력한 뒤, 5의 왼쪽 자식인 4와 오른쪽 자식인 6을 큐에 넣는다.

• pseudo code

LEVEL-ORDER-TREE-TRAVERSAL()
  visit the root;
  Q <- root       //Q is a queue
  while Q is not empty do
    v <- dequeue(Q);
    visit children of v;
    enqueue children of v into Q;
  end.
end.