BST ( Binary Search Tree )

트리는 편리한 구조를 전시하는것 외에 효율적인 탐색을 위해 사용하기도한다.

효율적인 탐색 을 위해 많은 지성인들이 각각의 특징을 추가하여 새로운 트리의 모습을 만드는 등 치열한 노력을 쏟았다.

그렇기 때문에 특징에 따라 여러가지 이름으로 불리고있다.

가장 많이 사용하는것이

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

자식 노드가 최대 두개인 노드들로 구성된 트리 를 이진트리 라고 정의 한다.

이 두개의 노드는 왼쪽자식과 오른족 자식으로 분류된다.

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

• 정 이진 트리 : 각 노드가 0개 혹은 2개의 자식노드를 가진다.

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

여기서!!

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

이진 탐색 트리는 균형 잡힌 트리가 아닐때, 입력되는 값의 순서에 따라 한쪽으로 노드들이 몰리게 될 가능성이 있다. 이러한 문제를 해결하기 위해 삽입과 삭제마다 트리의 구조를 재조정하는 과정을 거치는 알고리즘을 도입할수 있다.