이진 탐색 트리

• 트리 중 이진 탐색 트리는 아래와 같은 조건을 만족하는 트리다.

  • 왼쪽 서브트리는 키보다 작은 값을 갖는 노드로 구성되어 있다.
  • 오른쪽 서브트리는 키보다 큰 값을 갖는 노드로 구성되어 있다.

• 탐색 과정

  • 루트와 주어진 키 비교
  • 루트보다 작다면 왼쪽, 크다면 오른쪽 서브트리로 이동
  • 루트와 같다면 종료

• 중위순회를 통해 데이터 정렬 효과 있음

• 성능 특성

  • 평균: O($\log N$)
  • 최악: O(N)
    • 정렬/역순/최대최소가 번갈아 나타나는 경우
    • 최악의 경우를 방지하기 위해 균형을 맞춰준다.

• ADL로 구현

  • 올바른 트리가 이미 존재한다고 가정하자.

  binaryTreeSearch(T, search_key)
  	x <- T;
  	while (x != null) do {
  		if (x.key > search_key) then x <- x.left;
  		else if (x.key < search_key) then x <- x.right;
  		else return x;
  	}
  	return null;
  end binaryTreeSearch()
  

• 파이썬 코드로 구현

  def binaryTreeSearch(T, search_key):
  	x = T
  	while x != null:
  		if x.key > search_key: x = x.left
  		else if x.key < search_key: x = x.right
  		else return x
  	return None