Emong's Factory

[자료 구조][알고리즘] 이원 탐색 트리(binary search tree)

이원 탐색 트리(binary search tree) 이진 트리로서 공백일 수 있다. 만약 공백이 아니라면 다음 성질을 만족한다. 1) 모둔 원소는 키를 가지며, 어떤 두 원소도 동일한 키를 갖지 않는다. 2) 왼쪽 서브트리에 있는 키들은(만약 있다면) 그 루트의 키보다 작다. 3) 오른쪽 서브트리에 있는 키들을(만약 있다면) 그 루트의 키보다 크다. 4) 왼쪽과 오른쪽 서브트리도 모두 이원 탐색 트리이다. 첫 번째 트리가 이진 탐색 트리가 아닌 이유는 10이 15보다 작음 에도 오른쪽 자식에 위치해 있기 때문이다. 이진 탐색 트리는 정렬된 트리이다. 이원 탐색 트리의 탐색 키 값이 k인 원소를 탐색한다고 가정하자. 탐색은 루트에서부터 시작하는데 만약 루트가 NULL이면 탐색 트리는 원소를 갖지 않으므로 ..