Binary Search Tree

Binary Search Tree는 Binary Tree의 특성을 가지면서 추가로 부모 노드의 왼쪽 자식이 가지는 값은 부모 노드의 값보다 작고 부모 노드의 오른쪽 자식이 가지는 값은 부모 노드의 값보다 큰 특성을 지닙니다.
이 추가적인 특성은 검색, 삽입, 삭제에서 효율성을 보장해줍니다.

Binary Search Tree의 특성

• 노드의 왼쪽 서브트리는 해당 노드의 값보다 작은 값을 가진 노드들로 이루어집니다.
• 노드의 오른쪽 서브트리는 해당 노드의 값보다 큰 값을 가진 노드들로 이루어집니다.
• 위의 규칙은 모든 노드에 적용됩니다.
• Binary Search Tree 내에 있는 모든 서브트리는 Binary Search Tree입니다.

Binary Search Tree의 Operation

1. Searching
   Binary Search Tree는 어느 노드든지 왼쪽 자식은 해당 노드보다 작은 값을 가지고 오른쪽 자식은 해당 노드보다 큰 값을 가지는 특성을 이용해 보다 쉽게 값을 찾을 수 있습니다.
   아래는 Searching이 이루어지는 방식에 대한 설명입니다.

   1. 먼저 root의 값을 찾고자 하는 값과 비교합니다.
   - 만약 찾고자 하는 값과 같은 값을 root가 가지고 있다면 해당 노드를 반홥합니다.
   - 만약 찾고자 하는 값보다 큰 값을 root가 가지고 있다면 왼쪽 서브트리로 이동합니다.
   - 만약 찾고자 하는 값보다 작은 값을 root가 가지고 있다면 오른쪽 서브트리로 이동합니다.
   2. 위의 과정을 값을 찾을때 까지 반복합니다.
   3. 만약 위의 과정을 반복한 결과 값을 찾지 못한다면 NULL을 반환합니다.

2. Insertion
   Binary Search Tree에서 삽입은 언제나 리프 노드에서 이루어집니다.
   적절한 리프 노드를 찾으면 해당 리프 노드의 왼쪽 자식이나 오른쪽 자식으로 들어갑니다.

3. Deletion
   Binary Search Tree에서 삭제는 상황에 따라 고려해야 할 점이 있습니다.

• 삭제하고자 하는 노드가 리프 노드일 때
  그냥 삭제하면 됩니다.
• 삭제하고자 하는 노드가 자식 노드를 1개 가지고 있을 때
  해당 노드를 삭제한 후 부모 노드와 자식 노드를 연결해주면 됩니다.
• 삭제하고 하는 노드가 자식 노드를 2개 가지고 있을 때
  이때는 삭제하고자 하는 노드보다 작은 값들 중 가장 큰 값을 가진 노드를 찾습니다. 해당 노드는 리프 노드가 될 것입니다.
  리프 노드와 삭제하고자 하는 노드를 바꾼 뒤 노드를 삭제하면 됩니다.

4. Inorder Traversal
   Binary Search Tree에서 Inorder Traversal은 모든 값들을 오름차순으로 정렬해서 반환해주는 역할을 합니다.

Binary Search Tree의 이점

• 검색이 매우 빠름. 시간 복잡도가 평균적으로 O(N)
• Inorder traversal을 통해 정렬된 데이터셋을 얻을 수 있음

Binary Search Tree의 단점

• 편향된 Binary Search Tree가 되면 검색이 매우 비효율적.
• 편향된 Binary Search Tree가 되지 않게 균형을 맞추면 이에 대한 추가 시간이 필요
• 삽입, 삭제, 검색에서 hash table이 BST보다 더 빠름. 그러나 순서화된 데이터셋이 필요하면 BST 사용해야함.