[SW 정글 13일차] 트리 구조와 이진 트리

1. 트리 구조

트리 구조는 데이터 사이의 계층 관계를 표현하는 자료 구조로 노드(node)와 가지(edge)로 구성되어있다.

간단한 트리 구조를 아래의 그림으로 표현해 보았다.

그림을 보며 각각의 단어들이 어떠한 것을 뜻하는지 알아보자.

- 루트(root): 트리의 가장 위쪽에 있는 노드를 뜻하며 트리 하나에 루트는 오직 1개만 존재한다.

- 리프(leaf): 리프는 자기 자신으로부터 더 이상 가지가 뻗어나가지 않는 노드를 의미한다. 리프는 다른 말로 단말 노드, 외부 노드라고도 한다.

- 비단말 노드(non-terminal node): 비단말 노드는 트리 내에서 리프를 제외한 노드를 의미한다. 다른 말로 내부 노드라고도 한다.

- 자식 노드(child node): 노드와 노드가 가지로 연결되어있을 때 아래쪽 노드를 자식(child) 노드라고 한다.

위 그림에서 보면 Y와 Z가 가지로 연결되어있는데 이 때에 Z를 자식 노드라고 한다.

- 부모 노드(parent node): 노드와 노드가 가지로 연결되어있을 때 위쪽 노드를 부모(parent) 노드라고 한다.

위 그림에서 보면 Y와 Z가 가지로 연결되어있는데 이 떄에 Y를 자식 노드라고 한다.

- 레벨(level): 레벨은 루트에서 얼마나 멀리 떨어져 있는지를 나타내는 척도이다.

루트를 레벨 0으로 잡고 아래로 한 칸씩 내려갈수록 레벨 1, 레벨 2, ...로 증가하게 된다.

- 차수(degree): 차수는 각 노드가 갖는 자식의 수를 의미한다.

위 그림에서 보면 X 노드는 2개의 자식 노드를 가지므로 차수가 2인 것이다.

모든 노드의 차수가 n 이하인 트리를 n진 트리라고 부르는데 위 그림은 모든 노드가 3개이하의 자식을 가지고 있으므로 3진 트리라고 할 수 있다.

- 서브 트리(subtree): 루트 이외에 어떠한 노드를 루트로 하고 그 자손으로 구성된 트리를 서브트리라고 한다.

위 그림에서 표시된 것처럼 X노드를 루트로하여 서브트리를 구성할 수 있다.

- 형제 노드(sibling node): 부모가 같은 노드를 형제노드라고 한다.

위 그림에서 보면 X의 자식노드로 2개의 노드가 있는데 2 노드는 형제노드에 속하게 된다.

 

이러한 트리는 순서 트리(ordered tree)와 무순서 트리(unordered tree)로 나뉜다.

순서 트리는 형제 노드의 순서 관계가 있으면 순서 트리이고 형제노드의 관계를 구별하지 않으면 무순서 트리이다.

아래의 두 트리를 보면 순서 트리로 생각했을 때에는 서로 다른 트리이지만 무순서 트리로 생각했을 때에는 서로 같은 트리로 보게 된다.

 

 

2. 이진 트리 (binary tree)

우리는 위에서 트리를 공부할 때 차수(degree)라는 개념에서 모든 노드의 차수가 n 이하인 트리를 n진 트리라고 부른다고 보았다.

이 개념을 n = 2일 때, 즉, 어떠한 노드(루트 포함)의 자식 노드가 왼쪽 자식과 오른쪽 자식만을 갖는 트리를 이진 트리라고 부른다. 서브트리를 따로 보아도 이진트리라는 것이다.

여기서, 모든 노드의 차수가 2 이하이므로 자식노드가 하나도 없거나 한개만 가지고 있는 경우도 있을 것이다.

위에서 이진드리를 정의한 것에서 이진 트리의 특징을 볼 수 있는데 왼쪽 자식과 오른쪽 자신을 구분한다는 것이다.

아래의 그림을 보면 2번 노드의 왼쪽 자식은 4번이고 오른쪽 자식은 5번라고 구분을 지어 얘기할 수 있다.

