[자료구조] 트리

트리

트리는 계층적인 자료를 표현하는데 적합한 자료구조이다.

 

 

트리의 용어

• 노드(node) : 트리를 구성하는 기본 원소
  • 노드 (root node/root): 트리에서 부모가 없는 최상위 노드, 트리의 시작점
  • 부모 노드(parent node): 루트 노드 방향으로 직접 연결된 노드
  • 자식 노드(child node): 루트 노드 반대방향으로 직접 연결된 노드
  • 형제 노드(siblings node): 같은 부모 노드를 갖는 노드들
  • 리프 노드(leaf node/leaf): 루트 노드를 제외한 차수가 1인 정점을 뜻한다. 쉽게 말해 자식이 없는 노드. 단말 노드라 부르기도 한다.
• 경로(path): 한 노드에서 다른 한 노드에 이르는 길 사이에 있는 노드들의 순서
• 길이(length): 출발 노드에서 도착 노드까지 거치는 간선의 개수
• 깊이(depth): 루트 경로의 길이
• 레벨(level): 루트 노드(level=0)부터 노드까지 연결된 간선 수의 합
• 높이(height): 가장 긴 루트 경로의 길이
• 차수(degree): 각 노드의 자식의 개수
• 크기(size): 노드의 개수
• 너비(width): 가장 많은 노드를 갖고 있는 레벨의 크기

 

 

이진 트리

모든 노드가 2개의 서브 트리를 가지고 있는 트리

• 이진트리의 모든 노드는 차수가  2이하이다. 즉 자식 노드의 개수가 2이하이다. 반면 일반 트리는 자식 노드의 개수에 제한이 없다
• 일반 트리와는 달리 이진 트리는 노드를 하나도 갖지 않을 수 있다.
• 서브 트리간에 순서가 존재한다는 점도 다른 점이다. 따라서 왼쪽 서브트리와 오른쪽 서버트리를 구별한다.

 

이진 트리의 성질

• n개의 노드를 가진 이진트리는 정확하게 n-1의 간선을 가진다.
• 높이가 h인 이진트리의 경우, 최소 h개의 노드를 가지며 최대 2^k-1개의 노드를 가진다.
• n개의 노드를 가지는 이진트리의 높이는 최대 n이거나 [log2(n+1)]이 된다.

 

이진 트리의 분류

• 정 이진 트리(full binary tree): 모든 트리의 자식은 0개나 2개다.
• 포화 이진 트리(perfect binary tree): 모든 리프 노드의 높이가 같고 리프 노드가 아닌 노드는 모두 2개의 자식을 갖는다. 이진 트리에서 리프 높이의 최대치가 n일 때 가장 많이 존재할 수 있는 노드의 수는 2^n−1개인데 포화 이진 트리는 이 개수를 모두 채운 이진 트리라고도 볼 수 있다. 또한, 모든 포화 이진 트리는 정 이진 트리이다.
• 완전 이진 트리(complete binary tree): 모든 리프노드의 높이가 최대 1 차이가 나고, 모든 노드의 오른쪽 자식이 있으면 왼쪽 자식이 있는 이진트리이다. 다시 말해 트리의 원소를 왼쪽에서 오른쪽으로 하나씩 빠짐없이 채워나간 형태이다. 포화 이진 트리는 완전 이진 트리의 부분집합이다. 단, 포화 이진 트리가 아닌 완전 이진 트리는 정 이진 트리일 수도 있고 아닐 수도 있다

 

이진 트리의 표현

• 노드 i의 부모 노드 인덱스 = i / 2
• 노드 i의 왼쪽 자식 노드 인덱스 = 2i
• 노드 i의 오른쪽 자식 노드 인덱스 = 2i + 1

 

 

 

이진 트리의 순회

• 중위 순회(in-order traversal) LVR: 왼쪽 자손, 자신, 오른쪽 자손 순서로 방문하는 순회 방법. 이진 탐색 트리를 중위 순회하면 정렬된 결과를 얻을 수 있다.
• 전위 순회(pre-order traversal) VLR: 자신, 왼쪽 자손, 오른쪽 자손 순서로 방문하는 순회 방법.
• 후위 순회(post-order traversal) LRV: 왼쪽 자손, 오른쪽 자손, 자신 순서로 방문하는 순회 방법.
• 레벨 순서 순회(level-order traversal): 너비 우선 순회(Breadth-First traversal)라고도 한다. 노드를 레벨 순서로 방문하는 순회 방법. 위의 세 가지 방법은 스택을 활용하여 구현할 수 있는 반면 레벨 순서 순회는 큐를 활용해 구현할 수 있다.

 

트리 전위 순회 알고리즘

preorder(x):

if x != NULL
	then print DATA(x);
    	 preorder(LEFT(X));
         prorder(RIGHT(X));

 

트리 중위 순회 알고리즘

inorder(x):
	if x != NULL
    	then inorder(LEFT(x));
        	 print DATA(x);
             inorder(RIGHT(x));

 

트리 후위 순회 알고리즘

postorder(x):
	if x != NULL
    	then postorder(LEFT(x));
        	 postorder(RIGHT(x));
             print DATA(x);

 

트리 레벨 순회 알고리즘

level_order(root):

initialize queue:
if (root == null) then return;
enqueue(queue, root);
while is_empty(queue) != TRUE do
	x <- dequeue(queue);
    print x -> data;
    if (x -> left != NULL) then
    	enqueue(queue, x -> left)
    if (x -> right != NULL) then
    	enqueue(queue, x -> left);

 

수식 트리 계산 알고리즘

evaluate(exp):

if exp == NULL
	then return 0;
    else x <- evaluate(exp, left);
    	 y <- evaluate(exp, rihgt);
         op <- exp.data;
         return (x op y);

 

이진 탐색 트리에서 노드 개수 구하는 알고리즘

get_node_count(x):

if x != NULL then
	return 1 + get_count(x.left) + get_count(x.right);

 

이진 탐색 트리에서 단말노드 개수 구하는 알고리즘

get_leaf_count(T):

if T != NULL then
	if T.left == NULL and T.right = NULL
    	then return 1;
        else return get_leaf_count(T.left) + get_leaf_count(T.right);

 

이진 탐색 트리에서 높이 구하는 알고리즘

get_height(T):

if T != NULL
	return 1 + max(get_height(T.left), get_height(T.right));

 

 

이진 탐색 트리

• 이진 탐색 트리는 이진 틔 기반의 탐색을 위한 자료 구조이다.
• 모든 원소의 키는 유일한 키를 가진다.
• 왼쪽 서브 트리 키들은 루트 키보다 작다.
• 오른쪽 서브 트리의 키들은 루트의 키보다 크다.
• 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

 

이진 탐색 트리 탐색 알고리즘(순환적)

search (root, key):

if root = NULL
	then return NULL;
if key == KEY(root)
	then return root;
    else if key < KEY(root)
    	then return search(LEFT(root), k);
        else return search(RIGHT(root), k);

 

 

이진 탐색 트리 삽입 알고리즘

insert (root, n):

if KEY(n) == KEY(root)
	then return;
else if KEY(n) < KEY(root) then
	if LEFT(root) == NULL
    	then LEFT(root) <- n;
        else insert(LEFT(root), n);
else
	if RIGHT(root) == NULL
     	then RIGHT(root) <- n;
        else insert(RIGHT(root), n);