이진탐색드리(Binary Search Tree)

complete binary tree

 

 

균형잡혀있지 않은 이진트리

 

 

이진탐색트리는 말그대로 이진탐색을 위한  트리이다.

노드기준 오른쪽은 자신보다 큰노드, 왼쪽은 작은노드가 들어가기때문에 이진탐색트리의 서브트리또한 이진탐색트리이다.  균형잡인 complete binarytree의경우  탐색 시간복잡도가 높이 h에대해 n개의 자료가 있다고 가정한다면O(h) = O(log2n)이 된다. 하지만 아래와 같이 균형잡힌 트리가 아니라면, 최악의 경우 시간복잡도 n이 나올수도 있으므로 항상

이진탐색트리의 균형을 맞추어주는 알고리즘또한 중요하다.

 

 

 

 

 

 

 

 

<이진 탐색트리> 탐색, 삽입, 삭제 알고리즘 및 시간복잡도 분석