Tree(1) - 트리 개념, 이진트리, 이진검색트리

Yves (Taeyeon Kim)·2021년 11월 25일

CS - Data Structure and Algorithm Core

목록 보기

2/7

0. 트리 용어정리

루트(root)

트리의 가장 위쪽에 있는 노드이며, 트리별로 하나만 존재한다.

루트와 부모노드는 다르다. 부모노드는 자식노드가 1개 이상인 경우에 존재하는 개념이다.

서브트리(sub tree)

자식노드이면서 부모노드역할을 하는 노드가 있는 트리

차수

노드가 갖고 있는 최대 자식노드의 수

리프(leaf)

레벨별로 가장 마지막에 있는 노드로, 단말노드(terminal node) 혹은 외부노드(external node)라고도 한다.

리프는 트리별로 여러 개가 있을 수 있다.

레벨(level)

루트노드에서 얼마나 멀리 떨어져 있는지를 나타내는 수다.

루트노드의 레벨은 0이며, 한단계 내려갈때마다 1씩 증가한다.

높이

루트에서 가장 멀리 떨어진 리프노드까지의 거리이며, 리프 레벨의 최대값을 높이라고한다.

형제노드(sibling)

부모가 같은 두 개의 노드

1. Binary Tree - 이진 트리

1.1. What is binary tree?

이진트리는 위 그림과 같이 각 노드별로 최대 2개의 자식노드를 갖는다. (left, right)
다양한 트리 종류 중에서 이진트리는 가장 기본이 되며 많이 활용된다.
이진트리가 성립하기 위해서는 두가지 조건이 존재한다.
- 루트노드를 중심으로 두 개의 서브트리로 나눠진다.
- 나뉘어진 두 서브트리도 모두 두 개의 서브트리를 가진다. (단, 서브트리의 노드가 반드시 값을 가지고 있을 필요는 없다.)

# 이진트리 기본코드
class BinaryTreeNode:
	def __init__(self, value):
	    self.left = None #왼쪽 서브노드
            self.value = value
            self.right = None #오른쪽 서브노드

1.2. 이진트리 종류

1) Binary Search Tree(BST)

(이미지 출처)

모든 값들이 크기를 기준으로 노드들에 의해 구분되어 있다.
자세한 내용은 아래 1.3. Binary Search Trees(BST) - 이진검색트리 를 참고한다.

2) Balance

Balanced Tree와 Unbalanced Tree가 있는데, 여기서 'Balance가 맞다'라는 건 꼭 좌우노드의 수가 정확하게 같아야 하는 것을 의미하진 않는다.
우측(unbalanced) 트리와 같이 심한 불균형 상태가 아닌 경우 balanced tree 라고 할 수 있다.

3) Complete Binary Tree

트리 레벨별로 좌측부터 노드가 채워지는 이진트리다.

4) Full Binary Tree

노드가 Child를 가질거면 두개의 Child를 가지거나, 아예 하나도 가지지 않는 이진트리다.
즉, Child를 하나만 가진 부모노드는 Full Binary Tree에 존재하지 않는다.

5) Perfect Binary Tree

모든 노드가 두개의 Child를 가지며 정확한 피라미드 모양을 가지는 이진트리다.
레벨의 개수를 $n$ 이라고 할 때, Perfect Binary Tree의 총 노드 수 = $2^n-1$ 이다.
위의 그림에서는 $n=3$ (총 3개의 레벨), 총 노드 수= $2^3-1=7$ 이다.

1.3. Binary Search Trees(BST) - 이진검색트리

이진검색트리는 노드를 정확하게 정렬해야하는 특정 유형의 이진트리다.
이진검색트리는 값 크기 조건에 따라 노드에 값을 넣어줘야 한다.

값 크기 조건

값 크기 조건은 다음과 같은 노드의 값 크기 순서를 따른다.
오른쪽 서브노드의 값(right child) > 루트(부모)노드의 값(root node) > 왼쪽 서브노드의 값(left child)
중복값을 갖고 있는 노드가 없어야 한다.

왼쪽 서브트리노드들의 값은 루트(부모)노드값보다 작아야 한다.

오른쪽 서브트리노드들의 값은 루트(부모)노드값보다 커야 한다.

위와 같은 규칙이 정해진 이유는 왼쪽부터 오른쪽으로 검색하는 구조이기 때문인데, 트리와 같은 자료구조는 연결리스트를 참조해서 만들어진 개념이기 때문이다.

또한, 이진검색트리는 단순 이진트리보다 노드탐색이 빠른데, 그 이유는 값 크기 조건에 맞도록 노드에 값을 넣어주기 때문이다.