F·108COMPUTER SCIENCE2025.05.181 MIN READ
Binary Search Tree (BST): The Basics of Data Search and Balancing Aesthetics
이진 탐색 트리(BST): 데이터 검색의 기초와 자가 균형의 미학
Learn BST via Up & Down game. Why DBs use B-Trees over Hash Tables. Deep dive into AVL, Red-Black Trees, Splay Trees, and Treaps.
c
codemapo
INTERDISCIPLINARY DEV · SEOUL
10. Summary
- Logic: Divide and Conquer. Halve the playground every step.
- Performance: O(log N) is incredibly fast. $2^ \approx 1 \text$. 1 Billion items search in 30 steps.
- Risk: Sorted input kills performance ($O(N)$).
- Fix: Use Red-Black Trees in production to guarantee balance.
- Reality: Databases use B-Trees (a BST variant) to minimize Disk I/O.