let k and 2k be keys in a b-tree, b.
assume that the depth of b is reduced if the key k is deleted.
it necessary case if delete key 2k instead, depth of b reduced well?
i'm having hard time visualize , solve this, can please show me how should think , solve this?
assuming classical b-tree constrains number of keys per node: precondition node merge involving root - , reduction in height - root have 1 key , 2 children, both of have minimum allowable number of keys. state of affairs @ deeper levels of tree not matter.
if top of tree looks described, height reduction can triggered deleting root's key or 1 of keys in 2 children. deletion direct, or result of change rippling after deletion deeper in tree.
in case there many constellations deletion of key 2k not trigger height reduction under same circumstances. there many conditions can prevent height reduction after deletion of key 2k: key residing in 'safe' node (with more minimum number of keys) or having 'safe' parent, existence of 'safe' siblings somewhere along path borrowing becomes possible, etc. pp.
visualisation resources on web discussed in topic here:
Comments
Post a Comment