【数据结构】99%的人都知道的超好用二叉搜索树

笔者近期学习了二叉搜索树，与其说是学习了此种数据结构，倒不如说是先在力扣上做了相关题目，而后觉得对其了解甚浅，于是再去找资料…今天就结合力扣题目，向大家介绍一下二叉搜索树。

我们先抛开树形结构不谈，来看看我们司空见惯的二分查找。

从折半查找说起（Binary Search）

当我们用有序数组保存数据时，采用折半查找，可以以O(logn)的效率高效地查找数据。

如下图所示，我们采用二分查找在数组中寻找一个值：

无论需要寻找的值在数组中哪一个位置，都可以用O(logn)的时间复杂度寻找到。

但数组毕竟有其局限性，当我们想要插入或删除某个元素时，就容易遇到一些问题。

例如，我们如果要删除8这个元素

首先我们要将8移出，而后将8后方所有元素都向前移动一位，时间复杂度达到了O(n)。

添加操作同理，需要在数组中添加某一元素，需要找到合适部位，而后将该元素右侧所有元素向右移动一位，再插入元素。

二叉搜索树（Binary Search Tree）

为了解决这一问题，二叉搜索树应运而生，在二叉搜索树中，我们可以实现添加、删除、查找的时间复杂度均为O(logn)，接下来我们看看二叉搜索树如何实现查找，删除，添加操作。

注：本篇博客中关于二叉树的图片均用如下网站进行制作。

Binary Search Tree Visualization (usfca.edu)

首先介绍一下二叉搜索树的特点：

所有的左子树都小于根，所有的右子树都大于根。

对于任何子树都是如此。

如果对二叉搜索树中序遍历（即左中右）一定是从小到大

如图所示，这是一棵二叉搜索树：

查找

原题链接：

700. 二叉搜索树中的搜索 - 力扣（LeetCode）

以图为例，我如果要在如下的树中寻找7这个值：

首先遍历根节点，发现比7小，故而遍历右子树

发现12比7大，故而遍历左子树

最后找到7这个节点

接下来阐述代码思路：

使用递归法写代码，又或者是写二叉树的代码，总离不开递归三部曲，这在接下来的代码阐释中也会体现。

递归三部曲：

首先确定递归函数返回值及其参数。

而后确定递归停止条件。

最后确定单层递归逻辑。

在本题中：

确定递归函数返回值及其参数：
- 返回值：TreeNode，表示找到的节点或者是null（如果未找到）。
- 参数：root（当前遍历的BST节点），val（要查找的值）。
确定递归停止条件：
- 代码中的停止条件是 root == null || root.val == val。如果当前节点为null（即没有更多的节点可以遍历），或者当前节点的值等于要查找的值，递归将停止。
确定单层递归逻辑：
- 单层递归逻辑是：如果当前节点的值小于要查找的值val，则递归地在右子树上进行查找；否则，在左子树上进行查找。这是BST的性质，左子树上的所有值都小于根节点的值，右子树上的所有值都大于或等于根节点的值。

AC代码如下：

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if(root == null || root.val == val) return root;
        TreeNode result = new TreeNode();
        if(root.val < val){
            result = searchBST(root.right,val);
        }else{
            result = searchBST(root.left,val);
        }
        return result;
    }
}

删除

原题链接：

450. 删除二叉搜索树中的节点 - 力扣（LeetCode）

同样地，首先上图：

同样的二叉树，假设我要删除32这个节点

首先用同样的方式找到32节点所在位置，删除即可。

但如果我们要删除12这个节点，情况就会有所不同：

同样地，首先找到12这个节点

而后将7移动到12原来的位置上，再将32连接至7上。

事实上，我们要分五种情况考虑删除问题。

没找到需要删除的节点
叶子结点左右都为空
左不空右空
左空右不空
左不空右不空

依旧套用递归三部曲的模板。

