알고리즘...59

B 트리에서의 삭제

입력된 값을 x라 할 때, x를 삽입하는 방법은 다음과 같다.

• x를 갖고 있는 노드를 찾는다.
• 이 노드가 리프 노다가 아니면 x의 직후 원소 y를 가진 리프 노드 r을 찾아 x와 y를 맞바꾼다.
• 리프 노드에서 x를 제거한다.
• x 제거 후 노드에 언더플로우가 발생하면
  • 키를 가져올 수 있는 형제 노드가 있으면 해당 키를 가져온다.
  • 키를 가져올 수 있는 형제 노드가 없으면 형제 노드와 병합한다. 
• 부모 노드에 언더플로우 발생 시 부모 노드를 문제 노드로 하여 이상을 반복한다.

 

- B 트리 삭제 알고리즘

주어진 키를 삭제한 뒤 언더플로우에 대한 처리를 진행한다.

 

B 트리 삭제 알고리즘

BTreeDelete(t, x, v)
{
    if (v가 리프 노드가 아님) then
    {
    	x의 직후 원소 y를 가진 리프 노드를 찾는다;
        x와 y를 맞바꾼다;
    }
    리프 노드에서 x를 제거하고 이 리프 노드를 r이라 한다;
    if (r에서 언더플로우 발생) then
    {
    	clearUnderflow(r);
    }
}

clearUnderflow(r)
{
    if (r의 형제 노드 중 키를 하나 내놓을 수 있는 여분을 가진 노드가 있음) then
    {
        r이 키를 넘겨받는다;
    }
    else
    {
        r의 형제 노드와 r을 병합한다;
        if (부모 노드 p에 언더플로우 발생) then
        {
        	clearUnderflow(p);
        }
    }
}

 

- B 트리 삭제 예제

B 트리에 주어진 노드를 삭제할 때 발생한 언더플로우에 대한 처리를 보여준다.

쉽게 배우는 알고리즘 B 트리 그림 5-20

 

참고문헌

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