复旦大学961-数据结构-第三章-查找（3）-BST树定义,性质,ADT及其实现,BST树查找,插入,删除算法

妖狐艹你老母 2022-12-11 15:10 119阅读 0赞

[961全部内容链接][961]

### 文章目录 ###

*  BST树定义
 *  BST的性质
 *   *  BST的时间复杂度
 *  BST的ADT及其实现
 *   *  BST的ADT
     *  BST的具体实现
     *   *  BST的插入
         *  BST的查找
         *  BST的查找最大最小值
         *  BST的删除操作
     *  完整代码如下

# BST树定义 #

BST（Binary Search Tree），又称**二叉排序树**，**二叉查找树**，**二叉搜索树**。其特点为：

1.  根节点的左子树的所有元素必须小于根节点。右子树上的元素必须大于根节点。
2.  从根节点下的所有子树也都要满足1。

例如，如图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70_pic_center]  
该树为一棵BST，将其**中序遍历**就是一个有序数列：1,3,4,5,6,8,10,13,14

# BST的性质 #

性质基本上就是定义中的那些。

## BST的时间复杂度 ##

1.  平均查找时间复杂度为O(log n)
2.  最坏的时间复杂度为O(n)，例如这样一棵树。![在这里插入图片描述][20201003140525142.png_pic_center]

# BST的ADT及其实现 #

ADT就是抽象数据类型

## BST的ADT ##

## BST的具体实现 ##

### BST的插入 ###

基本思想如下：

1.  从根节点开始递归，若当前节点为空，则生成新节点
2.  若x小于根节点，则插入到左子树
3.  若x大于根节点，则插入到右子树
4.  若x等于根节点，则什么都不做
5.  2,3,4步骤一致递归，直至递归到1

代码如下：

private BinaryNode insert(BinaryNode<AnyType> node, AnyType x) { 
        if (node == null) { 
            return new BinaryNode<>(x);  // 如果为空节点，则生成新节点
        }
    
        int result = node.element.compareTo(x);
        if (result > 0) node.left = insert(node.left, x);  // x小于根节点，则插入到左子树
        else if (result < 0) node.right = insert(node.right, x);  // x大于根节点，插入到右子树
        return node;  // 返回插入后的树的根节点
    }
    
    public void insert(AnyType x) { 
        root = insert(root, x);
    }

### BST的查找 ###

基本思想（与插入类似）：

1.  从根节点开始递归的查找，若为空，则查找失败
2.  若x小于根节点，则查找左子树
3.  若x大于根节点，则查找右子树
4.  若x等于根节点，则查找成功
5.  递归2,3,4，直到查找成功或查找失败

代码如下：

private boolean contains(BinaryNode<AnyType> node, AnyType x) { 
        if (node == null) return false; // 如果都空了还没找到，那么就是不存在
    
        int result = x.compareTo(node.element);
        if (result == 0) return true; // 查找成功
        else if (result > 0) return contains(node.right, x); // x在右子树中
        else return contains(node.left, x); // x在左子树中
    }
    
    public boolean contains(AnyType x) { 
        return contains(root, x);
    }

### BST的查找最大最小值 ###

基本思想：沿着根节点一致往左查找，最后一个左孩子就是树的最小值。最大值就是沿着根节点一致往右。

代码如下：

private BinaryNode<AnyType> findMin(BinaryNode node) { 
        if (node.left == null) return node;
        return findMin(node.left); // 递归查找左孩子
    }
    
    public AnyType findMin() { 
        if (root == null) return null;
        return findMin(root).element;
    }
    
    private BinaryNode<AnyType> findMax(BinaryNode node) { 
        while (node.right != null)
            node = node.right; // node的右孩子不为空，则一直往右
        return node;
    }
    
    public AnyType findMax() { 
        if (root == null) return null;
        return findMax(root).element;
    }

### BST的删除操作 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70_pic_center 1]

BST的删除比较复杂，分很多情况：

1.  要删除的节点是叶子节点，直接删除即可，如删除图中4这个节点
2.  要删除的节点既有左孩子也有右孩子，此时需要将该节点的值替换为该节点右子树的最小值，然后删除其右子树中的最小值。如删除图中的3节点，则需要将3替换为4，然后删除647这棵树子树上的4节点
3.  要删除的节点只有左子树或只有右子树，则直接让其父节点连接到它的左子树或右子树

