[자료구조] 트리 with Python

💡 트리

: 트리는 Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조이다.

Level : 루트노드부터 현재 노드까지의 깊이

Height(높이)

: 트리에서 노드가 가질 수 있는 최대 Level

: 해당 트리의 높이는 3이다.

 

 

💡 이진트리(Binary Tree)

: 이진트리는 노드의 최대 브랜치가 2인 트리이다.

 

Q1. 이진트리에 있는 각 레벨의 최대 노드의 개수는?

레벨이 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 개

 

Q2. 높이가 h이고 꽉 차있는 이진 트리라면, 모든 노드의 개수는?

 1 + 2^1 + 2^2 + 2^3 + 2^4 ..... 2^h 

즉, 이를 수식으로 표현하면 2^{h+1} -1 이다.

 

Q3. 최대 노드의 개수가 N이라면, 트리의 높이 h는?

2^{h+1} -1  = N → h =  log_{2}(N+1)-1 

 

 

💡 완전 이진 트리(Complete Binary Tree)

: 완전 이진 트리는 최하단 왼쪽 노드부터 차례대로 채워져있는 이진 트리이다.

 

[ 완전 이진 트리 구현 : 배열 ]

완전 이진 트리의 경우, 클래스로 구현할 수도 있고 배열로도 구현할 수 있다.

다음과 같은 트리가 있다고 가정하자.

해당 트리는 [None, 8, 6, 3, 4, 2, 5] 라는 배열로 표현할 수 있다.

  8         Level 0

 6 3        Level 1

4 2 5      Level 2 

 

배열에서 트리로 접근하려면 다음과 같은 규칙을 가잔다.

1. 왼쪽 자식의 인덱스 : 현재 인덱스 * 2 

2. 오른쪽 자식의 인덱스 : 현재 인덱스 * 2 + 1 

3. 부모의 인덱스 : 현재 인덱스 // 2 

 

예를 들어서 1번째 인덱스인 8의 왼쪽 자식은 6, 오른쪽 자식은 3 입니다.

1. 왼쪽 자식 찾기    : 1 * 2 = 2,  인덱스 2의 값 6.

2. 오른쪽 자식 찾기 : 1 * 2 + 1 = 3,  인덱스 3의 값 3.

3. 인덱스 3의 부모 찾기 : 3 // 2 = 1,  인덱스1의 값 8.

 

 

 

💡 그 외의 트리 종류

- 이진 탐색 트리(Binary Search Tree) : 이진 탐색이 동작할 수 있도록 고안된 변형된 이진 트리

 

- 힙 : 데이터에서 최대/최소값을 빠르게 찾기 위해 고안된 변형된 완전 이진트리

 

- 힙 vs 이진 탐색트리

    - 공통점 : 둘다 이진트리

    - 차이점 

        1. 목적

        이진 탐색트리는 특정 노드를 빠르게 탐색하기 위한 구조, 힙은 최대 혹은 최소값을 탐색하기 위한 구조

        2. 최대/최소 값의 위치

        이진 탐색트리는 최대값이 우 최하단, 최소값은 좌 최하단이지만 힙은 최상단에 최대/최소 값이 위치

 

💡 완전 이진트리 예시

[HSAT 5회 정기 코딩 인증평가 기출] 업무 처리

어떤 부서의 업무 조직은 완전이진트리 모양이다. 즉, 부서장이 루트이고 부서장 포함 각 직원은 왼쪽과 오른쪽의 부하 직원을 가진다. 부하 직원이 없는 직원을 말단 직원이라고 부른다. 모든 말단 직원은 부서장까지 올라가는 거리가 동일하다. 조직도 트리의 높이는 H이다. 아래는 높이가 1이고 업무가 3개인 조직도를 보여준다.

 

 

업무는 R일 동안 진행된다. 처음에 말단 직원들만 각각 K개의 순서가 정해진 업무를 가지고 있다. 각 업무는 업무 번호가 있다. 각 날짜에 남은 업무가 있는 경우, 말단 직원은 하나의 업무를 처리해서 상사에게 올린다. 다른 직원들도, 대기하는 업무가 있는 경우 업무를 올라온 순서대로 하나 처리해서 상사에게 올린다. 단, 홀수 번째 날짜에는 왼쪽 부하 직원이 올린 업무를, 짝수 번째 날짜에는 오른쪽 부하 직원이 올린 업무를 처리한다.

 

부서장이 처리한 일은 완료된 것이다. 업무를 올리는 것은 모두 동시에 진행한다. 따라서 그날 올린 업무를 상사가 처리하는 것은 그 다음날에야 가능하다.

 

부서의 조직과 대기하는 업무들을 입력 받아 처리가 완료된 업무들의 번호의 합을 계산하는 프로그램을 작성하라.

 

입력형식

첫 줄에 조직도의 높이 H, 말단에 대기하는 업무의 개수 K, 업무가 진행되는 날짜 수 R이 주어진다.

그 다음 줄부터 각각의 말단 직원에 대해 대기하는 업무가 순서대로 주어진다.

제일 왼쪽의 말단 직원부터 순서대로 주어진다.

 

출력형식

완료된 업무들의 번호 합을 정수로 출력한다.

 

문제 링크 :

Softeer HSAT 5회 정기 코딩 인증평가 기출, 난이도 3

https://softeer.ai/practice/info.do?idx=1&eid=1256

Softeer

 

 

 

출처

PlanB의 백엔드 엔지니어링 블로그: Tree