Data Structures, Algorithms, & Applications in C++
Chapter 15, Exercise 63
From the solution for Exercise 62 we know that it is possible to
delete from a nonleaf node so that the worst-case number of disk
acceses is the same as when
deleting from a leaf node. So, assume we are deleting from a leaf node.
The worst-case access analysis is:
h reads to find the leaf to delete from
+ 2(h - 1) reads of nearest siblings
+ h - 2 writes at levels 3 through h
+ 3
The total is 4h - 1.