Tree Structure 노트3 - Binary Search Tree

이진 탐색트리(Binary Search Tree)

 

탐색(Searching) 문제의 특징

- 얼마나 빨리 탐색할 것인가? Input Size = N items./ 중간 새로운 insert를 허용하는가?/ 어떤 데이터의 삭제를 dynamic하게 허용할것인가?/ 얼마나 다양한 질의(query)를 지원하는가?

-insert, delete를 허용해주면서 빠른시간내에 O(logN)만에 찾을수 있게 만들어주는 트리

 

Multi-Dimension Query - 데이터베이스 관리 시스템을 사용한 온라인 분석 처리를 위한 쿼리 언어

 

Tree 형식의 탐색구조의 장점

- O(log n) 시간의 삽입 삭제,  O(log n) 시간의 탐색, 다양한 변이, 어떤 특수한 종류의 동작을 빠르게 구현해 줄 수 있는가?

 

Binary Search Tree의 의미

- Linear List의 문제 (탐색에서의 문제)

- Binary Search Tree에서 제공해야하는 동작 -> Search, Find and Delete, Insert, Depth

 

Binary Search Tree에서 k-번째 원소 찾기 (Selection Problem)

- 각 노드 x마다 추가 정보 설정 Left(x), Right(x) / 왼쪽 오른쪽 subtree의 크기

//BST에서 배열로 sorting된 순서는 Inorder

 

Binary Search Tree할때 worst case가 생길수 있는것은 균형트리로.

Linked List 모양의 skewed tree의 루트를 바꿔서 (adjust해서) 균형트리로 만드는 고급기법있음. (AVL트리, 레드블랙트리)

 

Binary Search Tree의 탐색성능 개선할때는 - 말단까지의 거리를 짧게 한다.(Tree의 maximum depth를 minimize한다)

 

좋은 자료구조 목적 -> Search되고 insert되고 delete되게. 전부다 O(logN)으로 되게. (BST의 목적)

(Vector의 Search는 O(log2N), insert는 O(N), delete = O(N)..)