Binary Search Tree

트리구조는 효율적인 탐색을 위해 사용하기도 한다.
트리구조의 특징에 따라 분류가 되는데, 그 중 이진트리와 이진 트리 탐색에 대해 알아보자.

이진 탐색 트리(Binary Search Tree)

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

이진 탐색 트리가 만약 균형이 잡혀 있지 않은 트리일 때, 탐색하는데 시간이 더 걸리는 경우가 생길 수 있다.

그러므로 이러한 문제를 해결하기 위해 삽입이나 삭제를 통해 트리를 재조정하는 과정을 거치는 알고리즘을 추가할 수 있다.

이진 트리(Binary tree)

이진 트리는 자식 노드가 최대 두 개인 노드들로 구성된 트리이다.

이진 트리는 자료 삽입, 삭제 방법에 따라
정 이진 트리
완전 이진 트리
포화 이진 트리로 나뉜다.

• 정 이진 트리 : 각 노드가 0개나 2개의 자식 노드를 가짐

• 완전 이진 트리 : 마지막 레벨을 제외한 모든 노드가 가득 차 있고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽은 채워져야 함

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