이진탐색트리 (Binary Search Tree)

 

 

💡이진 탐색 트리 (binary search tree)

 

트리 구조는 편리한 구조를 전시하는 것 외에 효율적인 탐색을 위해 사용하기도 한다. 트리 구조는 가지고 있는 특징에 따라 여러 가지 이름으로 불리는데 이진 트리(binary tree)와 이진 탐색 트리(binary search tree)가 가장 많이 사용된다.

 

먼저 이진트리는 자식 노드가 최대 두 개인 노드들루 구성된 트리이다. 두 개의 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 나눌 수 있는데, 이진 트리는 자료의 삽입, 삭제 방법에 따라 정 이진 트리, 완전 이진 트리, 포화이 이진 트리로 나뉘게 된다.

 

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



 

 

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