Computer >> 컴퓨터 >  >> 프로그램 작성 >> 프로그램 작성

데이터 구조의 B-트리 삭제


여기서 B-Tree에서 노드를 삭제하는 방법을 살펴보겠습니다. 아래와 같은 BTree가 있다고 가정합니다 -

B-트리의 예 -

데이터 구조의 B-트리 삭제

삭제에는 두 부분이 있습니다. 먼저 요소를 찾아야 합니다. 그 전략은 쿼리와 같습니다. 이제 삭제를 위해 몇 가지 규칙에 주의해야 합니다. 하나의 노드에는 최소 m/2개의 요소가 있어야 합니다. 따라서 하나의 요소를 삭제하고 m-1개 미만의 요소가 남아 있으면 자동으로 조정됩니다. 전체 노드가 삭제되면 자식 노드가 병합되고 크기가 m과 같으면 두 부분으로 나누면 다시 중앙값이 올라갑니다.

46을 삭제한다고 가정합니다. 이제 두 개의 자식이 있습니다. [45], [47, 49], [45, 47, 49]가 합쳐지면 47이 올라갑니다.

데이터 구조의 B-트리 삭제

알고리즘

BTreeDelete(x, 키) −

입력 − 트리의 루트, 삭제할 키

키가 목록에 있다고 가정합니다.

if x is leaf, then
   delete object with key ‘key’ from x
else if x does not contain the object with key ‘key’, then
   locate the child x->child[i] whose key range is holding ‘key’
   y := x->child[i]
   if y has m/2 elements, then
      If the sibling node z immediate to the left or right of y, has at least one more
      object than m/2, add one more object by moving x->key[i] from x to y, and
      move that last or first object from z to x. If y is non-leaf node, then last or first
      child pointer in z is also moved to y
   else
      any immediate sibling of y has m/2 elements, merge y with immediate sibling
   end if
   BTreeDelete(y, key)
else
   if y that precedes ‘key’ in x, has at-least m/2 + 1 objects, then
      find predecessor k of ‘key’, in the sub-tree rooted by y. then recursively delete k
      from the sub-tree and replace key with k in x
   else if ys has m/2 elements, then
      check the child z, which is immediately follows ‘key’ in x
      if z has at least m/2+1 elements, then
         find successor k of ‘key’, in the sub-tree rooted by z. recursively delete k
         from sub-tree, and replace key with k in x
   else
      both y and z has m/2 elements, then merge then into one node, and push ‘key’
      down to the new node as well. Recursively delete ‘key’ from this new node
   end if
end if