효율적인 탐색

• 트리 구조는 편리한 구조를 전시하는 것 외에 효율적인 탐색을 위해 사용되기도 한다.
• 트리 구조는 가지고 있는 특징에 따라 여러가지 이름으로 불린다.

이진트리 (Binary tree)

자식 노드가 최대 두 개인 노드들로 구성된 트리이다. 이 두 개의 자식 노드는 왼쪽 자식 노드와 오른쪽 자식노드로 나눌 수 있다.

이진트리 - 정 이진 트리, 완전 이진 트리, 포화 이진 트리

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

• 정 이진 트리 (Full binary tree)
  => 각 노드가 0개 혹은 2개의 자식 노드를 갖는다.

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

• 포화 이진 트리 (Complete binary tree)
  => 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차있지 않아도 되지만 왼쪽이 채워져야한다.

이진 탐색 트리 (Binary Search tree)

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

이진 탐색 트리는 균형 잡힌 트리가 아닐 때, 입력되는 값의 순서에 따라 한 쪽으로 노드들이 몰리게 될 수 있다. 균형이 잡히지 않은 트리는 탐색하는데 시간이 더 걸리는 경우가 있기 때문에, 해결해야할 문제이다. 이 문제를 해결하기 위해서는 삽입과 삭제마다 트리의 구조를 재조정하는 과정을 거치는 알고리즘을 추가할 수 있다.