算法（29）：deletion-9.6

这一节是 BST 中逻辑最复杂的一块但不涉及新数学只是指针操作的三种情况分类。Page 29章节过渡与总结这张 PPT 的上半部分是符号表实现的总结表其中 BST 行的delete成本当前被标记为???未定。下半部分用大标题说明Next. Deletion in BSTs.。它告诉你删除操作是 BST 这一节最后要攻克的内容。Page 30一种“慵懒”的删除方案墓碑标记物理内容一种简单的删除方法是找到要删除的键不把它从树里移除而是把该节点的value置为null键保留在树中作为占位符。查找时的行为get(key)在找到键后检查value是否为null。如果是返回null相当于键不存在。成本插入、查找和删除的平均成本依然是~2 ln NN是历史上插入过的总键数包括已被标记删除的。即使你只保留了少量实际数据N也会持续增长。物理缺陷被标记删除的键依然占用节点内存包括键对象和节点对象且会拉长查找路径。一旦删除操作频繁树上会布满“墓碑”Tombstone导致树高增大、内存泄漏。因此这是一种不实用的方案只是用来引出“即时删除”的必要性。Page 31删除最小键deleteMin物理动作从根开始沿着left指针一直向下走直到遇到一个节点x它的left null即当前子树的最小节点。把这个节点x替换成它的right子节点返回x.right给父节点。父节点收到这个返回值后通过x.left deleteMin(x.left)把返回值挂接到左指针位置。回溯过程中更新路径上所有节点的count。物理效果如果最小节点没有右子节点父节点的左指针直接指向null该节点被完全断开。如果有右子节点右子节点升上来替代最小节点的位置。Page 32删除只有一个或无子节点的普通节点物理分类在删除任意节点时首先找到它和put一样递归下降。Case 00 个子节点x.left null x.right null。直接返回null给父节点父节点将对应的左/右指针置空。堆上的节点对象断开引用GC 回收。Page 33删除只有一个子节点的节点Case 11 个子节点如果x.right null返回x.left左子树升上来。如果x.left null返回x.right右子树升上来。父节点接收到返回值后直接挂接到原来的指针位置。被删除的节点只有一个子节点时用它的子节点替代它就能保持 BST 性质。Page 34删除有两个子节点的节点Hibbard 删除——这是最复杂的部分物理问题当节点有两个非空子节点时你不能简单地让左子树或右子树升上来会破坏 BST 序左子树整体小于原节点右子树整体大于原节点但它们之间没有直接的大小关系。也叫即时删除。物理方案Hibbard 删除1962找到目标节点t要删除的节点。找t的后继节点Successor——即右子树中最小的节点一路沿left走到null的那个节点。在 BST 中后继节点是大于t且最小的那个恰好可以作为t的“合法替身”。把t的值用后继节点的值覆盖键和值。在t的右子树中删除该后继节点deleteMin因为后继节点已经被复制上去了原位置需要清除。把t的左子树指针指向原来的左子树右子树指针指向删除后继节点后的右子树。物理结果树中不再存在t的原始记录但所有键值对的顺序保持不变树依然满足 BST 性质。Page 35Hibbard 删除的 Java 实现代码结构与你之前学的put类似但在命中目标后增加了三种情况的分支if (x.right null) return x.left;只有左子节点if (x.left null) return x.right;只有右子节点两个子节点都存在Node t x;x min(t.right);找后继x.right deleteMin(t.right);删除右子树中的后继节点并挂回右指针x.left t.left;原左子树直接挂上返回x给上层并在回溯中更新路径上所有节点的count。物理关键deleteMin(t.right)会沿着右子树的最左端下降并删除节点随后返回右子树的根地址正是为了把它挂到x.right上。整体结构和put完全一致。Page 36Hibbard 删除的缺陷——最重要的学术观点PPT 原话Not symmetric.不对称。该算法总是选取后继节点右子树最小值来替代被删除的节点而不是随机选择前驱或后继。物理后果在一系列插入和删除的混合操作后树结构会逐渐偏向一侧因为总是用右子树的最小值填补空缺等价于不断从右子树抽取节点导致树高增长速度比随机 BST 更快。量化结论长期使用后树高预计增长到~√N而不是~log N。这意味着原本期望的对数级性能会退化到亚线性但远高于对数的级别。学术状态PPT 写明Longstanding open problem. Simple and efficient delete for BSTs.长期悬而未决的问题。至今没有找到像插入那样简单的、能保持完全对称的删除算法。Page 37更新后的总结表现在 BST 行的delete平均成本被标记为√N平方根而不是log N。其他操作如rank、floor也会受到退化树高的影响趋势相同。物理原因删除操作破坏了树原先的随机性。在 Hibbard 删除过程中你不会撤销它引入的不对称性因此算法性能会逐渐下滑。Page 38章节结束这一页是3.2 Binary Search Trees的收尾页。完成这一节后BST 的全部内容已经结束。下一节3.3 Red-Black BSTs会引入一种“自平衡”机制通过固定规则来消除删除导致的不对称性从而保证所有操作始终维持在log N。一、lazy approachQLeave key in tree to guide search (but dont consider it equal in search).这里为什么不能把删除和查找看作一样是因为删除会导致memory overload吗A如果把删除和查找“看作一样”即物理上把节点从树中摘除那就不叫“惰性删除”Lazy Deletion了那叫“即时删除Hibbard 删除”。你现在看的这页 PPTPage 30讲的正是另一种方案——惰性删除。它选择“不把删除和查找看作一样”而是故意“把键留下”原因你猜对了一半直接原因是为了避免复杂重组但最终确实会导致 memory overload内存过载。1. “把键留下”到底在做什么物理上它只是把节点的value设置为null但key和left、right指针都原封不动地保留在树里。查找时的行为顺着路径找到该键。发现value null返回null告知调用者“键不存在”。插入时的行为顺着路径找到该键。发现value null把新值写进去相当于“复活”了它且无需新建节点。2. 为什么不用“查找”的方式即时删除去处理因为即时删除Hibbard 删除在物理上会改变树的拓扑结构重接指针。它复杂且不对称会导致树性能退化退化为√N。惰性删除的策略是“我宁愿留着这个节点作为路标也不愿去动那些复杂的指针重组。”“留作路标”的物理价值如果直接删除键并把节点摘除某条查找路径上的指针会发生变化可能要用后继节点替代。而惰性删除保留了这个节点所以所有现有的搜索路径结构完全不变。get、put依然沿着完全相同的指针走下去只是走到最后发现值已经为空。这避免了在删除时修改树结构。3. 你的猜测“会导致 memory overload” 完全正确但这是结果不是原因你猜对了最终后果惰性删除会导致内存膨胀。因为被标记删除的节点依然占用堆内存Node对象头 key引用 value引用 左右指针。树的高度不会因为删除而降低反而会随着历史插入而持续增长因为删掉的节点还在路径上。PPT 里写的N历史上插入过的总键数会不断增大而有效的N实际存在的键可能很小。这意味着查找时依然要遍历很长的路径即使其中很多节点都已经是“墓碑”了。但这不是“原因”而是“后果”。PPT 提出惰性删除的原因是为了避免复杂的删除逻辑然后警告你如果这样做会让树越来越大。这就是为什么它说这是一种“Unsatisfactory solution”并最终指向 Hibbard 删除即时删除尽管它也有自己的问题。二、删除最小值Q我又在想一样的问题了我认为这一回这个代码去掉最后一行的return x好像是可以的。好像还是那个逻辑那我想大概是因为我没有明白。让我们来重新捋一下。①这是一个会逐层向下访问子节点的binary search tree的递归函数。当它访问到最底层的时候将会去遍历它的左右节点。如果要删除的那个节点没有左节点了那么就返回它右节点的地址。②每一层递归访问我们能知道的仅仅只有该层的node x引用而不包括上一层。因此我们想要把被删除节点的子节点给返回必须要写一个return语句。③由于要书写return语句那么该函数体内必须有一个赋值语句用来接收return的值。所以必须写 x.left deleteMin(x.left);④如果我们现在所在的逻辑层不是底层跟它的上一层之间而是在中间层级这个x.left语句依旧需要获得一个返回值即便该层已经知晓本层node x引用这是为了保证递归逻辑正确。因此中间层每层递归返回也需要return一个引用那就是node x的引用。⑤之所以不写这个return x会出错有几个原因。首先是这个函数已经声明了返回值类型是node那么每一层就必须要返回一个node。其次因为我们有一个x.left xxx的赋值语句我们需要让这个赋值语句成立需要返回值。最后如果我们把return x都给去掉我们在最下面那一层就需要知道倒数第二层的引用这将把函数变复杂。但写到这里我突然又在想为什么非要让倒数第一层知道倒数第二层的引用呢在这个情况下好像不这样也可以。例如if(x.left.leftnull) 相应条件语句;就是这里的访问看起来会特别麻烦特别慢。A一到五点是对的。你提出的方法物理上可行但实现起来特别麻烦、特别慢而且特别容易出错。你提出的“检查x.left.left”的方案本质上是“提前窥探两层”而不是标准递归的“走到尽头再处理”。我们直接对比两种方案在物理上的差异1. 你的方案不return改为void 提前判断你的设想大概是javaprivate void deleteMinVoid(Node x) { // 假设 x 和 x.left 都不为 null if (x.left.left null) { // 目标节点是 x.left要删除它并把它的右子树接上来 x.left x.left.right; // 需要更新 x 的 count x.count 1 size(x.left) size(x.right); return; } deleteMinVoid(x.left); x.count 1 size(x.left) size(x.right); }这个方案能工作吗能在物理上它确实能把x.left替换掉。但它在物理上引发了三个新问题问题一边界情况爆炸如果树的根就是最小节点root.left null呢你的函数需要额外判断x.left null。如果树是空的root null呢你需要单独处理。如果x.left ! null但x.left.left null是触发条件意味着你每一层都要多判断一次x.left是否存在。代码里的if分支会翻倍。问题二count更新滞后你的x.count 1 size(x.left) size(x.right);只在if分支里和递归调用后更新。如果递归调用发生在x.left内部路径上的count确实会在回溯时更新。但是如果x.left本身被删除了你的if分支执行了那一层的count更新了但它的父节点即上一层的x只会在退出deleteMinVoid后更新一次。如果删除发生在较深层路径上每一层的count更新都会在各自的栈帧中处理这一点和你写的代码一致。但为了处理边界情况你必须在函数开头额外检查x null || x.left null否则会抛出空指针异常。问题三函数签名无法统一如果删除操作需要知道“父节点是谁”那么deleteMinVoid只能在“确定x不是要删除的节点”的情况下才能被调用。如果根节点本身就是要删除的最小节点你必须单独处理根节点情况代码变得更长也更难维护。2. 标准方案返回Node 统一逻辑javaprivate Node deleteMin(Node x) { if (x.left null) return x.right; x.left deleteMin(x.left); x.count 1 size(x.left) size(x.right); return x; }为什么这个方案物理上更干净它不需要预先知道父节点是谁每个节点只处理自己和自己的子节点。if (x.left null)表示“我就是要删除的节点”不需要访问x.left.left来判断。它用同一个“挂接”模式覆盖了所有情况无论是删除根、删除叶子、删除只有一个子树的节点return的逻辑都能处理。边界情况统一由递归处理空树调用deleteMin(null)直接返回null不会报错。你在代码中不会看到任何关于x.left是否存在的额外判断。3. 为什么“返回到上一层”是必须的你问“为什么非要让倒数第一层知道倒数第二层的引用”——实际上标准方案里倒数第一层并不知道倒数第二层的引用。它只是把x.right的地址抛回给上一层由上一层通过x.left deleteMin(x.left);来接收。关键物理点return x传递的是“地址”而不是“父节点”。父节点上一层用它来更新自己的left指针从而把结果挂载回去。最底层只需要返回它所知道的那个地址可能是被删除节点的右子节点也可能是null它不需要知道是谁在等它。这种“上行传递”确保了每一层都只处理自己职责范围内的事而不需要向下窥探两层因此代码更短、分支更少、边界条件也更少。你最后那句“访问看起来会特别麻烦特别慢”总结得很准确——你的方案在物理上可行但它相当于在递归路径上添加了额外的判断而标准方案用一个return把这件事做了。