【数据结构与算法】系列十一 - 删除二叉搜索树节点

。。。。

一、删除节点

删除二叉搜索树节点无非就三种情况：删除叶子节点、删除度为1的节点、删除度为2的节点。

1.1. 删除叶子节点

叶子节点直接删除即可，例如图例中的节点3、5、8、10。

删除节点是左子节点：

1 2	node == node.parent.left node.parent.left = null

删除节点是右子节点：

1 2	node == node.parent.right node.parent.right = null

删除节点是根节点：

1 2	node.parent = null root = null

1.2. 删除度为1的节点

用子节点替代原节点的位置，即可实现删除度为1的节点。例如删除上图中的节点4、9。

假设child是node.left或者child是node.right，用child替代node的位置：

如果node是左子节点：

1 2	child.parent = node.parent node.parent.left = child

如果node是右子节点：

1 2	child.parent = node.parent node.parent.right = child

如果node是根节点：

1 2	root = child child.parent = null

1.3. 删除度为2的节点

删除度为2的节点，需要保证二叉搜索树的性质：左子树节点值小于右子树节点值。因此先用前驱或者后继节点的值覆盖原节点的值，然后删除相应的前驱或者后继节点，这样就能够满足所需。

如果一个节点的度为2，那么它的前驱、后继节点的度只可能是1和0。

例：删除节点5，找到节点5的前驱或后继并替换。

1.4. 完整代码

// 删除值对应的节点
public void remove(E element) {
  remove(node(element));
}

// 删除节点
private void remove(Node<E> node) {
  if (node == null) return;
  
  size--;
  
  if (node.hasTwoChildren()) { // 度为2的节点
    // 找到后继节点
    Node<E> s = successor(node);
    // 用后继节点的值覆盖度为2的节点的值
    node.element = s.element;
    // 删除后继节点
    node = s;
  }
  
  // 删除node节点（node的度必然是1或者0）
  Node<E> replacement = node.left != null ? node.left : node.right;
  
  if (replacement != null) { // node是度为1的节点
    // 更改parent
    replacement.parent = node.parent;
    // 更改parent的left、right的指向
    if (node.parent == null) { // node是度为1的节点并且是根节点
      root = replacement;
    } else if (node == node.parent.left) {
      node.parent.left = replacement;
    } else { // node == node.parent.right
      node.parent.right = replacement;
    }
  } else if (node.parent == null) { // node是叶子节点并且是根节点
    root = null;
  } else { // node是叶子节点，但不是根节点
    if (node == node.parent.left) {
      node.parent.left = null;
    } else { // node == node.parent.right
      node.parent.right = null;
    }
  }
}

// 根据值找对应节点
private Node<E> node(E element) {
  Node<E> node = root;
  while (node != null) {
    int cmp = compare(element, node.element);
    if (cmp == 0) return node;
    if (cmp > 0) {
      node = node.right;
    } else { // cmp < 0
      node = node.left;
    }
  }
  return null;
}

二、LeetCode

删除二叉搜索树中的节点：https://leetcode-cn.com/problems/delete-node-in-a-bst/
二叉搜索树中的搜索：https://leetcode-cn.com/problems/search-in-a-binary-search-tree/
二叉搜索树中的插入操作：https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/
验证二叉搜索树：https://leetcode-cn.com/problems/validate-binary-search-tree/comments/
二叉搜索树的最小绝对差：https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/comments/
二叉搜索树结点最小距离：https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/comments/
将有序数组转换为二叉搜索树：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
二叉搜索树的范围和：https://leetcode-cn.com/problems/range-sum-of-bst/
二叉搜索树的最近公共祖先：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
二叉搜索树中第K小的元素：https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/
二叉搜索树迭代器：https://leetcode-cn.com/problems/binary-search-tree-iterator/
恢复二叉搜索树：https://leetcode-cn.com/problems/recover-binary-search-tree/