tag:blogger.com,1999:blog-18002060.post2115284086667883569..comments2023-03-03T14:17:07.975+00:00Comments on ARQtick: A small mystery about deletion in T-TreesAndyShttp://www.blogger.com/profile/18033124086179105115noreply@blogger.comBlogger1125tag:blogger.com,1999:blog-18002060.post-56459223834972421252009-11-12T21:54:33.033+00:002009-11-12T21:54:33.033+00:00My analysis is that the original paper does not co...My analysis is that the original paper does not consider this case. A half-leaf will less than the minumum could get pulled up. My thought is to not worry about it then, but to generalize the underflow-on-delete to notice that it's <i>way</i> low, not just one low, and pull up as many as it can rather than assuming 1.<br /><br />(well, don't empty the leaf if it totally fills the internal node, since that could lead to alternating inserts/deletes destroying and re-creating the leaf each time. So leave two in the leaf and two empty in the internal node, in that case)<br /><br />I'm wondering about a different issue, and found your post when Googling for T-tree balancing.John M. Długosznoreply@blogger.com