이진탐색트리(Binary Search tree)

이진 트리

1. 이진 트리 유형

1-1. 정 이진 트리(full binary tree)

모든 노드가 2개의 자식을 가지는 트리

1-2. 포화 이진 트리(perfect binary tree)

모든 노드가 2개의 자식을 가지고 leaf 노드가 모두 같은 레벨인 트리

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

다음 두 조건을 만족해야 한다

1. 마지막 레벨을 제외하고 모든 노드가 채워진 트리
2. 노드는 왼쪽부터 채워져야 한다.

2. 이진 트리 배열로 표현하기

1. 0번 인덱스를 비워두고 root 노드를 1번 인덱스에 위치시킨다
2. level 순, 그리 다음은 왼쪽에서 오른쪽 노드 순으로 배열에 위치시킨다.