이진검색트리-1

dynamic set, search structure

- 여러 개의 키를 저장

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

• insert - 새로운 키의 삽입
• search - 키 탐색
• delete - 키의 삭제

- 예 : 심볼 테이블

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

- 정렬된 혹은 정렬되지 않은 배열 혹은 연결 리스트를 사용할 경우 insert, search, delete 중 적어도 하나는 o(n)

- 이진탐색트리, 레드-블랙 트리, avl-트리등의 트리에 기반한 구조들

- direct address table, 해쉬 테이블 등

 

검색트리

- dymamic set 트리의 형태로 구현

- 일반적으로 search, insert, delete 연산이 트리의 높이에 비례하는 시간복잡도를 가짐

- 이진검색트리, 레드-블랙 트리, b-트리 등

 

이진검색트리

- 이진 트리이면서

- 각 노드에 하나의 키를 저장

- 각 노드 v에 대해서 그 노드의 왼쪽 부트리에 있는 키들은 key[v]보다 작거나 같고, 오른쪽 부트리에 있는 값은 크거나 같다.

이진검색트리의 예

** 키 13을 검색

검색 : 15 -> 6 -> 7 -> 13

- 13은 15보다 작으므로 왼쪽 부트리를 검색

- 13은 6보다 크므로 오른쪽 부트리 검색

- 13은 7보다 크므로 오른쪽 부트리 검색

- 13을 만났으므로 여기서 리턴

 

* 이진검색트리의 수도코드

- k = 찾고자 하는 값, x = 현재 기준 노드

- 시간복잡도 : o(h) 여기서 h는 트리의 높이

 

* 위의 그림들은 "영리한 프로그래밍을 위한 알고리즘" 강좌에서 가져왔습니다.