BST (Binary Search Tree)

BST
Binary Search Tree
이진 검색 트리, 이진 탐색 트리
데이터를 효율적으로 관리하고 검색하기 위해 설계된 아주 영리한 자료구조이다.
정렬된 상태를 유지하는 나무
이진 탐색 트리(Binary Search Tree, BST)는 이진 탐색(Binary Search)의 원리를 연결 리스트 형태의 트리 구조로 옮겨놓은 자료구조이다.
수를 찾기 쉽다.
최악의 경우 한 쪽으로만 치우칠 수 있다. 그리고 리스트에서 검색하는 것과 같은 시간 복잡도를 가질 수 있고 메모리 공간을 많이 차지할 수 있다.
효율성을 높인 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을 만들었다.