트리(Tree)

 

트리^Tree는 자료들이 리스트, 스택, 큐와 같은 1:1 관계의 선형 구조가 아니라 1:n 관계의 비선형 자료구조이다. 또한 계층 관계로 만들어진 계층형 자료구조^{Hierarchical Data Structure}이다.

---

노드^node - 트리의 원소

루트 노드^{root node} - 트리의 시작 노드(레벨 0)

간선^edge - 노드를 연결하는 선, 부모 노드와 자식 노드를 연결

형제 노드^{sibling node} - 같은 부모의 자식 노드들

조상 노드^{Ancestor node} - 간선을 따라 루트 노드까지 경로에 있는 모든 노드들

서브 트리^subtree - 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리

자손 노드^{child or descendant node} - 서브 트리에 있는 하위 레벨의 노드들

---

노드의 차수^{node degree} - 노드에 연결된 자식 노드의 수

트리의 차수^{tree degree} - 트리에 있는 노드의 차수 중에서 가장 큰 값

---

노드의 높이^{node height or depth} - 루트에서 노드에 이르는 간선의 수(노드의 레벨)

트리의 높이^{tree height or depth} - 트리에 있는 노드의 높이 중에서 가장 큰 값(최대 레벨)

---

포리스트^forest - 서브 트리의 집합

---

이진 트리^{Binary Tree} - 트리의 모든 노드의 차수를 2 이하고 제한하여 전체 트리의 차수가 2 이하가 되도록 정의

이진 트리의 특성

• 노드가 n개인 이진 트리는 항상 간선이 (n-1)개이다.
• 높이가 h인 이진 트리가 가질 수 있는 노드 개수는 최소 (h+1)개이며, 최대 (2^h+1-1)개이다.

 

 

이진 트리의 종류

---

1. 포화 이진 트리^{Full Binary Tree}

• 모든 레벨에 노드가 포화 상태로 차 있는 이진 트리
• 높이가 h일 때, 최대의 노드 개수인 (2^h+1-1)개의 노드를 가진 이진 트리
• 루트를 1번으로 하여 (2^h+1-1)까지 정해진 위치에 대한 노드 번호를 갖는다.

2. 완전 이진 트리^{Complete Binary Tree}

• 높이가 h이고 노드 수가 n개일 때, 노드 위치가 포화 이진 트리에서의 노드 1번부터 n번까지의 위치와 완전히 일치하는 이진 트리
• 완전 이진 트리에서는 (n+1)번부터 (2^h+1-1)번까지 노드는 모두 공백 노드

3. 편향 이진 트리^{Skewed Binary Tree}

• 높이가 h일 때, (h+1)개의 노드를 가지면서, 모든 노드가 왼쪽이나 오른쪽 중 한 방향으로만 서브 트리를 가지고 있는 트리

---

 

 

이진 트리의 순회^traversal

• 전위 순회^{preorder traversal} - D → L → R 순서로, 현재 노드를 방문하여 처리하는 작업 D를 가장 먼저 수행
• 중위 순회^{inorder traversal} - L → D → R 순서로, 현재 노드를 방문하여 처리하는 작업 D를 작업 L과 작업 R의 중간에 수행
• 후위 순회^{postorder traversal} - L → R → D 순서로, 현재 노드를 방문하여 처리하는 작업 D를 가장 나중에 수행

---

이진 탐색 트리^{Binary Search Tree} - 이진 트리를 탐색용 자료구조로 사용하기 위해 원소 크기에 따라 노드 위치를 정의한 것

---

AVL 트리^{Adelson-Velskii, Landis Tree}

• 대표적인 균형 이진 탐색 트리
• 각 노드에서 왼쪽 서브 트리의 높이 hL^{height of Left subtree}과 오른쪽 서브 트리의 높이 hR^{height of Right subtree}의 차이가 1 이하인 트리

AVL 트리의 특징

• 왼쪽 서브 트리 < 부모 노드 < 오른쪽 서브 트리의 크기 관계를 갖는다.
• 각 노드의 왼쪽 서브 트리 높이와 오른쪽 서브 트리 높이의 차이(hL-hR)를 노드의 균형 인수^{BF, Balance Factor}라 한다.
• 각 노드의 균형 인수로 {-1, 0, +1} 값만 가지게 함으로써 왼쪽 서브 트리와 오른쪽 서브 트리의 균형을 항상 유지함.

AVL 트리의 회전 연산

• AVL 트리에서 수행하는 삽입, 삭제 작업은 이진 탐색 트리에서의 삽입, 삭제 작업과 같고, 이후에 균형을 맞추어주는 재구성 작업이 추가되는데 이 작업은 회전^Rotation 연산을 통해 이루어진다.
• LL 회전 연산 - 삽입, 삭제 연산 후에 AVL 트리에 LL 유형의 불균형이 발생했을 때 적용
• RR 회전 연산 - 삽입, 삭제 연산 후에 AVL 트리에 LL 유형의 불균형이 발생했을 때 적용
• LR 회전 연산 - 삽입, 삭제 연산 후에 AVL 트리에 LR 유형의 불균형이 발생했을 때 적용
• RL 회전 연산 - 삽입, 삭제 연산 후에 AVL 트리에 RL 유형의 불균형이 발생했을 때 적용

 

---