트리

🌲 트리

데이터의 상-하 관계를 저장하는 자료 구조 => 계층적 관계

root 노드(뿌리 노드): 트리의 시작 노드
부모 노드: 특정 노드의 직속 상위 노드
자식 노드: 특정 노드의 직속 하위 노드, 부모 노드와 반대 개념
형제 노드: 같은 부모를 같는 노드
leaf 노드(잎/말단 노드): 자식 노드를 갖고 있지 않은, 가장 말단에 있는 노드

깊이: 특정 노드가 root 노드에서 떨어져 있는 거리
레벨: 깊이 + 1
높이: 트리에서 가장 깊이 있는 노드의 깊이

부분트리(sub-tree): 현 트리의 일부분을 이루고 있는 더 작은 트리

---

✌ 이진 트리

각 노드가 최대 2개의 자식 노드를 갖을 수 있는 트리

💻 이진 트리 구현

class Node:
    """이진 트리 노드 클래스"""

    def __init__(self, data):
        """데이터와 두 자식 노드에 대한 레퍼런스를 가짐"""
        self.data = data
        self.left_child = None
        self.right_child = None   

"""노드 인스턴스 생성"""
root_node = Node(2)
node_B = Node(3)
node_C = Node(5)
node_D = Node(7)
node_E = Node(11)

"""B와 C를 root 노드의 자식으로 지정"""
root_node.left_child = node_B
root_node.right_child = node_C

"""D와 E를 B 노드의 자식으로 지정"""
root_B.left_child = node_D
root_B.right_child = node_E

🧱 이진 트리의 종류

• 정 이진 트리(Full Binary Tree): 모든 노드가 2개 또는 0개의 자식을 갖는 이진 트리

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

  1. 마지막 레벨 직전의 레벨까지는 모든 노드들이 다 채워진 이진 트리

  2. 마지막 레벨의 노드들은 다 채워질 필요는 없지만, 왼쪽부터 오른쪽 방향으로 노드들이 채워져야 함

     완전 이진 트리의 높이: 완전 이진 트리 안에 저장된 노드가 n개라면, 높이는 항상 lg(n)에 비례함

     

• 포화 이진 트리(Perfect Binary Tree): 모든 레벨이 빠짐없이 다 노드로 채워져있는 이진 트리
  정 이진 트리와 완전 이진 트리의 특성을 가짐
  높이에 따라 노드의 수가 고정되는 특성이 있음, n = 2^(h + 1) - 1 (노드 수 n, 트리 높이 h)

---

💻 완전 이진 트리 구현

파이썬의 리스트로 구현하기

0번째 인덱스를 None으로 두고, 1번째 인덱스부터 root 노드를 시작으로, 왼쪽에서 오른쪽 방향 순으로 리스트에 저장하면 됨
ex) complete_binary_tree = [None, 1, 5, 12, 11, 9, 10, 14, 2, 10]

마지막 레벨 직전의 레벨까지는 노드들로 가득 차 있으며, 마지막 레벨은 왼쪽에서 오른쪽 방향으로 노드들이 채워져 있으므로, 부모 노드와 자식 노드를 손쉽게 찾을 수 있음!!

🔎 자식 노드 찾는 방법

• 특정 부모 노드의 왼쪽 자식 노드 찾기 => 부모 노드의 인덱스에 2를 곱해준 값의 인덱스 노드
• 특정 부모 노드의 오른쪽 자식 노드 찾기 => 부모 노드의 인덱스에 2를 곱해주고 1을 더해준 값의 인덱스 노드
  ex) 2번째 노드(노드 5)의 왼쪽 자식 노드 => 2 * 2 = 4, 인덱스 4의 노드, 4번째 노드(노드 11)

🔎 부모 노드 찾는 방법

• 자식 노드의 인덱스에 2를 나눈 값의 인덱스 노드, (자식 노드의 인덱스가 홀수라면 2로 나눈 후 정수 값만!)