[Trees]24. Binary Trees(이진 트리)

목차

1. Binary Trees(이진 트리)

2. Arithmetic Expression Tree

3. Decision Tree

4. 이진 트리의 종류

 

1. Binary Trees(이진 트리)

 Binary tree(이진 트리)는 다음과 같은 특징들을 따르는 tree를 말합니다.

1) 각각의 internal node는 최대 두개의 children을 지닌다(proper binary tree를 위해서는 정확히 2개)

2) node의 children은 ordered pair이다.

 

 따라서 root 한개만 보유하고 있는 tree, 혹은 하나의 root와 root의 자식 2개로 이루어져 있는 tree도 binary tree의 일종이라고 할 수 있습니다.

2. Arithmetic Expression Tree

 일반적인 사칙연산으로 이루어진 수식은 binary tree로 나타낼 수 있습니다. 여기서 특징으로는,

1) 연산자는 internal node

2) 비연산자는 external node

 

3. Decision Tree

 Decision Tree는 binary tree를 활용한 결정의 과정을 말합니다. 이것의 특징은,

1) 참/거짓을 판단하는 문제는 internal node

2) 최종 결정은 external node

 

4. 이진 트리의 종류

 이진 트리는 각각 node별로 2개의 자식을 가질 수 있는 특수한 tree임으로, 다양한 특징들을 지니고 있습니다.

 

1) Notation(표기법)

- n: node의 개수

- e: external node의 개수

- i: internal node의 개수

- h: height

 

2) Tree의 종류

- Proper Binary Tree(적정 이진 트리): 각각의 node가 자식을 0개, 혹은 2개만 가지는 tree를 말합니다.

- Complete Binary Tree(완전 이진 트리): 부모, 왼쪽 자식, 오른쪽 자식 순으로 저장되는 tree로서, 마지막 레벨 전까지는 node가 가득차있으며, 마지막 레벨의 node도 왼쪽으로 쏠려있는 구성이다.

- Perfect Binary Tree(포화 이진 트리): 모든 레벨이 가득 채워져 있는 tree를 말한다.