알고리즘...32

이진 검색 트리에서의 삭제

이진 검색 트리서 노드를 삭제할 때에는 다음과 같이 케이스를 나눠서 진행해야 한다.

1. 삭제할 노드에 자식이 없는 경우
2. 삭제할 노드에 자식이 하나 있는 경우
3. 삭제할 노드에 자식이 둘 있는 경우

 

- 자식이 없는 경우

해당 노드를 바로 삭제한다.

 

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

 

- 자식이 하나 있는 경우

해당 노드를 삭제한 뒤 자식 노드를 삭제한 노드의 위치에 놓아준다.

 

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

 

- 자식이 둘 있는 경우

해당 노도를 삭제한 뒤 이진 검색 트리의 서브 트리의 조건을 깨지 않는 자식 노드를 골라 삭제한 노드의 위치에 놓아준다. 이때, 서브 트리의 조건을 깨지 않는 조건은 다음과 같다.

• 오른쪽 자식의 서브 트리에서 가장 작은 값을 가진 노드
• 왼쪽 자식의 서브 트리에서 가장 큰 값을 가진 노드

 

※ 선택된 노드에 자식이 존재하는 경우 이상의 알고리즘을 재귀적으로 반복한다.

 

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

 

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

TreeDelete(t, r, x)
{
    
    if (r = t) then
    {
        root ← DeleteNode(t);
    }
    else if (r = left[p]) then
    {
        left[p] ← DeleteNode(r);
    }
    else
    {
        right[p] ← DeleteNode(r);
    }
}

DeleteNode(r)
{
    if (left[r] = right[r] = NIL) then
    {
        return NIL;
    }
    else if (left[r] = NIL and right[r] ≠ NIL) then
    {
        return right[r];
    }
    else if (left[r] ≠ NIL and right[r] = NIL) then
    {
        return left[r];
    }
    else
    {
        s ← right[r];
        while (left[s] ≠ NIL)
        {
            parent ← s;
            s ← left[s];
        }
        key[r] ← key[s];
        if (s = right[r]) then
        {
            right[r] ← right[s];
        }
        else
        {
            left[parent] ← right[s];
        }
        return r;
    }
}

 

참고문헌

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