자료구조 4주차_트리

자료구조 4주차_트리

---

📌 선형구조

• 큐(Queue), 스택(Stack)
• 데이터들을 순차적으로 나열시킨 형태
• 자료를 꺼내는 것에 초첨이 맟춰져 있음

 

📌 비선형구조

• 트리
• 데이터가 계층적 혹은 망으로 구성되어 있음
• 자료 표현에 초점이 맞춰져 있음

 

---

트리

 

📌 계층형 구조

트리, [출처 : 스파르타 코딩클럽]

• Root Node : 트리 맨 위에 있는 노드
• Level :  노드의 깊이
• Parent Node : 어떤 노드의 상위 레벨에 연결된 노드
• Child Node : 어떤 노드이 하위 레벨에 연결된 노드
• Leaf Node(Terimnal Node) : Child Node가 하나도 없는 노드
• Sibling : 동일한 Parent Node를 가진 노드
• Depth : 트리에서 Node가 가질 수 있는 최대 Level

---

이진 트리(Binary Tree)

 

자식노드를 최대 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)

자식노드를 최대 3개 가지면, 이진 트리가 아니다.

---

완전 이진 트리(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번째 인덱스는 사용되지 않습니다.

      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를 넣으면 됩니다!

 [None, 8, 6, 3, 4, 2, 5] 라는 배열이 됩니다.


1. 현재 인덱스 * 2 -> 왼쪽 자식의 인덱스
2. 현재 인덱스 * 2 + 1 -> 오른쪽 자식의 인덱스
3. 현재 인덱스 // 2 -> 부모의 인덱스

예를 들어서 1번째 인덱스인 8의 왼쪽 자식은 6, 오른쪽 자식은 3 입니다.
그러면 1 * 2 = 2번째 인덱스! 6!
그러면 1 * 2 + 1 = 3번째 인덱스! 3! 입니다!
부모를 찾아보면, 3 // 2 = 1번째 인덱스 8 이므로 부모를 찾을 수 있습니다.

 

완전 이진 트리 각 레벨에 노드가 꽉 차 있다면, 

레벨 k에 최대 노드 갯수는 2^k 개.

      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 개

 

1+2^1 = 3 = 2^2-1

1+2^1+2^2 = 7 = 2^3-1

1+2^1+2^2+2^3 = 15 = 2^4-1

1+2^1+2^2+2^3+2^4 = 31 = 2^5-1

                 ↓

높이가 h인 완전 이진 트리의 모든 노드의 갯수 : 2^(h+1) -1

 

그렇다면, 높이가 h일때 최대 노드의 갯수를 N이라고 한다면, h는?

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

 

이진 트리의 높이는 최대 O(log(N))  임!