1.이진탐색트리 (BST)

이진탐색트리는 오름,내림차순이 가능한 리스트 혹은 정렬된 구조의 자료형에서,

처음 크기의 값의 중간값을 임의의 값으로 정하고, 크고 작음 여부를 판별해나가는 방식으로 비교한다.

 

 

 

11을 찾기위해 이진탐색 트리를 사용할 경우, 중간값인 6보다 크거나 작음을 판별하기만 하면 되기 때문에

좌측 서브트리는 고려할 필요가 없다, 따라서 필요한 최소 검색 시간이 매우 줄어들게 된다.

 

『시간 복잡도』

 

전체 순회의 경우,

최상의 결과일 때 시간복잡도는 Ω(1) [ 첫번째에 찾은 경우 ]

최악의 결과일 때 시간복잡도는 O(n) [ 마지막에 찾은 경우 ] 이지만

 

이진탐색트리의 검색 시간 복잡도는 Ω(1), O(H) 로, 트리의 높이에 따라서 달라지긴 하나,

전체 순회보다 빠르다고 할 수 있다.

 

 

 

 

 

 

def binarySearch(array, value, low, high):
	if low > high:
		return False
	mid = (low+high) / 2
	if array[mid] > value:
		return binarySearch(array, value, low, mid-1)
	elif array[mid] < value:
		return binarySearch(array, value, mid+1, high)
	else:
		return mid

파이썬에서의 이진트리방식, 위 그림과 같이 중간값을 구해 한 차수를 탐색한다.

 

코드 출처: https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98