[자료구조] Binary Search Tree

Binary Search Tree란?

---

👉 개념

Binary Search Tree(BST)는 효율적인 탐색을 위한 데이터 저장 방법이다. 

 

👉 규칙

• 노드에 저장되는 키는 유일하다. 
• 부모의 키 값이 왼쪽 자식 노드의 키 값보다 크다. 
• 부모의 키 값이 오른쪽 자식 노드의 키 값보다 작다. 
• 왼쪽과 오른쪽 서브트리도 BST이다. 

 

👉 장단점

장점
탐색 연산 시간복잡도가 O(log N)이다. (명확히 말하면 O(h))

단점 
편향 트리의 경우 저장 순서에 따라서 한 쪽으로만 노드가 추가되는 경우가 발생한다.
최악의 경우는 탐색 시간복잡도가 O(N)이다.
배열보다 많은 메모리를 사용한다.

 

출처: https://yoongrammer.tistory.com/71

 

 

 

Leetcode 문제를 통한 BST 구현

---

BST를 직접 구현하는 것이 도움이 될 것이라 생각하여 아래 문제를 풀어보았다. 

1. 탐색: https://leetcode.com/problems/search-in-a-binary-search-tree/

Search in a Binary Search Tree - LeetCode

 

2. 삽입: https://leetcode.com/problems/insert-into-a-binary-search-tree/

Insert into a Binary Search Tree - LeetCode

 

3. 삭제: https://leetcode.com/problems/delete-node-in-a-bst/

Delete Node in a BST - LeetCode

 

 

👉 풀이

1. 탐색

 

2. 삽입

 

3. 삭제