이진 탐색 트리
위키백과, 우리 모두의 백과사전.
 |
이 문서의 내용은 출처가 분명하지 않습니다. 지금 바로 이 문서를 편집하여, 참고하신 문헌이나 신뢰할 수 있는 출처를 주석 등으로 표기해 주세요. 검증되지 않은 내용은 삭제될 수도 있습니다. 내용에 대한 의견은 토론 문서에서 나누어 주세요. |
컴퓨터 과학에서 이진 탐색 트리(BST: binary search tree)는 다음과 같은 속성이 있는 이진 트리 자료 구조이다.
- 각 노드에 값이 있다.
- 각 노드의 키값은 모두 달라야 한다.
- 값들은 완전 순서가 있다.
- 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.
- 노드의 오른쪽 서브트리에는 그 노드의 값보다 크거나 같은 값들을 지닌 노드들로 이루어져 있다.
이진 탐색 트리 에서의 검색 [편집]
- 이진탐색트리에서 키 x를 가진 노드를 검색하고자 할때, 트리에 해당 노드가 존재하면 해당 노드를 리턴하고, 존재하지 않으면 NIL을 리턴한다.
- 검색하고자 하는 값을 루트노드와 먼저 비교하고, 일치할경우 루트노드를 리턴한다.
 |
이 글은 컴퓨터 과학에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다. |
