트리와 이진트리

검색 트리 (Search Tree)

Tree and BinaryTree

트리 (Tree)

- 계층적인 구조를 표현한다.

조직도 | 디렉토리와 서브 디렉토리 구조 | 가계도 등

- 트리는 노드 (node)들과 이를 연결하는 링크 (link)들로 구성되어 있다.

맨 위의 노드는 "루트"라고 부른다.

노드를 연결하는 선인 링크는 edge, branch등으로도 불린다.

- 부모 - 자식 관계 : 상하로 링크되어 있는 두 노드를 비교했을 때 상대적으로 루트에 가까운 노드는 부모 노드, 아래쪽 노드는 자식 노드라고 불린다.

- 루트 노드를 제외한 트리의 모든 노드들은 하나의 부모 노드만을 가지고 있다.

- 형제 관계 : 같은 부모노드를 가지고 있는 노드들은 서로 형제(sibling)관계라고 부른다.

- 리프 노드 : 아래에 자식 노드를 두지 않은 노드들은 리프 노드라고 불린다.

- 내부 노드 : 리프 노드가 아닌 노드들은 내부 노드라고 불린다.

- 조상 - 자손 관계 : 부모 - 자식 관계를 확장한 개념으로 조상 - 자손의 개념이 있다. 이는 한 부모 노드에 한개 이상의 링크관계를 두고 자식 노드가 존재한다면 이들 둘의 관계를 각각 조상과 자손이라고 부르는 것을 의미한다.

- 서브 트리 : 트리에서 어떤 한 노드와 그 노드의 자손들로만 이루어진 트리를 부 트리(Sub Tree)라고 부른다.

- 레벨 : 루트 노드를 1레벨로 하여  한 단계씩 밑으로 내려갈때마다 레벨을 1씩 올려준다.

- 높이 : 루트 노드로부터 리프 노드까지의 높이를 비교하는 것인데 리프 노드를 1로 하여 순차적으로 높여간다.

트리의 기본적인 성질

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

- 트리에서는 루트에서 어떤 노드러 가는 경로가 유일하게 존재한다. 또한 임의의 두 노드간의 경로도 같은 노드를 두 번 이상 방문하지 않는다는 조건 하에 유일하다는 특징이 있다.

이진 트리 (Binary Tree)

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

- 각각의 자식 노드에는 자신이 부모의 왼쪽 자식인지 오른쪽 자식인지 지정된다. 이는 또한 자식이 한 명일때도 동일하게 지정된다.

- 자식 노드의 위치만 달라져도 서로 다른 이진트리라고 할 수 있다.

이진 트리 응용

- Expression Tree

- Huffman Code

어떠한 데이터를 인코딩하거나 압축하는 가장 기본적인 알고리즘의 하나이다.

가변 길이 인코딩을 할 때 주로 사용된다.

Full and Complete Binary Trees

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

- 노드가 N개인 full 또는 complete이진 트리의 높이느 O(logN)이 된다.

- 노드가 N개인 이진트리의 높이는 최악의 경우 N이 될 수도 있다.

이진트리의 표현

- 연결 구조 (Linked Structure) 표현

각 노드에 하나의 데이터 필드와 왼쪽 자식, 오른쪽 자식, 그리고 부모 노드(p)의 주소를 저장한다.

부모 노드의 주소는 반드시 필요할 경우가 아니라면 보통 생갹하게 된다. 단, 루트 노드의 주소는 항상 따로 보관해놔야 한다. 첫 번째 노드의 주소를 잃어버린다면 모든 노드를 함께 잃어버리는 문제가 발생하기 때문이다.

이진트리의 순회 (Traversal)

- 이진트리를 루트 노드 r, 왼쪽 서브 트리 Tl, 오른쪽 서브트리 Tr로 나누어 생각한다.

- 순회 : 이진 트리의 모든 노드를 방문하는 일을 뜻한다.

- 중위 (inorder)순회

1)  왼쪽 서브 트리 Tl을 중위 순회한다.

2) 루트 r을 순회한다.

3) 오른쪽 서브 트리Tr을 중위 순회한다.

슈도 코드

INORDER_TREE_WALK (x) //x는 루트노드

if x != null

INORDER_TREE_WALK(left[x])

print key[x]

INORDER_TREE_WALK(right[x])

- 전위 (preorder)순회

1) 루트 r을 순회한다.

2) 왼쪽 서브 트리 Tl을 전위 순회한다.

3) 오른쪽 서브 트리 Tr을 전위 순회한다.

- 후위 (postorder)순회

1) 왼쪽 서브 트리 Tl을 후위 순회한다.

2) 오른쪽 서브 트리 Tr을 후위 순회한다.

3) 루트 노드를 순회한다.

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

레벨 순으로 방문을 수행한다. 동일 레벨의 경우 왼쪽에서 오른쪽 순서로 순회를 한다.

레벨 오더 순회는 큐를 이용하여 구현을 수행한다.

슈도 코드

LEVEL_ORDER_TREE_TRABERSAL()

visit the root;

Q <- root; // Q는 큐를 의미한다.

while Q is not empty

v <- dequeue(Q);

visit children of v;

enqueue children of v into Q;

Expression Trees

- Expression트리를 inorder 순회하게 된다면 아래와 같이 출력된다.

x + y * a + b / c

- 각 서브 트리를 순회할 때 시작과 종료시에 괄호를 추가하게 된다면 더욱 정확한 식이 완성된다.

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

- 위 트리를 postorder 순회하게 된다면 아래와 같이 출력된다.

x y + a b + c / *

- 위 트리를 preorder 순회하게 된다면 아래와 같이 출력된다.

+ x y * / + a b c

- 레벨 오더로 순회하게 된다면 아래와 같이 출력된다.

* + / x y + c a b