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

데이터 구조에 B-트리 삽입


여기서 B-트리에 삽입을 수행하는 방법을 살펴보겠습니다. 아래와 같은 B-Tree가 있다고 가정합니다. -

B-트리의 예 -

데이터 구조에 B-트리 삽입

요소를 삽입하는 아이디어는 BST와 매우 유사하지만 몇 가지 규칙을 따라야 합니다. 각 노드에는 m개의 자식과 m-1개의 요소가 있습니다. 하나의 노드에 요소를 삽입하면 두 가지 상황이 발생합니다. 노드에 m-1보다 작은 요소가 있으면 새 요소가 노드에 직접 삽입됩니다. m-1개의 요소가 있는 경우 모든 요소와 삽입될 요소를 취하여 그 중 중간값을 취하고 동일한 기준을 수행하여 중간값을 해당 노드의 루트로 보낸 다음 두 개를 만듭니다. 노드의 왼쪽 절반과 오른쪽 절반에서 별도의 목록

트리에 79를 삽입한다고 가정합니다. 처음에는 루트로 검사합니다. 이 값은 56보다 큽니다. 그런 다음 가장 오른쪽의 하위 트리로 이동합니다. 이제 81보다 작으므로 왼쪽 하위 트리로 이동합니다. 그런 다음 루트에 삽입됩니다. 이제 세 가지 요소[66, 78, 79]가 있습니다. 중앙값은 78이므로 78이 올라가고 루트 노드는 [79, 81]이 되며 노드의 요소는 두 개의 노드로 분할됩니다. 하나는 66, 다른 하나는 79입니다.

79를 삽입한 후의 B-Tree.

데이터 구조에 B-트리 삽입

알고리즘

BTreeInsert(루트, 키)-

입력 − 트리의 루트와 삽입할 키 키가 목록에 없다고 가정합니다.

x := Read root
if x is full, then
   y := new node
   z := new node
   Locate the middle object oi, stored in x, move the objects to the left of oi in to node y
   Move the object to the right of oi into node z.
   If x is an index node, then move the child pointers accordingly
   x->child[1] := address of y
   x->child[2] := address of z
end if