(자료구조,알고리즘) Binary Search Tree

이진 탐색 트리(Binary Search Tree)는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징이 있다.

먼저, 이진 트리(Binary tree)는 자식 노드가 최대 두 개인 노드들로 구성된 트리입니다.
이 두 개의 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 나눌 수 있다.

이진 트리는 자료의 삽입, 삭제 방법에 따라
정 이진 트리(Full binary tree),
완전 이진 트리(Complete binary tree),
포화 이진 트리(Perfect binary tree)로 나뉩니다.

정 이진 트리(Full binary tree)

각 노드가 0개 혹은 2개의 자식노드를 갖는다

포화 이진 트리(Perfect binary tree)

정이진트리 이면서 완전 이진 트리인 경우이다. 모든 리프노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리이다

완전 이진 트리(Complete binary tree)

마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고,
마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 한다