确定递归函数返回值及其参数：
- 返回值：TreeNode，表示删除节点后的树的根节点。
- 参数：root（当前遍历的树节点），key（要删除的节点的值）。
确定递归停止条件：
- 递归的停止条件是当root为null时，即未找到需要删除的节点。在这种情况下，函数将返回null，表示不需要做任何改变。
- 如果找到需要删除的节点root.val == key，则根据该节点的子节点情况来决定如何处理：
  - 如果节点是叶子节点（没有子节点或者只有一个子节点），可以直接返回其子节点（如果有的话），或者返回null（如果没有子节点）。
  - 如果节点有两个子节点，找到该节点右子树中最左侧的节点（即右子树的最小值节点），将其值复制到当前节点，然后删除那个最小值节点。这样做的原因是二叉搜索树的性质，即任何节点的左子树都小于该节点，右子树都大于该节点。
确定单层递归逻辑：
- 如果当前节点的值大于要删除的key，在左子树中查找并删除节点。
- 如果当前节点的值小于要删除的key，在右子树中查找并删除节点。

AC代码如下：

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        //如果没找到需要删除的节点
        if (root == null) return root;
        if (root.val == key) { 
            //叶子节点左右都为空 || 左空右不空
            if (root.left == null) {
                return root.right;
            //左不空右空
            }else if(root.right == null) {
                return root.left;
            //左右都不为空
            }else{
                //找到当前节点右子树中最左侧的值
                TreeNode cur = root.right;
                while (cur.left != null) {
                    cur = cur.left;
                }
                cur.left = root.left;
                root = root.right;
                return root;
            }
        }
        if (root.val > key) root.left = deleteNode(root.left, key);
        if (root.val < key) root.right = deleteNode(root.right, key);
        return root;
    }
}

添加

原题链接：

701. 二叉搜索树中的插入操作 - 力扣（LeetCode）

不说废话，上图：

同样的树，假设我要插入一个10

首先新建了一个10的节点，而后按照二叉搜索树的遍历顺序依次比较。

最终找到合适的位置并插入。

确定递归函数返回值及其参数：
- 返回值：TreeNode，表示插入新节点后的BST的根节点。
- 参数：root（当前遍历的BST节点），val（要插入的新节点的值）。
确定递归停止条件：
- 递归的停止条件是当root为null时，即到达了BST的末端，需要在此处插入新节点。
确定单层递归逻辑：
- 如果新节点的值val大于当前节点的值root.val，则递归地在右子树上插入新节点。
- 如果新节点的值val小于当前节点的值root.val，则递归地在左子树上插入新节点。
- 在递归调用返回后，当前节点的左或右子节点将会指向新插入的节点。

AC代码及题解如下：

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        TreeNode node = new TreeNode(val);
        if(root == null) root = node;
        //搜索到合适位置
        if(root.val < val){
            root.right = insertIntoBST(root.right,val);
        }
        if(root.val > val){
            root.left = insertIntoBST(root.left,val);
        }
        return root;
    }
}

构造

原题链接：

108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）

本题不上图，直接上题解。

确定递归函数返回值及其参数：
- 返回值：TreeNode，表示平衡二叉搜索树的根节点。
- 参数：
  - nums：一个整数数组，表示排序后的序列。
  - left：当前递归调用处理的数组的左边界。
  - right：当前递归调用处理的数组的右边界。
确定递归停止条件：
- 递归的停止条件是left > right，这意味着当前子数组为空，没有元素可以构造成树的节点。
确定单层递归逻辑：
- 首先，计算子数组的中间索引mid，这是为了确保树的平衡。
- 接着，创建一个新的TreeNode对象，其值为nums[mid]，这个节点将成为当前递归调用构建的BST的根节点。
- 然后，递归地调用
```
traversal
```
  函数来构建左子树和右子树：
  - 左子树的节点由数组中从left到mid - 1的元素构成。
  - 右子树的节点由数组中从mid + 1到right的元素构成。

class Solution {
    //构造平衡二叉搜索树
	public TreeNode sortedArrayToBST(int[] nums) {
		TreeNode root = traversal(nums, 0, nums.length - 1);
		return root;
	}

	private TreeNode traversal(int[] nums, int left, int right) {
		if (left > right) return null;

		int mid = left + ((right - left) >> 1);
		TreeNode root = new TreeNode(nums[mid]);
		root.left = traversal(nums, left, mid - 1);
		root.right = traversal(nums, mid + 1, right);
		return root;
	}
}