🚀 What I Will Learn

• 이진 탐색 트리(binary Search Tree, BST)에 대해 이해하기

이진 탐색 트리(binary Search Tree, BST)란? 이진 탐색(Binary Search)이 항상 동작하도록 구현하여 탐색 속도를 극대화 시킨 자료구조

---

이진 탐색 트리(binary Search Tree, BST)

1️⃣ 이진 탐색 트리란?

• 이진 탐색(Binary Search)이 항상 동작하도록 구현하여 탐색 속도를 극대화 시킨 자료구조

✔️ 이진 탐색 트리의 원리

• 한 번 확인할 때 마다 원소의 개수가 절반씩 줄어든다는 점에서 완전 이진 트리인 경우 탐색 시간에 𝑂(𝑙𝑜𝑔𝑁)의 시간 복잡도를 가진다
• 찾고자 하는 값이 부모 노드보다 작을 경우 왼쪽 자식으로, 찾고자 하는 값이 부모 노드보다 클 경우 오른쪽 자식으로 이어 나가면서 방문한다

✔️ 이진 탐색 트리 예제:: 탐색

• 항상 부모 노드가 왼쪽 자식보다는 크고, 오른쪽 자식보다는 작다

• 두 번째 노드인 48의 자식과 비교했을 때 바로 찾았다...

✔️ 이진 탐색 트리 예제:: 삭제

• 자식이 없는 경우

  • 삭제할 노드의 자식이 없는 경우 단순히 제거하면 된다

  

• 자식이 하나만 존재하는 경우

  • 삭제할 노드의 자식이 하나만 존재하는 경우 삭제할 노드의 자리에 자식 노드를 추가한다

  

• 자식이 둘 다 존재하는 경우

  • 자식이 둘 다 존재하는 경우 그 다음으로 삭제할 노드의 자리에 자기 다음으로 큰 노드를 추가한다

  

📌 참고

이진 탐색 트리의 성능을 최대로 끌어내기 위해서는 이진 탐색 트리가 완전 이진 트리에 가까워 질 수 있도록 설계해야 한다
▶︎ 높이가 낮을수록 탐색을 빠르게 할 수 있기 때문에 균형이 잡힌 트리가 될 수 있도록 설계해야 한다

✔️ 트리(Tree)의 효율성

트리(Tree)를 사용하면 데이터를 처리할 때 효율적이다

• 트리에서 데이터의 개수가 N개일 때, 배열과 마찬가지로 O(N)의 공간만이 소요되며
• 삽입 및 삭제할 때 일반적인 경우, 기존의 배열을 이용하는 방식보다 효율적이다

▶︎ 그래서 데이터베이스 등 대용량 저장 및 검색 자료구조로 많이 활용된다

---

✨ tl;dr

• 편향 이진 트리(Skewed Binary Tree)은 탐색할 때 𝑂(𝑁)의 시간 복잡도를 가지기 때문에
• 이진 탐색 트리를 최대한 완전 이진 트리의 형태를 유지할 수 있도록 해야한다