BST (Binary Search Tree)

BST
Binary search tree
이진 검색 트리, 이진 탐색 트리
수를 찾기 쉽다.
시간복잡도: log N
최악의 경우 한 쪽으로만 치우칠 수 있다. 그리고 리스트에서 검색하는 것과 같은 시간 복잡도를 가질 수 있고 메모리 공간을 많이 차지할 수 있다.
효율성을 높인 BST를 만들기 위해서 Balancing factor를 만들어서 AVL(Adelson-Velsky and Landis), Splay tree, 2-3-4 tree, red black tree
Python에서는 set과 dictionary를 해시값으로 매핑해서 사용한다.
C++에서는 Binary Search Tree의 변형을 가지고 Set을 만들었다.

순차 탐색, 이진 탐색 - 비교