일지
알고리즘...30
niamdank
2021. 8. 3. 14:48
이진 검색 트리에서의 검색
특정 키를 가진 노드를 검색하는 방법은 다음과 같다.
- 이진 검색 트리의 루트 노드에서부터 비교를 시작한다.
- 주어진 키와 노드의 키를 비교하여 주어진 키가 노드의 키가 같으면 노드를 반환한다.
- 주어진 키가 노드의 키보다 작으면 왼쪽 서브 트리로 이동하여 다시 비교한다.
- 주어진 키가 노드의 키보다 크면 오른쪽 서브 트리로 이동하여 다시 비교한다.
- 위 과정을 노드를 찾거나 말단 노드에 도달할 때까지 반복한다.
이진 검색 트리에서의 검색 알고리즘
TreeSearch(t, x)
{
if (t = NIL or key[t] = x) then return t;
if (x < key[t]) then
{
return TreeSearch(left[t], x);
}
else
{
return TreeSearch(right[t], x);
}
}