빅데이터 자료구조 - 10주차

이진트리의 개념

: 대표적인 비선형 자료구조로 각 노드가 최대 두 개의 자식을 가지는 트리 구조

 

이진트리의 요소

- Root : 트리의 시작점. 부모가 없음

- Leaf : 자식이 없는 트리의 최하단

- Internal : 1개 이상의 자식을 가진 노드

- Sibling : 같은 부모를 공유하는 노드

- Subtree : 어떤 노드를 루트로 하는 트리

- Height : 루트에서 가장 리프까지의 깊이

- Level : 루트로부터 해당 노드까지의 거리

- Degree : 해당 루트가 가진 노드의 개수

 

 

트리의 특징

- 트리는 하나의 루트 노드를 가진다

- 루트 / 리프는 0개 이상의 자식/부모 를 가진다

- 노드와 노드는 Edge로 이어져 있다

- 트리는 순회구조(Cycle)와 자기순회(Self-Loop)가 존재하지 않음

 

 

이진트리의 구조의 예시

이진트리의 구조 예시

 

자식이 2개 / 1개 / 0개  모두 가능

 

 

이진트리의 종류

1. 일반 트리

2. Binary Tree

3. Full BT

4. Perfect BT

5. Complete BT

6. Skewed BT

7. Balance BT

 

1. 일반 트리 

- 부모 자식 관계만 있음. 정해진 규칙 없음

- 임의의 개수로 자식 노드를 가질 수 있음

- 배치 순서X , 정렬 불가

- HTML DOM 구조가 이러함

 

2. Binary Tree = 일반 이진 트리

- 최대 2개의 자식 노드(Left, Right)를 가질 수 있음. 0개의 자식 노드를 가질 수도 있다는 뜻임

- 자식 노드를 n개 가진다고 할 때, 해당 트리의 최대 Height는 n임

- 데이터를 조회하는 순서가 있음

  1) Pre-order (전위 순회)

  2) In-order (중위 순회)

  3) Level-order (후위 순회)

 

3. Full Binary Tree = 전 이진 트리

- 자식 노드의 개수가 0개 또는 2개

- 리프 노드를 제외한 모든 노드가 두 개의 자식 노드를 가진다

- L = I + 1  (리프 노드의 개수 = 내부 노드의 개수 + 1)

FBT

 

 

 

4. Perfect Binary Tree = 포화 이진 트리

- 모든 내부 노드가 2개의 자식 노드를 가지고 있다

- 모든 리프 노드들이 형제관계이다 = 같은 레벨이다

- 높이가 h일때, (노드의 수) = 2^h

PBT

 

 

5. Complete Binary Tree = 완전 이진 트리 

- 마지막 레벨을 제외한 나머지 노드가 모두 2개임

- 마지막 레벨이 왼쪽부터 채워진 형태가 CBT

- 가질 수 있는 최대 노드의 개수는 2^h-1

- Heap 구현에 이상적

CBT

 

6. Skewed Binary Tree = 편향 이진 트리

- 한쪽 방향으로만 자식노드가 존재하는 트리

- Left / Right Skewed Binary Tree가 존재

- 실질적으로 선형리스트와 가장 흡사

편향 이진 트리

 

 

7. Balanced Binary Tree = 균형 이진 트리

- 모든 노드의 왼 / 오 서브트리의 높이 차가 일정 기준 이하

 

 

# CBT의 간단 구현

1. TreeNode() 클래스 생성

2. 루트노드 생성 + 데이터 값 넣기

3.  왼쪽 자식 노드 생성 + 데이터 값 넣기 + 부모 왼쪽 노드 = 자식 노드 선언

4. 위의 내용을 마지막 리프노드까지 반복

5. print.......노가다 print................

 

class TreeNode():

  def __init__(self):

    self.left = None

    self.data = None

    self.right = None

root = TreeNode()

root.data = "화사"

node2 = TreeNode()

node2.data = "솔라"

root.left = node2

node3 = TreeNode()

node3.data = "문별"

root.right = node3

node4 = TreeNode()

node4.data = "휘인"

node2.left = node4

node5 = TreeNode()

node5.data = "쯔위"

node2.right = node5

node6 = TreeNode()

node6.data = "선미"

node3.left = node6

print(root.data ,end='')

print()

print(root.left.data, root.right.data, end=' ')

print()

print(root.left.left.data, root.left.right.data, root.right.left.data, end=' ')

 

 

이진트리의 순회 순서

1. 전위 순회

- PLR

- 위에서 아래로 내려가는 모양새

 

2. 중위 순회

- LPR

- 아래/위/아래를 훑는 모양새

 

3. 후위 순회

- LRP

- 아래를 다 훑고 위를 올라가는 모양새

 

4. 레벨 순회

- 노드의 레벨에 따라 순회

- 가로로 한 줄씩 훑는 모양