알고리즘 4주차 - 트리

트리

• 뿌리와 가지로 구성되어 거꾸로 세워 놓은 나무처럼 보이는 계층형 비선형 자료 구조

• 선형구조와 다르게 계층적 혹은 망으로 구성

• 자료를 표현하는데 초점이 맞춰져 있음

• 컴퓨터 폴더 구조와 같이 하나의 밑에 밑에 있는 계층적 구조가 중요하다면 트리를 쓰는 것이 맞음

• 큐, 스택 같은 경우는 선형구조인데 자료를 구성하고 있는 데이터들이 순차적으로 나열시킨 형태이다.

• 자료를 저장하고 꺼내는 것 에 초점이 맞춰져 있음

💡

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

트리의 종류

• 트리의 종류로는 이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, red-black 트리), 이진 힙(최대힙, 최소힙) 등이 있지만 수업에서는 이진과 완전 이진만 다룸

이진 트리(Binary Tree)

• 각 노드가 최대 2개의 자식을 가진다

• 즉 무조건 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

# 출처: 스파르타 코딩클럽

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

• 트리 구조를 표현하는 방법은 1. 직접 클래스를 구현해서 사용 2. 배열로 표현 이와 같이 2개가 있음

• 트리구조를 배열에 저장하는 경우는 완전 이진 트리 를 쓰면 가능함

• 완전 이진트리는 왼쪽부터 데이터가 쌓이기에 순서대로 배열에 표현

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

+ 0번째 인덱스는 사용하지 않음. None값을 0번째 인덱스에 넣어서 시작

# 출처: 스파르타코딩클럽

• 그렇다면 해당 배열을 보고 다시 구조화 파악은 어떻게 할까?

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

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

이를 다시 생각해보면
[None, 8, 6, 3, 4, 2, 5] 는
8 밑에 6, 3 이 있고, 6, 3 밑에 4, 2, 5가 있는 완전 이진 트리

# 출처: 스파르타코딩클럽

완전 이진 트리의 높이

• 트리의 높이(Height)는 루트 노드 → 리프 노드까지의 길

      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인데 모든 노드가 꽉 차 있는 완전 이진 트리의 노드의 개수는? 답: 2^h - 1

이 때 최대 노드의 개수가 N이라면, h 는 뭘까

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

라고 할 수 있습니다!
즉! 완전 이진 트리 노드의 개수가 N일 때 최대 높이가 log_2(N+1) 이므로

이진 트리의 높이는 최대로 해봤자 O(log(N))  

# 출처: 스파르타코딩클럽