티스토리 뷰
Binary search tree는 탐색, 삽입, 삭제, 연산에 있어서 지금까지 공부했던 어떤 자료구조보다도 성능이 좋다고 한다!! 열심히 공부할 이유가 되는군!!
[Definition]
(1) 모든 원소는 키를 가지며, 어떤 두 원소도 동일한 키를 갖지 않는다
(2) 왼쪽 subtree에 있는 키들은 루트의 키보다 작다
(3) 오른쪽 subtree에 있는 키들은 루트의 키보다 작다
(4) 왼쪽, 오른쪽 subtree도 모두 binary search tree이다.
BST(binary search tree, 앞으로는 BST라고 부를게요) 의 가장 큰 특징은, inorder로 traverse했을 때 작은 순서대로 라는것 !!
'Algorithm > 이론' 카테고리의 다른 글
| [자료구조] 트리/Prim's Algorithm (0) | 2019.06.03 |
|---|---|
| [자료구조] 트리/Kruskal's Algorithm (0) | 2019.06.03 |
| [자료구조] heap/최대 heap에서 delete (0) | 2019.05.31 |
| [자료구조] heap/ 최대 heap에서 insert (0) | 2019.05.31 |
| [자료구조] heap(힙), priority queue(우선순위 큐) (0) | 2019.05.31 |