[자료구조] 트리(Tree)

트리

트리는 노드로 이루어진 자료구조이며, 다음과 같은 형태를 갖는다.

예를 들어, 컴퓨터의 폴더 즉, 디렉토리를 예로 들 수 있다.

한 디렉 토리 안에는 여러 디렉토리가 들어있을 수 있고, 그 안에 또 여러 개의 파일들이 있을 수 있다.

트리 관련 용어

• 루트 노드(root node): 부모가 없는 노드로, 최상위 노드를 뜻한다. 위의 트리 예시에서 A에 해당한다.
• 단말 노드(leaf node): 자식이 없는 노드. C, D, F, G, H가 해당한다.
• 간선(edge): 각 노드를 연결하는 선(branch 라고도 한다.)
• 형제(sibling): 동일한 부모를 갖는 노드를 의미한다. C, D, E는 B라는 동일한 부모를 가졌으므로 형제이다.
• 차수(degree): 각 노드가 지닌 간선의 수이다.
• 트리의 차수(degree of tree): 트리의 최대 차수이다.
• 트리의 깊이, 높이(depth or height): 루트 노드로부터 가장 아래 있는 노드까지의 깊이를 의미한다. 위의 예시에서는 A~(F or G)까지가 가장 멀으므로 A - B - E - F or G 총 4의 깊이가 된다.

특징

1. 그래프(graph)의 한 종류로, 사이클이 없는 그래프이다.
2. 스택, 큐와 같은 선형 구조가 아닌 비선형 구조이다.
3. 계층 형태를 갖는다.
4. 노드가 N개이면 (N-1)개의 간선을 갖는다.
5. 모든 자식 노드는 하나의 부모 노드를 갖는다.

트리의 종류

트리의 종류에는 이진트리, AVL트리, B트리, 다원 탐색 트리 등 다양한 트리가 있지만, 이 중 이진 트리에 대해서만 알아보고자 한다.

1. 이진 트리(Binary Tree)
   이진 트리는 각 노드가 최대 2개의 자식 노드를 갖는 트리를 의마한다.
   

   

2. 완전 이진 트리(Complete Binary Tree)
   이진트리는 최대 2개의 자식 노드로 하나의 노드만을 자식 노드로 가질 수 있지만, 완전 이진 트리의 경우, 루트 노드와 단말 노드가 아닌 모든 노드는 2개의 자식 노드를 갖는다.
   또한 노드가 채워지는 순서는 부모 노드, 왼쪽 자식 노드, 오른쪽 자식 노드 순으로 전위 순회(preorder, root → left → right) 방식을 따른다.
   

   

3. 포화 이진 트리(Perfect Binary Tree)
   모든 노드가 0 또는 2개의 자식 노드를 갖고,
   모든 리프 노드가 같은 레벨에 있는 경우의 트리이다.(이것이 완전 이진 트리와의 차이점이다.)
   레벨이 3일 시, 2ⁿ - 1개의 노드를 갖는다.
   

   

4. 정 이진 트리(Full Binary Tree)
   각 내부 노드가 2개의 자식 노드를 갖는 순서화된 트리를 의미한다.
   

   

5. 편향 이진 트리(Sweked Binary Tree)
   모든 노드들이 한 방향으로만 편향된 트리를 의미한다.
   

   

6. 이진 탐색 트리(Binary Search Tree)
   이진트리의 구조에 데이터의 검색/삽입/삭제를 효율적으로 하기 위해 정렬의 개념이 추가된 트리이다.
   특징
   
   1. 각 노드의 왼쪽에는 자신보다 작은 데이터를 갖는 노드만이 있어야 한다.
   2. 각 노드의 오른쪽에는 자신보다 큰 데이터를 갖는 노드만이 있어야 한다.
   3. 중위순회(inorder, left→root →right) 시 순차적으로 데이터가 정렬된다.