이진 검색 트리

계층적인 자료를 표현하기 위해 트리를 사용한다.

여러 개의 키를 저정한다.

다음과 같은 연산들을 지원하는 자료구조

insert - 새로운 키의 삽입

search - 키 탐색

delete - 키 삭제

		search	insert	delete
배열	정렬	O(logn)	O(n)	O(n)
	정렬x	O(n)	O(1)	O(1)
연결리스트	정렬	O(n)	O(n)	O(1)
	정렬x	O(n)	O(1)	O(1)

정렬되거나 정렬되지 않은 배열 혹은 연결리스트를 선택하면 O(n)은 항상 존재함.

탐색트리, 해쉬를 사용해서 보다 효율적인 방법을 구현할 수 있음.

search, insert, delete의 연산은 트리의 높이에 비례하는 시간 복잡도를 가짐.

search

찾으려는 값 k와 노드 key[x]를 비교한다. 같다면 찾은거고 k가 작다면 왼쪽, 크다면 오른쪽으로 노드로 이동한다.

tree_search(x,k):

  if x == None or k == key[x]: #노드가 비어있거나 찾으려는 값을 찾았다면

    return x                          #x 반환

  if k<key[x]:                        #찾으려는 값이 작다면

    return tree_search(left[x],k)  #왼쪽으로 서브트리로 이동

  else:

    return tree_search(right[x],k)

시간 복잡도는 O(h)이다. 

iterative_tree_search(x,k):

  while x!=None and k!=key[x]:

    if k<key[x]:

      x=left[x]

    else:

      x=right[x]

  return x