또한, 4번을 루트로 하여 서브트리를 구성하면 왼쪽 서브트리, 5번을 루트로 하여 서브트리를 구성하면 오른쪽서브트리라고 부른다.

 

 

 

 

 

3. 완전 이진 트리 (complete binary tree)

완전 이진 트리는 큰 틀로 봤을 때는 위에서 정의한 이진 트리 중 하나이지만 더 구체적으로 같은 레벨 안에서 왼쪽부터 오른쪽으로 노드가 채워져 있는 이진 트리를 완전 이진 트리라고 한다.

즉, 노드의 자식 노드는 왼쪽 자식과 오른쪽 자식만 존재하고 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리를 말한다.

완전 이진 트리의 모습은 아래와 같다.

- 마지막 레벨을 제외하고 모든 레벨에 노드가 가득 차 있는 상태다.

- 마지막 레벨에 한해서 왼쪽부터 오른쪽으로 노드를 채우되 반드시 끝까지 채우지 않아도 된다.

 

아래의 그림을 보면 왼쪽 트리는 완전 이진 트리이고 오른쪽 트리는 완전 이진 트리가 아니다.

그 이유는 왼쪽 트리는 노드들이 왼쪽부터 오른쪽으로 채워졌지만 오른쪽 노드는 그러하지 않기 때문이다.

 

완전 이진 트리의 높이(= 리프의 최대 레벨)가 h라면 완전 이진 트리가 가질 수 있는 노드의 수는 최대 2^(h+1) - 1개이다.

이렇게 되면 n개의 노드를 가진 완전 이진 트리의 높이는 log(n)이 된다.

(여기서 log의 밑은 10이 아닌 2이다.)

 

---

[오늘의 나는 어땠을까?]

오늘은 뭔가 뭘했지? 하는 느낌이 드는 하루다.

아침에 와서 Do it! 책을 잠깐 보고 우선순위 큐 문제를 슥 보다가 점심시간이 됐다.

점심을 먹은 후 까먹고 있었던 토스 2021 NEXT 채용 코딩테스트가 오늘 오후 2시에 진행되는 것을 문자를 통해 알게 되었고 응시를 했다.

문제 자체는 어렵지 않았지만 보이지 않고 떠오르지 않는 예외처리를 해야하고 시간복잡도를 줄여야 했다.

최대한 생각을 끄집어 내보려 했지만 완벽히 풀어낼 수 없었다.

하지만 조금만 더 지금 내게 이렇게 주어진 시간들을 최대한 효율적으로 활용해서 익숙해진다면 다 해결할 수 있다는 생각이 들었다.

알고리즘 문제풀이식 테스트를 마치고 서술형 문제도 진행되었다.

서술형 문제를 본 순간, '이게 신입에게 요구하는 실력인가?'하는 생각이 들었다.

너무 어려웠고 뭔가 대충은 이렇게 하면 되지 않을까?했지만 글로 써내는게 어려웠다.

지금은 내게 큰 벽을 느끼게 했지만 다음에 이 벽을 못넘을 거라는 생각을 하지 않고 어떻게든 CS지식을 쌓아가며 해결해 낼 것이다.

SW 사관학교 정글의 과정을 하나하나 해결해나가면 분명 해낼 수 있을 것이다.

아니, 해낼 것이다. 할 수 있다!!

 

---

<참고 자료>

자료구조와 함께 배우는 알고리즘 입문 파이썬 편 (저자 Bohyoh Shibata, 옮김 강민)

 

https://codingdog.tistory.com/entry/%EC%99%84%EC%A0%84%EC%9D%B4%EC%A7%84%ED%8A%B8%EB%A6%AC-vs-%ED%8F%AC%ED%99%94%EC%9D%B4%EC%A7%84%ED%8A%B8%EB%A6%AC-%EC%9D%B4-%EB%91%98%EC%97%90-%EB%8C%80%ED%95%B4-%EC%95%8C%EC%95%84%EB%B4%85%EC%8B%9C%EB%8B%A4

 

https://jomuljomul.tistory.com/entry/%EC%99%84%EC%A0%84%EC%9D%B4%EC%A7%84%ED%8A%B8%EB%A6%ACComplete-Binary-Tree%EB%9E%80