private BinaryNode remove(AnyType x, BinaryNode<AnyType> node) { 
        if (node == null) return null;
    
        int result = x.compareTo(node.element);
        if (result > 0) { 
            // x在右子树中
            node.right = remove(x, node.right);
        } else if (result < 0) { 
            // x在左子树中
            node.left = remove(x, node.left);
        } else { 
            if (node.left == null && node.right == null) { 
                // 要删除的节点是叶节点，则直接删除，即返回空
                return null;
            } else if (node.left != null && node.right != null) { 
                // 要删除的节点左子树和右子树都不为空
                BinaryNode<AnyType> minNode = findMin(node.right);  // 获取右子树中的最小值
                node.element = minNode.element;  // 替换要删除节点的值为右子树中的最小值
                node.right = remove(minNode.element, node.right); // 删除右子树中的最小值
            } else if (node.left != null && node.right == null) { 
                // 要删除的节点的左孩子不为空，右节点为空，则返回左孩子
                return node.left;
            } else if (node.right != null && node.left == null) { 
                // 要删除的节点的右孩子不为空，左节点为空，则返回右孩子
                return node.right;
            }
        }
        return node;
    }
    
    public void remove(AnyType x) { 
        root = remove(x, root);
    }

代码中有很多地方的判断是没有必要的，可以简化很多，但为了思路清晰，所以加上了。我觉得考试应该不会因此扣分。

## 完整代码如下 ##

public class BinarySearchTree<AnyType extends Comparable<? super AnyType>> { 
    
        private static class BinaryNode<AnyType> { 
    
            AnyType element;
            BinaryNode<AnyType> left;
            BinaryNode<AnyType> right;
    
            public BinaryNode(AnyType theElement) { 
                this.element = theElement;
            }
    
            public BinaryNode(AnyType theElement, BinaryNode lt, BinaryNode rt) { 
                this.element = theElement;
                this.left = lt;
                this.right = rt;
            }
        }
    
        private BinaryNode<AnyType> root;
    
        public BinarySearchTree() { 
            root = null;
        }
    
        public void makeEmpty() { 
            root = null;
        }
    
        public boolean isEmpty() { 
            return root == null;
        }
    
        private boolean contains(BinaryNode<AnyType> node, AnyType x) { 
            if (node == null) return false; // 如果都空了还没找到，那么就是不存在
    
            int result = x.compareTo(node.element);
            if (result == 0) return true; // 查找成功
            else if (result > 0) return contains(node.right, x); // x在右子树中
            else return contains(node.left, x); // x在左子树中
        }
    
        public boolean contains(AnyType x) { 
            return contains(root, x);
        }
    
        private BinaryNode<AnyType> findMin(BinaryNode node) { 
            if (node.left == null) return node;
            return findMin(node.left); // 递归查找左孩子
        }
    
        public AnyType findMin() { 
            if (root == null) return null;
            return findMin(root).element;
        }
    
        private BinaryNode<AnyType> findMax(BinaryNode node) { 
            while (node.right != null)
                node = node.right; // node的右孩子不为空，则一直往右
            return node;
        }
    
        public AnyType findMax() { 
            if (root == null) return null;
            return findMax(root).element;
        }
    
        private BinaryNode insert(BinaryNode<AnyType> node, AnyType x) { 
            if (node == null) { 
                return new BinaryNode<>(x);  // 如果为空节点，则生成新节点
            }
    
            int result = node.element.compareTo(x);
            if (result > 0) node.left = insert(node.left, x);  // x小于根节点，则插入到左子树
            else if (result < 0) node.right = insert(node.right, x);  // x大于根节点，插入到右子树
            return node;  // 返回插入后的树的根节点
        }
    
        public void insert(AnyType x) { 
            root = insert(root, x);
        }
    
        private BinaryNode remove(AnyType x, BinaryNode<AnyType> node) { 
            if (node == null) return null;
    
            int result = x.compareTo(node.element);
            if (result > 0) { 
                // x在右子树中
                node.right = remove(x, node.right);
            } else if (result < 0) { 
                // x在左子树中
                node.left = remove(x, node.left);
            } else { 
                if (node.left == null && node.right == null) { 
                    // 要删除的节点是叶节点，则直接删除，即返回空
                    return null;
                } else if (node.left != null && node.right != null) { 
                    // 要删除的节点左子树和右子树都不为空
                    BinaryNode<AnyType> minNode = findMin(node.right);  // 获取右子树中的最小值
                    node.element = minNode.element;  // 替换要删除节点的值为右子树中的最小值
                    node.right = remove(minNode.element, node.right); // 删除右子树中的最小值
                } else if (node.left != null && node.right == null) { 
                    // 要删除的节点的左孩子不为空，右节点为空，则返回左孩子
                    return node.left;
                } else if (node.right != null && node.left == null) { 
                    // 要删除的节点的右孩子不为空，左节点为空，则返回右孩子
                    return node.right;
                }
            }
            return node;
        }
    
        public void remove(AnyType x) { 
            root = remove(x, root);
        }
    
        public void printTree() { 
        	// todo 这个大纲里没有，后期补充
        }
    }

[961]: https://blog.csdn.net/zhaohongfei_358/article/details/111414370
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/659862de518141808d7755a4eed1e5f6.png
[20201003140525142.png_pic_center]: /images/20221123/8c621367794d450b92b5c67122f989fd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/1a951b9c184b4f55860bd15f2f1c4bcd.png