bst
Q&A 정리: bst
BST에서 임의의 노드를 골랐을 때, 왼쪽 서브트리와 오른쪽 서브트리의 값은 어떤 관계인가?
이진 탐색 트리(BST)는 어떤 노드를 기준으로 왼쪽에는 더 작은 값, 오른쪽에는 더 큰 값만 존재하는 규칙을 가진다. 사전에서 단어를 찾을 때 알파벳 순서로 왼쪽/오른쪽을 나누는 원리와 같다.
- Ordering Property: For every node in the BST, all values in the left subtree are smaller, and all values in the right subtree are larger than the node's value. This rule holds recursively for all subtrees.
- Recursive Nature: Each left or right subtree of a node in a BST is itself a BST, allowing recursive algorithms to naturally process the tree.
BST에 중복 값을 삽입할 수 있는가?
기본적으로 BST에는 중복 값이 없어야 하지만, 구현 방식에 따라 중복을 허용하는 변형도 있다. 중복 처리 방법은 설계 시 별도로 결정해야 하는 사항이다.
There must be no duplicate nodes (BST may have duplicate values with different handling approaches).
BST의 장점은?
검색, 삽입, 삭제, 최댓값/최솟값 찾기 등의 연산을 트리 높이에 비례하는 빠른 시간 안에 수행할 수 있다. 자가 균형 BST를 쓰면 데이터가 아무리 많아도 효율적인 속도를 유지하며, 데이터를 정렬된 순서로 출력하는 것도 가능하다.
A BST supports operations like search, insert, delete, maximum, minimum, floor, ceil, greater, smaller, etc in O(h) time where h is height of the BST. To keep height less, self balancing BSTs are used in practice. These Self-Balancing BSTs maintain the height as O(Log n). Therefore all of the above mentioned operations become O(Log n). Together with these, BST also allows sorted order traversal of data in O(n) time.
BST가 Array보다 정렬된 데이터 관리에 유리한 이유는?
데이터가 실시간으로 들어오는 상황에서 항상 정렬 상태를 유지해야 할 때 BST가 유리하다. 예를 들어 온라인 주문이 들어올 때마다 "현재까지 특정 금액 이하 주문이 몇 건인지"를 즉시 파악할 수 있다.
A Self-Balancing Binary Search Tree is used to maintain sorted stream of data.
For example, suppose we are getting online orders placed and we want to maintain the live data in sorted order of prices. For example, we wish to know number of items purchased at cost below a given cost at any moment. Or we wish to know number of items purchased at higher cost than given cost.
BST vs Hash Table 비교는?
단순히 데이터를 찾고, 넣고, 삭제하는 것만 필요하면 Hash Table이 평균적으로 더 빠르다. 하지만 정렬 순서대로 탐색하거나 "가장 가까운 값 찾기" 같은 연산이 필요하면 BST가 적합하다.
Search, insert and delete are faster than array and linked list and slower than hashing, but hashing does not allow sorted traversal, floor and ceil operations.
When we need only search, insert and delete and do not need other operations, we prefer Hash Table over BST as a Hash Table supports these operations in O(1) time on average.