📚 Reference

📜 Chapter

AVL (Adelson-Velsky and Landis)

‣

Binary Tree

‣

Heap

Red-black tree

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을 만들었다.

BST - 시간 복잡도

원하는 값 1개 찾기: 탐색(Search), 삽입(Insert), 삭제(Delete)

• BST의 주요 연산(탐색, 삽입, 삭제)은 모두 트리의 높이(h)에 비례한다.