자료구조 트리에 대해서 배워보자

📚 트리의 정의

 

 

 

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

 

 

 

 

트리는 대표적인 사용 예시는 컴퓨터의 폴더 구조이다.

파일이 어느 경로에 있는지 그 경로에는 어떤 폴더들이 포함되는지 나타내야 하기 때문이다.

트리의 구조는 다음과 같다

 

🧬 트리의 구조

 

https://heung-bae-lee.github.io/2020/05/02/data_structure_06/

 

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

📝 이진 트리

 

트리의 대표적인 종류 중 하나인 이진트리의 특징은

각 노드가 최대 두 개의 자식을 가진다.

Child Node가 3개 이상 가질 수 없으며

무조건 0,1,2 개로만 있어야 한다.

 

 

이렇게 자식 노드가 3개이면 이진 트리가 아니다

 

 

📝 완전 이진 트리

 

완전 이진트리의 특징은 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입해야 하는 것이다. 

 

최하단 노드인 2가 아닌 8에서 부터 노드를 삽입했으므로 완전 이진 트리가 아니다.

 

완전 이진트리의 표현법은 대체로 배열로 표현한다

 

 

#    10
#  5    17
# 1 6  14 21

tree = [None, 10, 5, 17, 1, 6, 14, 21]
# 첫 인덱스는 None으로 비워준다. 계산하기 편하기 위해 일부터 비워두는 것이다.

 

 

완전 이진트리라는 전제 하에

왼쪽에서부터 오른쪽으로

위에서 아래로 하나씩 차례대로 넣는 것이다.

이런 식으로 배열에 넣게 되면 부모와 자식 사이의 인덱스 관계가 공식에 따라 성립한다.

 

• 현재 인덱스 * 2 -> 왼쪽 자식의 인덱스
• 현재 인덱스 * 2 + 1 -> 오른쪽 자식의 인덱스
• 현재 인덱스 // 2 -> 부모의 인덱스
  
  // 연산자는 왼쪽 변수를 오른쪽 변수를 나눈 후 소숫점을 제거하는 것이다.

☝ 즉 현재 인덱스가 3인 17은

3 // 2 = 1

인덱스가 1인 10의 자식 노드이다

 

☝ 현재 인덱스가 2인 5는

2 * 2 = 4

인덱스가 4인 1의 부모 노드(왼쪽 자식)이다.

 

☝ 현재 인덱스가 2인 5는

2 * 2 + 1= 5

인덱스가 5인 6의 부모 노드(오른쪽 자식)이다.

 

 

📏 완전 이진 트리의 높이

 

각 level을 k라고 한다면 각 level에 최대로 들어갈 수 있는 노드의 개수는 2^k 개수 임을 알 수 있다.

 

 

 

level k 에선 2^k 만큼의 노드가 있는 것이다.

 

만약 높이가 h라면 모든 노드의 개수는 몇 개 일까?

 

1 + 2¹ + 2² + 2³ + ... + 2^h 이니

2^(h+1) - 1 이 된다.

 

높이가 h일 때 최대 노드의 개수는 2(h + 1) - 1 개

 

최대 노드의 개수가 N이라면

2(h + 1) -1 = N

h = log₂(N+1) - 1

 

완전 이진트리 노드의 개수가 N일 때 최대 높이가 log₂(N+1) - 1 이므로

어떤 트리의 노드를 모두 탐색해야 되는 경우 O(log(N)) 이 된다