[자료구조] 이진 트리(Binary Tree) / 이진 탐색 트리(Binary Search Tree)

 이진 트리(binary tree)는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 구조이다. 여기서 자식 노드들은 왼쪽 자식 노드, 오른쪽 자식 노드로 나뉜다.

 

 이진 트리는 자료의 삽입, 삭제 방법에 따라서 다음과 같이 나뉜다.

 

• 정 이진 트리(ful binary tree)
  : 각 노드가 0개 혹은 2개의 자식 노드를 갖는다.
  
  
• 포화 이진 트리(perfect binary tree)
  : 정 이진 트리이면서 완전 이진 트리인 경우이다. 모든 리프 노드의 레벨이 동일하고 모든 레벨이 가득 채워져 있는 트리이다.
  
  
• 완전 이진 트리(complete binary tree)
  : 마지막 레벨을 제외한 모든 노드가 가득 차 있으며, 마지막 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 한다.

 

 이진 탐색 트리(binary search tree)는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 트리를 말한다. 이진탐색의 효율적인 탐색 능력을 유지하면서, 빈번한 자료 입력과 삭제가 가능하게끔 고안되었다.