일지
알고리즘...59
niamdank
2021. 9. 29. 11:17
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 트리에 주어진 노드를 삭제할 때 발생한 언더플로우에 대한 처리를 보여준다.