[자료구조] 트리(Tree)란, 트리 순회, 이진 트리, 이진 탐색 트리(Binary Search Tree)

트리(Tree)의 특징

• 원소들 간에 다대일 관계를 가지는 비선형 자료구조이다.
• 계층적 관계를 표현하는 자료구조이다.
• 트리의 구조는 데이터의 저장보단 저장된 데이터의 탐색에 중점을 둔다.
• 사이클이 존재하지 않는다.(사이클이 없는 하나의 연결 그래프라 할 수 있다.)
• 루트 노드를 제외하고 모든 노드는 단 하나의 부모노드를 갖는다.
• N개의 노드를 갖는 트리는 N-1개의 간선(edge)를 갖는다.

트리(Tree)의 용어

• 노드(node) : 트리의 원소 (A, B, C, D, E, F, G, H, I, J)
• 간선(edge) : 노드를 연결하는 선으로 부모-자식간을 연결한다.
• 루트 노드(root node) : 부모가 없는 최상위 노드를 의미하며 트리는 단 하나의 루트노드를 갖는다.  (A)
• 단말 노드(leaf node) : 자식이 없는 노드(terminal node 라고도 한다.) (H,I,J)
• 형제(sibling) : 같은 부모를 같는 노드(H-I, D-E, F-G)
• 크기(size) : 트리에 포함된 모든 노드의 개수
• 깊이(depth) : 루트 노드로부터의 거리(A는 0, B와C는 1, (D,E,F,G)는 2..)
• 높이(height) : 깊이의 최댓값
• 차수(degree) : 각 노드의 자식 간선 갯수(A의 차수는 2, E는 0, F는 1..)
• 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합(level 1 = {B,C})

트리(Tree)의 순회 종류

1. 전위 순회(Preorder Traversal)

전위 순회는 루트노드 - 왼쪽 서브트리 - 오른쪽 서브트리 순의 탐색이 재귀적으로 진행된다.

A-B-D-H-I-E-C-F-J-G

 

2. 중위 순회(Inorder Traversal)

중위 순회는 왼쪽 서브트리 - 루트노드 - 오른쪽 서브트리 순으로 재귀적 탐색을 진행한다.

H-D-I-B-E-A-J-F-C-G

 

2. 후위 순회(Postorder Traversal)

후위 순회는 왼쪽 서브트리 - 오른쪽 서브트리 - 루트노드 순으로 재귀적 탐색을 진행한다.

H-I-D-E-B-JF-G-C-A

이진 트리(Binary Tree)

이진트리는 각 노드가 최대 2개 이하의 자식노드를 갖을 수 있으며, 자식이 공백이더라도 자식노드로 취급한다.

 

1.1 완전 이진 트리(Complete Binary Tree)

• 모든 노드가 왼쪽부터 생성된다.
• 마지막 레벨의 노드를 제외하고 모든 레벨이 완전히 채워져야 한다.
• 마지막 레벨은 꽉 차있진 않아도 되지만 왼쪽 노드 - 오른쪽 노드 순으로 채워져야 한다.
• 높이가 h인 완전 이진 트리의 총 노드 갯수는 2^h 이상 2^(h+1)개 미만이다.
• 완전 이진 트리는 배열을 사용해 효율적으로 표현 가능하다. 

1.2 전 이진 트리(Full Binary Tree)

• 전 이진트리는 모든 노드가 0개 또는 2개의 자식노드를 갖는 트리이다.

1.3 포화 이진 트리(Perfect Binary Tree)

• 포화 이진트리는 전 이진트리의 성질을 만족하며, 모든 레벨이 노드로 꽉 차 있어야 한다.
• 모든 Leaf Node가 동일한 깊이 또는 레벨을 갖는다.

이진 탐색 트리(Binary Search Tree)

데이터를 효율적으로 탐색 할 수 있게 하기 위해 이진 탐색 트리가 만들어졌다.

이진 탐색 트리의 특징으로는 

• left node에는 부모노드보다 작은 값이 들어간다.
• right node에는 부모노드보다 큰 값이 들어간다.

따라서 원하는 값을 찾을 때까지 노드값보다 찾고자하는 값이 작으면 왼쪽, 크면 오른쪽으로 움직이면 된다.