Binary Tree를 알아보자

코딩 공부를 시작했다면 한 번쯤은 "데이터 구조", "알고리즘" 이 두 단어들을 들어봤을 거다.

데이터 구조와 알고리즘은 코딩 테스트/인터뷰에서 자주 등장하는 주제로, 신입 개발자의 실력을 테스트해보는 용도로 사용된다.

 

오늘은 여러 데이터 구조 종류 중 binary tree에 대해서 알아보자.

Binary tree는 거꾸로 뒤집힌 나무 모양과 비슷하다.

Binary Tree

Binary tree는 node로 구성돼있고, 각 node는 최고 2개의 child node를 가질 수 있다.

Binary tree를 시작하는 node를 root라고 부르고, root는 반드시 딱 하나만 존재할 수 있다.

 

node는 값을 저장하는 value, 왼쪽/오른쪽 child node에 연결할 수 있는 pointer들로 구성돼있다.

node를 코드로 보면:

class TreeNode:
	def __init__(self, value, left=None, right=None):
    		self.val = value
       		self.left = left
        	self.right = right

 

맨 마직막에 child node가 없는 node를 leaf node라고 부른다.

Binary tree의 사이즈는 두 가지로 측정할 수 있는데,

첫 번째는 node의 총 개수

두 번째는 트리의 높이이다.

 

트리의 높이는 층으로 세는데, 위 이미지의 트리 같은 경우에 높이는 2이다.

root 하나만 있는 트리의 높이는 0 이 된다.

 

다른 데이터 구조처럼 binary tree도 순회할 수 있다.

트리의 각 node를 순회하는 방법은 2가지가 있다:

첫 번째는 Breadth-First, 너비 우선 방식,

두 번째는 Depth-First, 깊이 우선 방식이다.

 

너비 우선 방식은 위에서 아래로 층층이 내려가면서 각 node를 순회하는 방식이고

깊이 우선 방식은 아래에서 위로 올라가면서 각 node를 순회하는 방식이다.

 

깊이 우선 방식에는 Inorder, Preorder, Postorder 이렇게 3개의 순서가 있다.

이 순서는 각 node를 언제 사용하는지, 언제 왼쪽/오른쪽 하위 트리로 가는지에 차이가 있을 뿐

전부 깊이 우선 방식의 알고리즘을 사용한다.

 

Breadth-First - 너비 우선

너비 우선 알고리즘은 queue를 사용해서 작성할 수 있다.

이 알고리즘의 플로우를 말로 풀어보면:

1. queue를 만든다
2. queue에 root를 넣는다
3. queue의 사이즈가 0 보다 크면 [while loop]
3.1. queue에서 node 하나를 빼내어 n에 저장한다 [여기서 n은 변수를 말한다]
3.2. 만약 n이 목표 node 이면 필요한 작업을 한다
3.3. 만약 n이 왼쪽 child node를 가지고 있으면 queue에 왼쪽 child node를 넣는다
3.4. 만약 n이 오른쪽 child node를 가지고 있으면 queue에 오른쪽 child node를 넣는다

이렇게 queue가 비어질 때까지 반복하면 결국엔 위에서 아래로 내려가면서 각 층의 모든 node를 한 번씩 방문하게 된다.

 

Depth-First - 깊이 우선

깊이 우선 알고리즘은 너비 우선과는 다르게 stack을 사용한다.

함수가 재귀할 때마다 콜 스택에 들어가고, 콜 스택에서 나오는 순서가 순회 순서가 된다.

앞서 말했듯이 깊이 우선에는 3가지의 순서가 있다.

 

Inorder 순회 방식

이 방식의 순서는 왼쪽 하위 트리, root, 오른쪽 하위 트리 순으로 순회한다.

알고리즘의 플로우를 살펴보자:

1. 만약 node가 null이면 끝
2. Recursion(node.left)
3. 작업 하기
4. Recursion(node.right)

 

Preorder 순회 방식

이 방식의 순서는 root, 왼쪽 하위 트리, 오른쪽 하위 트리 순으로 순회한다.

알고리즘의 플로우를 살펴보자:

1. 만약 node가 null이면 끝
2. 작업 하기
3. Recursion(node.left)
4. Recursion(node.right)

 

Postorder 순회 방식

이 방식의 순서는 왼쪽 하위 트리, 오른쪽 하위 트리, root 순으로 순회한다.

알고리즘의 플로우를 살펴보자:

1. 만약 node가 null이면 끝
2. Recursion(node.left)
3. Recursion(node.right)
4. 작업 하기

 

Binary Tree 저장 방법

Binary tree를 저장하는 방법은 기본적으로 node와 레퍼런스 방식이 있다.

지금까지 언급한 binary tree는 이 방식으로 만들어진 트리이다.

이 방식의 오점은 낭비되는 메모리가 많다는 거다.

위에서 봤듯이 각 node는 2개의 null pointer를 가지고 있다. 즉 node 하나당 메모리 2 공간이 소비된다는 뜻이다.

이 계산대로라면 4개의 node로 만들어진 트리에는 5개의 null pointers가 존재한다. 생각보다 많은 메모리 소비이다.

 

Node pointer 방식에 낭비되는 메모리

만약 트리를 array형식으로 저장한다면 node & pointer 방식보다는 훨씬 적은 메모리를 낭비한다.

위와 같은 트리를 array에 저장하면 아래와 같은 array가 만들어진다.

Array에 저장한 binary tree

node & pointer 방식과는 달리 낭비되는 메모리가 없다.

물론, 예시에 사용된 트리는 작아서 그렇지만, 더 큰 트리를 사용한다 해도 낭비되는 메모리는 훨씬 적다.

Array를 사용하는 경우 왼쪽/오른쪽 child node는 현재 index에서 2를 곱하고 왼쪽의 경우 1을 더하고, 오른쪽의 경우 2를 더하면 된다.

Index	Value	Left Child	Right Child
0	0	(2*0)+1 = 1	(2*0)+2 = 2
1	1	(2*1)+1 = 2	(2*1)+2 = 4
2	2	(2*2)+1 = 5 (out of bound)	(2*2)+2 = 6 (out of bound)

 

나도 이제 배우기 시작해서 좀 두서없더라도 이해해주길 바란다.