알고리즘...58

B 트리에서의 삽입

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

• x를 삽입할 리프 노드를 찾는다.
• 리프 노드에 여유가 있으면 키를 삽입하고 종료한다.
• 리프 노드에 여유가 없으면
  • 형제 노드에 여유가 있으면 형제 노드에 키를 하나 넘기고 종료한다.
  • 형제 노드에 여유가 없으면 노드를 두 개로 분리한다.
• 부모 노드에 오버플로우 발생 시 부모 노드를 문제 노드로 하여 이상을 반복한다.

 

- B 트리 삽입 알고리즘

새로운 키를 삽입한 뒤 오버플로우에 대한 처리를 진행한다.

 

B 트리 삽입 알고리즘

BTreeInsert(t, x)
{
    x를 삽입할 리프 노드 r을 찾는다;
    x를 r에 삽입한다;
    if (r에 오버플로우 발생) then
    {
        clearOverflow(r);
    }
}

clearOverflow(r)
{
    if (r의 형제 노드 중 여유가 있는 노드가 있음) then
    {
        r의 남는 키를 넘긴다;
    }
    else
    {
        r을 둘로 분할하고 가운데 키를 부모 노드로 넘긴다;
        if (부모 노드 p에 오버플로우 발생) then
        {
            clearOverflow(p);
        }
    }
}

 

- B 트리 삽입 예제

B 트리에 새로운 노드를 삽입할 때 발생한 오버플로우에 대한 처리를 보여준다.

 

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

 

참고문헌

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