如何实现二叉搜索树的插入和删除操作？

二叉搜索树(Binary Search Tree)是一个二叉树,其中左子树中的节点值小于根节点值,右子树中的节点值大于根节点值。

我们可以实现二叉搜索树的插入和删除操作如下:

public class BST {
    public void insert(int val) {
        root = insert(root, val);
    }

    private TreeNode insert(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        if (val < root.val) root.left = insert(root.left, val);
        else root.right = insert(root.right, val);
        return root;
    }

    public void delete(int val) {
        root = delete(root, val);
    }

    private TreeNode delete(TreeNode root, int val) {
        if (root == null) return null;
        if (val < root.val) root.left = delete(root.left, val);
        else if (val > root.val) root.right = delete(root.right, val);
        else {
            // 节点只有一个子节点或无子节点
            if (root.left == null) return root.right;
            if (root.right == null) return root.left;

            // 节点有两个子节点,找右子树的最小节点代替
            TreeNode minNode = findMin(root.right);
            root.val = minNode.val;
            root.right = delete(root.right, minNode.val);
        }
        return root;
    }

    private TreeNode findMin(TreeNode root) {
        if (root.left == null) return root;
        return findMin(root.left);
    }
}

算法流程:

1. insert():递归插入,当root为空时创建新节点,否则比较大小插入左子树或右子树。
2. delete():递归删除,当节点只有一个子节点或无子节点时直接返回子节点或null。当有两个子节点时,找到右子树最小节点代替当前节点,再删除最小节点。
3. findMin():辅助方法,用于找到右子树最小节点。
4. 重复以上过程,构建二叉搜索树。

时间复杂度O(n),空间复杂度O(1)。

所以,二叉搜索树的插入和删除的关键是:

1. insert():递归插入,比较大小插入左子树或右子树,当root为空时创建新节点。
2. delete():递归删除,情况1:节点只有一个子节点或无子节点,直接返回子节点或null。情况2:有两个子节点,找到右子树最小节点代替当前节点,再删除最小节点。
3. 找到右子树最小节点用findMin()辅助方法。
4. 重复以上过程,构建二叉搜索树。