[자료구조] Tree: Binary Search Tree

1. 이진 탐색 트리 (Binary Search Tree, BST)

• 정렬된 이진 트리입니다. 
  • 왼쪽 노드는 루트보다 작고, 오른쪽 노드는 루트보다 큽니다.
• 검색에 특화된 이진트리 입니다.

 

특징

• 정렬되어 있어 탐색, 삽입 삭제 연산이 효율적입니다.

 

Time Complexity

• $O(logN)$

 

2. 종류

AVL Tree (균형 이진 트리)

Red-Black Tree (균형 이진 트리)