黑马程序员技术交流社区

标题: 关于二叉树 [打印本页]
作者: 禾呈    时间: 2013-7-19 13:47
标题: 关于二叉树
本帖最后由 杨兴庭 于 2013-7-22 21:30 编辑

在学习数据结构时，我记得，二叉树结构，如果删除一个节点，那么其节点之下的节点都会删除，那么在TreeMap中删除一个元素，是如何实现删除一个元素的。
总不可能 将二叉树从新排列一遍吧？
作者: tonygone    时间: 2013-7-19 14:09
本帖最后由 tonygone 于 2013-7-19 14:11 编辑

TreeMap删除元素：
和新增元素一样，删除元素也可能会破坏二叉树的平衡性，所以也可能需要做调整
假如当前要被删除节点有两个孩子节点，那么只需要将其后继节点查找出来，将其内容换成后继节点的内容，然后问题就转变成删除后继节点的问题.这里是找到当前节点的右子树中最小的那个节点的内容替代之，
  1. Entry<K,V> p = t.right;  
  2.           while (p.left != null)  
  3.               p = p.left;  
  4.           return p;  
复制代码
这样删除有两个孩子节点的节点问题就转换成删除带有一个子节点或者删除叶子节点的问题。接下来一段代码是:
  1. // Start fixup at replacement node, if it exists.  
  2.       Entry<K,V> replacement = (p.left != null ? p.left : p.right);
复制代码
假如这里的p是上述后继节点得来，因为此时p不可能有左孩子，那替代者就是p.right，此时可能为null，或者是被删除节点的子节点少于两个的情况，可能是p.left，也可能是p.right.如果不是null的话就要将后继节点指向到p的parent节点，用于删除当前节点：
  1. replacement.parent = p.parent;  
  2.             if (p.parent == null)  
  3.                 root = replacement;  
  4.             else if (p == p.parent.left)  
  5.                 p.parent.left  = replacement;  
  6.             else  
  7.                 p.parent.right = replacement;  
复制代码
此时p被删除，假如p是红色的，那就不会影响红黑树，但是如果被删除的节点是黑色的，此时因为删掉了一个黑色节点，所以需要对原来的树进行调整：
  1. while (x != root && colorOf(x) == BLACK) {  
  2.          if (x == leftOf(parentOf(x))) {//如果x是左子节点  
  3.              Entry<K,V> sib = rightOf(parentOf(x));  
  4.   
  5.              if (colorOf(sib) == RED) {//如果其兄弟节点为红色  
  6.                  setColor(sib, BLACK);//兄弟节点设为黑色  
  7.                  setColor(parentOf(x), RED);//父节点设置为红色  
  8.                  rotateLeft(parentOf(x));//父节点左旋  
  9.                  sib = rightOf(parentOf(x));  
  10.              }  
  11.   
  12.              if (colorOf(leftOf(sib))  == BLACK &&  
  13.                  colorOf(rightOf(sib)) == BLACK) {//如果兄弟节点的两个儿子都是黑色  
  14.                  setColor(sib, RED);//兄弟节点设置为红色  
  15.                  x = parentOf(x);  
  16.              } else {  
  17.                  if (colorOf(rightOf(sib)) == BLACK) {  
  18.                      setColor(leftOf(sib), BLACK);  
  19.                      setColor(sib, RED);  
  20.                      rotateRight(sib);  
  21.                      sib = rightOf(parentOf(x));  
  22.                  }  
  23.                  setColor(sib, colorOf(parentOf(x)));  
  24.                  setColor(parentOf(x), BLACK);  
  25.                  setColor(rightOf(sib), BLACK);  
  26.                  rotateLeft(parentOf(x));  
  27.                  x = root;  
  28.              }  
  29.          }   
  30.      setColor(x, BLACK);  
复制代码
另外，如果replacement值是空的，就说明被删除节点没有子节点，如果是黑色节点需要进行调整再删除，如果不是就直接删除即可
  1. if (p.color == BLACK)  
  2.                fixAfterDeletion(p);  
  3.   
  4.            if (p.parent != null) {  
  5.                if (p == p.parent.left)  
  6.                    p.parent.left = null;  
  7.                else if (p == p.parent.right)  
  8.                    p.parent.right = null;  
  9.                p.parent = null;  
  10.            }  
复制代码
作者: xscn    时间: 2013-7-19 14:11
本帖最后由 xscn 于 2013-7-19 14:14 编辑

楼主这个问题问的太好了，我从网上查了一下，很详细
程序从排序二叉树中删除一个节点之后，为了让它依然保持为排序二叉树，程序必须对该排序二叉树进行维护：维护可分为如下几种情况：
（1）被删除的节点是叶子节点，则只需将它从其父节点中删除即可。
（2）被删除节点 p 只有左子树，将 p 的左子树 pL 添加成 p 的父节点的左子树即可；被删除节点 p 只有右子树，将 p 的右子树 pR 添加成 p 的父节点的右子树即可。
（3）若被删除节点 p 的左、右子树均非空，有两种做法：
    将 pL 设为 p 的父节点 q 的左或右子节点（取决于 p 是其父节点 q 的左、右子节点），将 pR 设为 p 节点的中序前趋节点 s 的右子节点（s 是 pL 最右下的节点，也就是 pL 子树中最大的节点）。
    以 p 节点的中序前趋或后继替代 p 所指节点，然后再从原排序二叉树中删去中序前趋或后继节点即可。（也就是用大于 p 的最小节点或小于 p 的最大节点代替 p 节点即可）。


image002.png (24.25 KB, 下载次数: 0)

被删除节点只有左子树

被删除节点只有左子树

image003.png (13.6 KB, 下载次数: 0)

被删除节点只有右子树

被删除节点只有右子树

image004.png (25.66 KB, 下载次数: 0)

被删除节点既有左子树，又有右子树-1

被删除节点既有左子树，又有右子树-1

image005.png (15.53 KB, 下载次数: 0)

被删除节点既有左子树，又有右子树-2

被删除节点既有左子树，又有右子树-2




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2