알고리즘...30

이진 검색 트리에서의 검색

특정 키를 가진 노드를 검색하는 방법은 다음과 같다.

1. 이진 검색 트리의 루트 노드에서부터 비교를 시작한다.
2. 주어진 키와 노드의 키를 비교하여 주어진 키가 노드의 키가 같으면 노드를 반환한다.
3. 주어진 키가 노드의 키보다 작으면 왼쪽 서브 트리로 이동하여 다시 비교한다.
4. 주어진 키가 노드의 키보다 크면 오른쪽 서브 트리로 이동하여 다시 비교한다.
5. 위 과정을 노드를 찾거나 말단 노드에 도달할 때까지 반복한다.

 

쉽게 배우는 알고리즘 이진 검색 트리 그림 5-4

 

이진 검색 트리에서의 검색 알고리즘

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);
    }
}

 

참고문헌

한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