트리(Tree) 🌲

• 자주 쓰는 자료구조인 리스트, 큐 등과 다르게, 트리는 계층적인 형태를 띈다.

• 즉 입력 받는 데이터 간의 상하관계가 존재하는데, 위에 있는 노드를 부모 노드, 그 아래의 최대 2개의 노드를 자식 노드라고 명칭한다.

(출처: https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html)

1. 루트 노드 (Root Node)
   • 이름 그대로 트리의 뿌리, 즉 트리의 시작점에 위치한 노드를 말한다.

2. 부모 노드 (Parent Node)
   • 자식 노드의 위에 있는 노드로, 최대 2개의 자식 노드를 거느린다.

3. 자식 노드 (Child Node)
   • 부모 노드의 아래에 위치하는 노드를 말한다. 두 자식 노드는 형제(자매)관계 Siblings 라 부를 수 있다.

4. 리프 노드 (Leaf Node)
   • 나뭇잎은 더 이상 다른 나무로 이어지지 않는 것처럼, 자식 노드가 존재하지 않는 노드를 말한다.

5. 부분 트리 (Sub-tree)
   • 전체 트리의 내부에 위치한 작은 하위 트리를 일컫는다.

6. 레벨 (깊이)
   • 특정 노드가 루트 노드로부터 떨어진 정도를 말한다.
   • 레벨은 0부터 시작한다.

7. 높이
   • 레벨과 비슷한 개념이지만, 특정 노드를 대상으로 말한다기보다는 전체 트리를 기준으로 말할 때 사용한다.
   • Ex) 위 트리는 3의 높이를 갖고 있다.

이진 트리 🌳

• 이진 트리란, 각 노드가 최대 2개의 자식노드를 거느릴 수 있는 트리이다.

• 이진 트리는 쓰임새가 다양하고 용이해, 트리를 사용할 때는 일반적으로 이진 트리를 이용한다.

이러한 이진 트리에는 가진 모양에 따라 3가지의 종류로 나뉜다.

1. 정 이진 트리

(출처: https://www.wikiwand.com/en/Binary_tree)

• 정 이진 트리는 모든 노드가 0개 혹은 2개의 자식 노드를 갖고 있는 것을 말한다.

2. 포화 이진 트리

(출처: https://math.stackexchange.com/questions/2207518/determine-the-depth-and-number-of-node-in-perfect-binary-tree-if-index-number-gi)

• 포화 이진 트리는 모든 레벨의 노드들이 빠짐없이 차 있는 형태를 말한다.

3. 완전 이진 트리

(출처: https://www.wikiwand.com/en/Binary_tree)

• 완전 이진 트리는 마지막 레벨을 제외한 모든 레벨들에서는 노드들이 꽉 차 있으며, 마지막 레벨의 노드는 왼쪽부터 차례대로 채워진 형태를 말한다.

• 가장 많이 사용되는 방식으로, 우선 순위 큐 또는 힙 큐에서도 이와 같은 형태를 유지해야만 한다.

완전 이진 트리는 다음과 같은 특징들이 존재한다.

① 전체 노드의 개수를 통해서 트리의 높이를 구할 수 있다.

완전 이진 트리는 각 층별로 최대 2^레벨 만큼의 노드를 갖고 있다.

• 레벨 0: 2^0 = 1개
• 레벨 3: 2^3 = 8개

그러므로 높이가 3인 완전 이진 트리는 최대 1 + 2 + 4 + 8 = 15개의 노드를 가질 수 있다.

이와 비슷한 방식으로 최소 노드 또한 구할 수 있다.
최소 노드를 가지기 위해서는, 마지막 레벨에서 노드를 1개만 가져야 한다.

• 레벨 1: 2^0 + 1 = 2개
• 레벨 2: 2^0 + 2^1 + 1 = 4개
• 레벨 3: 2^0+ 2^1 + 2^2 + 1 = 8개

이를 통해서 높이가 3인 완전 이진 트리의 노드 개수 범위는 2^3인 8부터 2^4 - 1 15까지인 것을 알 수 있다.

이는 전체 노드 개수에 log2()를 씌운 후에 그보다 작은 정수 중 가장 큰 값에도 해당한다.

👉 python에서는 int(math.log2(15)) 이와 같이 3을 구할 수 있다.

👉 높이가 4인 완전 이진 트리의 전체 노드 개수 범위는?: 2^4인 16개 ~ 2^5 - 1인 31개

👉 어떤 완전 이진 트리의 전체 노드 개수가 64개라면, 이 트리의 높이는 몇인가?: log2(64) = 6이므로 높이는 6

② 리프 노드의 개수를 통해서 트리의 높이를 구할 수 있다.

리프 노드의 개수를 구한 후에, log2()를 씌운 후 올림하면 높이를 구할 수 있다.

높이가 2인 경우에 모든 노드가 꽉 차있다면, 리프 노드는 4개가 존재할 것이다.

여기서 가장 왼쪽의 노드에서 자식 노드가 2개 생긴다고 가정하면, 리프 노드는 레벨2에서 3개, 레벨3에서 2개가 존재해 총 5개가 된다.

math.ceil(math.log2(5)) 은 3이므로 리프 노드를 통해 높이가 3인 것을 알 수 있다.

하지만 이 방법은 트리가 정 이진 트리의 형태인 경우에만 가능하다.

👉 만약 위와 같은 트리에서 자식 노드가 1개만 생성된다면, 리프 노드는 그대로 4개가 존재하게 되므로 높이에 변화가 생기지 않기 때문이다.

③ 부모 노드의 인덱스를 통해서 자식 노드의 인덱스를 구할 수 있다.

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

위 트리를 리스트로 나타내면, [None,10,5,15,1,7,12,20]이 된다.

• index 2에 해당하는 5는 1과 7을 자식 노드로 갖는데, 이는 index 4와 index 5에 해당한다.

👉 위의 공식이 성립함을 알 수 있다.

④ 자식 노드의 인덱스를 통해서 부모 노드의 인덱스를 구할 수 있다.

부모 노드 인덱스 = 자식 노드 인덱스 // 2

• index 4에 위치한 1과 index 5에 위치한 7의 부모 노드인, 5는 index 2에 위치해있다.

👉 위의 공식이 성립함을 알 수 있다.

---

참고한 블로그