트리(Tree)

🏃‍♂️ 트리의 개념

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

트리는 한개 이상의 노드(트리의 구성요소(로 이루어진 유한 집합이고, 루트(root) 노드와 서브트리(subtree)로 구분지을 수 있다. 트리는 값을 가진 노드와 노드 들을 연결해주는 간선 (edge)로 구성되어 있다.

트리 용어

• 루트 노트(A) : 계층 구조에서 가장 높은 곳에 있는 노드

• 부모 노드 - 자식노드 : D는 H의 부모노드가 되고, H는 D의 자식 노드가 된다.

• 형제 관계 : H 와 I, F 와 G는 각각 형제 관계 이다.

• 단말 노드(Leaf Node, or terminal node) : 자식 노드가 없는 노드 , 비단말 노드의 반대

• 차수(degree) : 자식 노드의 개수 , A의 경우 차수가 2, E의 경우 차수가 1 이다. 단말노드는 차수가 0이다.

• 레벨(level) : 트리의 각층에 번호를 매긴다. 루트의 레벨은 1이 되고, 한층씩 내려갈 수록 1씩 증가한다.

🔬 이진트리

모든 노드가 2개의 서브 트리를 가지고 있는 트리를 이진트리 (binary tree)라고 한다.

모든 노드는 최대 2개까지의 자식 노드가 존재 할 수 있고, 모든 노드의 차수가 2 이하가 된다.

정의 : 공집합이거나 루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의 된다. 이진 트리의 서브 트리들은 모두 이진 트리여야 한다.

이진트리의 성질

• $n$ 개의 노드를 가진 이진트리는 정확하게 $n-1$ 개의 간선을 가진다.

         ⇒ 루트를 제외하고 모두 정확히 하나의 부모노드만 갖기 때문이다.

• 높이가 $h$ 인 이진트리는 최소 $h$개의 노드를 가지고, 최대 $2^h -1$ 개의 노드를 가진다.

• $n$개의 노드를 가지는 이진트리의 높이는 최대 $n$이거나 최소 $[log_2(n+1)]$이 된다.

이진트리의 분류

포화 이진 트리 (full binary tree)

• 트리의 각 레벨에 노드가 꽉 차 있는 이진 트리
• 높이 $k$인 포화 이진트리는 정확하게 $2^k-1$개의 노드를 가진다.

완전 이진 트리 (complete binary tree)

• 높이가 $k$일때, 레벨 1부터 $k-1$까지 노드가 모두 채워져 있고, 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진 트리
• 마지막 레벨에서 노드가 꽉차있지 않아도 되지만, 노드의 중간에 빈곳이 있어서는 안된다.
• 포화 이진트리는 완전 이진트리 이다.

기타 이진 트리

이진트리의 순회

이진트리도 데이터를 저장하기 위한 자료 구조이고, 데이터는 노드의 데이터 필드를 이용하여 저장된다. 이진 트리를 순회 한다는 것은 이진 트리에 속하는 모든 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것을 의미한다.

이진트리 순회방법은 전위, 중위, 후위 3가지 방법이 있다.

루트를 방문하는 작업을 V, 왼쪽 서브트리방문을 L, 오른쪽 서브트리 방문을 R이라 하자

전위순회(VLR) : 루트 먼저 방문 → 왼쪽 서브트리 방문 → 오른쪽 서브트리 방문

중위순회(LVR) : 왼쪽 서브트리 방문 → 루트 방문 → 오른쪽 서브트리 방문

후위순회(LRV) : 왼쪽 서브트리 방문 → 오른쪽 서브트리 방문 → 루트 방문

레벨 순회 : 각 노드를 레벨 순으로 검사하는 순회 방법 (간접적으로 큐 사용)

🔗 참조한 사이트

⌜C언어로 쉽게 풀어쓴 자료구조⌟ 개정3판, 천인국, 생능출판

https://gyoogle.dev/blog/computer-science/data-structure/Heap.html