[자료 구조] 트리 (Tree)

트리란?

• 큐 (Queue), 스택 (Stack) -> 선형 구조 : 데이터들을 순차적으로 나열 / 자료를 저장하고 꺼내는 것에 초점
• 트리 (Tree) -> 비선형 구조 : 데이터가 계층, 망으로 구성 / 표현에 초점

트리 용어

• Node: 트리에서 데이터를 저장하는 기본 요소
• Root Node: 트리 맨 위에 있는 노드
• Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
• Parent Node: 어떤 노드의 상위 레벨에 연결된 노드
• Child Node: 어떤 노드의 하위 레벨에 연결된 노드
• Leaf Node(Terminal Node): Child Node가 하나도 없는 노드 (제일 끝)
• Sibling: 동일한 Parent Node를 가진 노드
• Depth: 트리에서 Node가 가질 수 있는 최대 Level

트리의 종류

이진트리

• 각 노드가 최대 두 개의 자식을 가지는 트리
• 하위 노드가 3개 이상일 수 없다. 무조건 0,1,2개

      o      Level 0 
    o o o    Level 1
   o  o  o   Level 2 # 이진 트리(X)

      o      Level 0 
    o   o    Level 1
   o o o     Level 2 # 이진 트리(O)

완전 이진 트리 (Complete Binary Tree)

• 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입해야 한다

      o      Level 0
    o   o    Level 1
     o o     Level 2  # -> 이진 트리 O 완전 이진 트리 X

      o      Level 0
    o   o    Level 1
   o o o     Level 2  # -> 이진 트리 O 완전 이진 트리 O

완전 이진 트리를 배열로 표현

트리 구조를 표현하는 방법

• 직접 클래스 구현
• 배열로 표현 -> 완전 이진 트리를 쓰는 경우에 가능!
  • 왼쪽부터 데이터가 쌓이므로, 이를 순서대로 배열에 쌓으면서 표현

완전 이진 트리 배열로 표현하기

• 트리를 구현할 때는 편의성을 위해 0번째 인덱스는 사용되지 않음
• 그래서 None 값을 배열에 넣고 시작한다. [None]

      8      Level 0 -> [None, 8] 첫번째 레벨의 8
    6   3    Level 1 -> [None, 8, 6, 3] 다음 레벨인 6, 3
   4 2 5     Level 2 -> [None, 8, 6, 3, 4, 2, 5] 다음 레벨인 4, 2, 5

• 8의 자식 6,3 / 6의 자식 4,2 / 3의 자식 5
• 배열 = [None, 8, 6, 3, 4, 2, 5]

1. 왼쪽에 있는 자식의 인덱스 : 현재 인덱스 * 2
   • 8 : 1번 / 6 : 1 * 2 = 2번
   • 6 : 2번 / 4 : 2 * 2 = 4번
2. 오른쪽 자식의 인덱스 : 현재 인덱스 * 2 + 1
   • 8 : 1번 / 3 : 1 * 2 + 1 = 3번
   • 6 : 2번 / 2 : 2 * 2 + 1 = 5번
3. 부모 인덱스 : 현재 인덱스 // 2
   • 3 : 3번 / 3 // 2 = 1번 : 8
   • 👉 부모를 찾을 수 있다!

완전 이진 트리의 높이

트리의 높이
👉 루트 노드부터 가장 아래 리프 노드까지의 길이

높이가 2인 트리

      o      Level 0  # 루트 노드
    o   o    Level 1
   o o o     Level 2  # 가장 아래 리프 노드

이 트리의 높이는 ? 2 - 0 = 2!

각 레벨에 노드가 꽉 차 있는 경우

      1            Level 0 -> 1개
    2   3          Level 1 -> 2개 
   4 5 6 7         Level 2 -> 4개
 8 9....... 14 15  Level 3 -> 8개 
                   Level k -> 2^k 개

👉 레벨이 k라면, 각 레벨에 최대로 들어갈 수 있는 노드의 개수는 2^k이다.

노드가 꽉 찬 완전 이진 트리의 모든 노드 개수

• 높이 h
• 각 레벨k 의 노드 2^k개

레벨은 1, 2, 3, ... , h 이므로 모든 노드의 개수는
1 + 2^1 + 2^2 + 2^3 + 2^4 + ... + 2^h
= 2^(h+1) - 1

👉 높이가 h라면, 최대 노드 개수는 2^(h+1) -1​개가 된다.

최대 노드 개수가 N이라면 h는?

2^(h+1) -1 = N
→ h = log_2(N+1)-1

👉 완전 이진 트리 노드의 갯수가 N일 때, 높이는 최대 O(log(N))