[자료구조] BST : 이진 탐색 트리

김희성의 개발자 면접 cs 강의/ 스터디

 

Binary Search Tree

• 비선형 자료구조
• 논리적으로 데이터 정렬되어있음
• 정렬된 상태에서도 데이터의 삽입/삭제 시간복잡도 : O(logN)
•  시간복잡도
  • i번째 데이터에 접근(Access) : *NONE
  • 데이터의 삽입/삭제 : O(logN)
  • X라는 데이터에 접근 : O(logN)
  • X기준 Ceiling/Floor 에 접근 : O(logN)
• BST 는 빠른 검색을 위해 자주 사용된다.
• Ordered Map (Java 에서는 TreeMap or TreeSet) 이 BST 이다.
  •  Map : Key-Value 쌍으로 저장, Set : Key 값만 저장 (Key는 중복될 수 없다.)
• Red-Black Tree (대표적 BST.  java의  TreeMap or TreeSet이 이걸로 설정되어있다.)
• MySQL Database 에서 Table 의 Index 는 B-Tree 로 되어있다. 이는 BST 와는 다르다.