二叉搜索树（BST）详解及代码实现

推荐可视化插入、删除节点的二叉树网站：Binary Search Tree Visualization (usfca.edu)

1. 概述

二叉搜索树（Binary Search Tree，简称BST）是一种特殊的二叉树结构，它具有以下特点：

有序性：对于BST中的每个节点，其左子树中的所有节点的值都小于该节点的值，而右子树中的所有节点的值都大于该节点的值。
递归性：BST的每个子树也是BST，即子树中的节点仍然满足有序性和递归性。
无重复值：BST中不允许存在相同值的节点。

由于BST的有序性，它具有快速的查找、插入和删除操作的特点，因此被广泛应用于数据结构和算法中。

2. BST的查找操作

当需要查找某个值时，从根节点开始，比较要查找的值与当前节点的值的大小关系。
若相等，则找到目标节点；
若小于当前节点的值，则在左子树中继续查找；
若大于当前节点的值，则在右子树中继续查找。
如果找到叶子节点仍然没有找到目标值，则说明目标值不存在于BST中。

3. BST的插入操作

从根节点开始，比较要插入的值与当前节点的值的大小关系。
若小于当前节点的值，则在左子树中继续插入；
若大于当前节点的值，则在右子树中继续插入。
直到找到一个空位置，将新节点插入其中。

4. BST的删除操作

BST（二叉搜索树）的删除操作涉及到以下几种情况：

删除叶子节点：如果要删除的节点是叶子节点（没有子节点），直接将其删除即可。

删除节点有一个子节点：如果要删除的节点只有一个子节点，将子节点替代要删除的节点的位置即可。

删除节点有两个子节点：如果要删除的节点有两个子节点，可以采用以下两种方法之一来替代删除节点：

找到删除节点的右子树中的最小节点，将最小节点的值复制到删除节点，然后删除最小节点。
找到删除节点的左子树中的最大节点，将最大节点的值复制到删除节点，然后删除最大节点。

如删除下面这个BST的节点5，会把节点 4 的值复制到节点4上，然后删除原来的节点4：

5. 性能

在普通的二叉搜索树（Binary Search Tree，BST）中，各种操作的平均时间复杂度取决于树的平衡性。各种操作的平均时间复杂度： O(log n)

需要注意的是，这里的时间复杂度是基于平衡的二叉搜索树的情况。如果树不平衡，例如出现倾斜树（所有节点都集中在一条路径上），则各种操作的时间复杂度可能退化为 O(n)，其中 n 是树中节点的数量。

下图描述了BST退化成线性表：

因此，为了确保较好的性能，可以使用自平衡的二叉搜索树（如AVL树、红黑树）或其他平衡树的变种来保持树的平衡性，从而保证各种操作的时间复杂度在对数级别。

6. 代码实现

（1）树节点

public class TreeNode {int val;TreeNode left;TreeNode right;public TreeNode(int val) {this.val = val;this.left = null;this.right = null;}
}

（2）BST

public class BST {private TreeNode root;public BST() {root = null;}//插入操作public void insert(int val) {root = insertNode(root, val);}private TreeNode insertNode(TreeNode root, int val) {if (root == null) {root = new TreeNode(val);return root;}if (val < root.val) {root.left = insertNode(root.left, val);} else if (val > root.val) {root.right = insertNode(root.right,val);}return root;}// 查找操作public boolean search(int val) {return searchNode(root, val);}private boolean searchNode(TreeNode root, int val) {if (root == null) {return false;}if (val == root.val) {return true;} else if (val < root.val) {return searchNode(root.left, val);} else {return searchNode(root.right, val);}}// 删除操作public void delete(int val) {root = deleteNode(root, val);}private TreeNode deleteNode(TreeNode root, int val) {if (root == null) {return null;}if (val < root.val) {root.left = deleteNode(root.left, val);} else if (val > root.val) {root.right = deleteNode(root.right, val);} else {// 找到要删除的节点if (root.left == null) {return root.right;} else if (root.right == null) {return root.left;}// 如果要删除的节点有两个子节点// 找到右子树中的最小节点，将其值赋给要删除的节点// 然后在右子树中删除最小节点TreeNode minNode = findMin(root.right);root.val = minNode.val;root.right = deleteNode(root.right, minNode.val);}return root;}private TreeNode findMin(TreeNode node) {while (node.left != null) {node = node.left;}return node;}
}

insert 方法用于插入节点。它通过调用 insertNode 方法实现。在 insertNode 方法中，首先判断根节点是否为空，如果为空则直接创建一个新节点作为根节点。如果根节点不为空，则比较要插入的值与当前节点的值的大小关系，如果小于当前节点的值，则递归地插入到左子树中，如果大于当前节点的值，则递归地插入到右子树中。
search 方法用于查找节点。它通过调用 searchNode 方法实现。在 searchNode 方法中，首先判断当前节点是否为空，如果为空则说明没有找到目标值，返回 false。如果当前节点的值等于目标值，则说明找到了，返回 true。如果目标值小于当前节点的值，则递归地在左子树中查找。如果目标值大于当前节点的值，则递归地在右子树中查找。
delete 方法用于删除节点。它通过调用 deleteNode 方法实现。在 deleteNode 方法中，首先判断当前节点是否为空，如果为空则直接返回 null。如果目标值小于当前节点的值，则递归地在左子树中删除。如果目标值大于当前节点的值，则递归地在右子树中删除。如果目标值等于当前节点的值，则分三种情况处理删除操作：如果要删除的节点没有子节点，则直接将其置为 null；如果要删除的节点只有一个子节点，则将其子节点替换为要删除的节点；如果要删除的节点有两个子节点，则找到右子树中的最小节点，将其值赋给要删除的节点，并在右子树中递归地删除最小节点。
另外还定义了一个辅助方法 findMin，用于找到给定节点下的最小节点，即最左子节点。