이진탐색트리는 말그대로 이진탐색을 위한 트리이다.
노드기준 오른쪽은 자신보다 큰노드, 왼쪽은 작은노드가 들어가기때문에 이진탐색트리의 서브트리또한 이진탐색트리이다. 균형잡인 complete binarytree의경우 탐색 시간복잡도가 높이 h에대해 n개의 자료가 있다고 가정한다면O(h) = O(log2n)이 된다. 하지만 아래와 같이 균형잡힌 트리가 아니라면, 최악의 경우 시간복잡도 n이 나올수도 있으므로 항상
이진탐색트리의 균형을 맞추어주는 알고리즘또한 중요하다.
<이진 탐색트리> 탐색, 삽입, 삭제 알고리즘 및 시간복잡도 분석
# 이진 탐색 트리란? // 이 글은 복붙 및 드래그가 불가하니 밑에 소스파일을 다운로드 해주세요. 이진 탐색 트리(binary search tree)는 이진 트리 기반의 탐색을 위한 자료 구조이다. 이진 탐색 트리
mattlee.tistory.com
'Data Structure' 카테고리의 다른 글
| 그래프(Graph) (0) | 2020.06.14 |
|---|---|
| 위너트리(Winner Tree) (0) | 2020.06.14 |
| 트리 - Max heap (0) | 2020.06.14 |
| 명제식 이진트리 (2) | 2020.06.14 |
| 트리의 순회(inorder, preorder, postorder, levelorder traversal) (0) | 2020.06.14 |