Page 551 Exercise 17

Page 551 Exercise 17

The modification of the insertb algorithm consists of these lines from Program 11. 2:

/* node p has to be split*/
Let p and q be defined as in Eq. (11.5);

With the following lines:

Let Parent = p's parent
Let K_i = the key in Parent which points to P
Let q = p's right sibling
If q→n ≤ m-1 then begin
/*the right child has space so shift entries*/
      Insert K_i into the appropriate place in q
      Insert x into K_i
      Output(p,q,parent) to disk
      Exit
end
else begin
/*use the splitting technique of Bayer &McCreight*/
    Insert p's keys into the array Key in sorted order
   Insert K_i into the array Key in sorted order
   Insert x into the array Key in sorted order
   Insert q's keys into the array Key in sorted order
   Insert Key(s) 1 .. _⌊ (2m-2)/3) _⌋ into p

   Insert Key _⌊ (2m+1)/3 _⌋ into K_i

   Insert Key(s) m .. (m + _⌊ (2m-2)/3 _⌋ -1) into q

   Insert Key (2m -_⌊ 2m/2 _⌋) into K_i+1

   Insert Key(s) (2m - _⌊ 2m/3 _⌋+1) .. 2m into R

   Set p→n to _⌊ (2m-2)/3 _⌋

   Set q→n to _⌊ (2m-1)/3_⌋

   Set r→n to_⌊ 2m/3_⌋

   Set Parent→n to Parent→n+1

   Set _⌊ (2m-2)/3 _⌋+1 .. m-1 key values in p to void and pointers to NULL
   Set q's _⌊ (2m-1)/3_⌋ +1 .. m-1 key values to void and pointers to NULL
   Set r's _⌊ 2m/3 _⌋ +1 ... m-1 key values and pointers to nil
   Output(Parent,p,q,r) to disk
   exit

end