1. 개요

Tree는 말 그대로 나무 비스무리한 구조긴한데, 현실 나무 처럼 위로 뻗는게 아니라 가계도처럼 위에서 아래로 뻗는다고 생각하면된다.

Tree는 Cycle (어느 지점에서 출발해서 다시 출발한 곳으로 돌아오는것) 이 없는 Node들의 모음이다.

본문을 소개하기 이전에 tree 관련 정의에 대해 설명하겠다.

2. 정의

Root : 부모(Parent)라고 불리는 상위 노드가 없는 노드를 root라고 한다.

ex) A
Leaf : 아이(children)라고 불리는 하위 노드가 없는 노드를 leaf라 한다. Leaf는 degree가 0이다.

ex) K,L,F,G,M,I,J
Degree of node : 노드 하나에 연결되어 있는 Subtree의 개수.

ex) degree of a=3, c=1, f=0
Degree of tree : tree안에서 가장 많은 degree

ex) degree of tree = 3 (A,D)
Sibling : 같은 부모(Parent)를 둔 아이들(children)

ex) (H,I,J) (E,F) (K,L) (B,C,D)
Path : 각각의 노드에서 인접한 다음 노드로의 순서
Ancestors : root로부터 그 노드까지의 path를 따라가는 모든 노드

ex) M의 ancestors: A,D,H
Decendants : subtree에 있는 모든 노드

ex) B의 decendants: E,F,K,L
Level of node : root 노드를 1이라 잡고, 한 노드의 레벨을 L이라 하면, 그 노드의 자식의 레벨은 L+1

ex) Level of M : 4
Height / Depth of tree : tree의 제일 큰 level. 이미지의 heigh는 4.

3. Binary Tree

이번 글에서는 Binary tree에 대해 다룰 것이다.

Binary tree란 아예 비었거나, root와 left, right로 불리는 서로 다른 subtree로 구성된 유한한 노드의 집합이다.

어떤 노드든 최대 2개의 children을 가질수 있고, children들은 ordered(순서를 가지고 있는)되어있다.

Binary Tree의 종류

Skewed binary tree

한쪽으로 치우쳐저있는 구조다. 이게 심해지면, Linear(선형)구조와 다를게 없게 된다. 그러면 데이터 탐색시 시간이 길어질 수 있다.

Full binary tree of depth k

2의 k(k>=0)승 - 1개의 노드를 가지고 있는 binary tree

ex) depth 3의 full binary tree의 노드 개수는 2의 3승(8) - 1 = 7개

Complete binary tree

영문으로는 ‘A binary tree with n nodes and depth k is complete iff(if and only if) its nodes correspond to the nodes numbered 1 to n in the full binary tree’ 라고 하는데 간단하게 말하면, 왼쪽부터 차례대로 채워놓은 트리다.