알고리즘...31

이진 검색 트리에서의 삽입

이진 검색 트리에 노드를 삽입하는 방법은 다음과 같다.

1. 삽입하려는 값이 이진 검색 트리에 존재하는지 확인하기 위해 검색을 진행한다.
2. 값이 이미 존재하는 경우 종료한다.
3. 값이 존재하지 않아 말단 노드에 도달한 경우 해당 노드에 삽입하려는 값을 가진 노드를 추가한 뒤 종료한다.

 

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

 

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

TreeInsert(t, x)
{
    if (t = NIL) then
    {
        r = NEW_NODE;
        key[r] ← x;
        left[r] ← NIL;
        right[r] ← NIL;
        return r;
    }

    if (x < key[t]) then
    {
        left[t] ← TreeInsert(left[t], x);
        return t;
    }
    else
    {
        right[t] ← TreeInsert(right[t], x);
        return t;
    }
}

 

참고문헌

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