[자료구조] 이진탐색트리(Binary Search Tree)

🎯 Binary Search Tree

---

Binary Search Tree(BST, 이진 탐색 트리)는 이진 트리의 일종으로, 모든 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값을 가진 노드들이, 모든 오른쪽 서브트리에는 해당 노드보다 큰 값을 가진 노드들이 저장되어 있는 이진 트리입니다.

Binary Search Tree의 특징

---

1. 이진 트리의 구조를 따르고 있으므로, 모든 노드의 자식 노드의 수가 최대 2개입니다.
2. 모든 왼쪽 서브트리의 노드들은 해당 노드보다 작은 값을 가지고 있으며, 모든 오른쪽 서브트리의 노드들은 해당 노드보다 큰 값을 가지고 있습니다.
3. 중복된 값을 가지는 노드를 허용하지 않습니다.

Binary Search Tree의 주요 연산

---

1. 탐색(Search)
   • BST에서 특정 값을 가진 노드를 찾는 연산입니다. 해당 값이 BST에 없는 경우 NULL을 반환합니다. 이 연산의 시간 복잡도는 O(log n)입니다.
2. 삽입(Insertion)
   • BST에 새로운 노드를 삽입하는 연산입니다. 이 연산의 시간 복잡도는 탐색과 같은 O(log n)입니다.
3. 삭제(Deletion)
   • BST에서 특정 값을 가진 노드를 삭제하는 연산입니다. 삭제할 노드의 자식 노드에 따라 연산 방법이 달라집니다. 이 연산의 시간 복잡도는 O(log n)입니다.

Binary Search Tree 장단점

---

⭐️ Binary Search Tree 장점

1. 검색 시간이 빠르다
   • 이진 탐색 트리의 특성상 탐색 시간이 O(log n)으로 매우 빠릅니다.
2. 삽입과 삭제가 용이하다
   • BST는 삽입과 삭제가 다른 자료구조에 비해 용이합니다.
3. 데이터의 중복을 허용하지 않는다
   • 데이터의 중복을 허용하지 않으므로 데이터의 유일성이 보장됩니다.

💀️ Binary Search Tree 단점

1. 트리의 불균형
   • 삽입과 삭제가 빈번하게 일어나는 경우, 트리의 균형이 깨져 검색 시간이 O(n)으로 증가할 수 있습니다.
2. 최악의 경우 시간 복잡도가 O(n)이 될 수 있다
   • BST가 균형을 유지하지 못할 경우, 최악의 경우 시간 복잡도가 O(n)으로 증가할 수 있습니다.