二分搜索树节点删除学习笔记

概述

在二分搜索树中，我们可以通过比较节点中的值来进行查找、插入和删除操作。而节点删除操作是其中的一项关键操作，也是比较复杂的一种操作。

节点删除操作流程

删除一个二分搜索树中的节点，需要考虑该节点所在的位置以及其子节点的情况。删除一个节点后，需要将其子节点移动到正确的位置上，从而保持二分搜索树的性质。

具体步骤如下：

1. 查找要删除的节点
2. 删除节点并处理其子节点

对于第一步，我们可以使用递归或者循环的方式进行查找。如果找到了要删除的节点，就可以进入第二步操作。

对于第二步，我们需要对于要删除的节点进行分类处理：

• 如果要删除的节点没有子节点，直接删除该节点；
• 如果要删除的节点有一个子节点，将该子节点接到父节点的位置上；
• 如果要删除的节点有两个子节点，则找到其右子树的最小值节点来代替它，同时删除该最小值节点。

代码实现如下：

pythonCopy Code
class BST:
    # ...
    
    def remove(self, val):
        self.root = self._remove(self.root, val)
        
    def _remove(self, node, val):
        if not node:
            return None

        if val < node.val:
            node.left = self._remove(node.left, val)
        elif val > node.val:
            node.right = self._remove(node.right, val)
        else:
            # 没有子节点，或只有一个子节点
            if not node.left:
                return node.right
            if not node.right:
                return node.left

            # 有两个子节点，找到右子树的最小值节点
            temp = self._min(node.right)
            node.val = temp.val
            node.right = self._remove(node.right, temp.val)

        return node
        
    def _min(self, node):
        while node.left:
            node = node.left
        return node

实例演示

假设我们有以下二分搜索树：

Copy Code
     5
   /   \
  3     8
 / \   / \
1   4 7   9
         /
        6

我们来进行删除操作：

1. 删除节点 1：

Copy Code
     5
   /   \
  3     8
   \   / \
    4 7   9
         /
        6

2. 删除节点 8：

Copy Code
     5
   /   \
  3     9
 / \   / \
1   4 7   6

3. 删除节点 5：

Copy Code
     4
   /   \
  3     9
 /     / \
1     7   6

通过以上实例演示，可以看到我们成功地删除了二分搜索树中的节点，并保持了其性质。