数据结构之二分搜索树 Binary Search Tree

二分搜索树（BST）是一种有序的二叉树，也是数据结构中最常用的树形结构之一，其核心特性是 “左小右大”，这使得它的查找、插入、删除操作的平均时间复杂度可达 \(O(\log n)\)（最坏为 \(O(n)\)，退化为链表），是高效的动态查找 / 排序数据结构。

一、定义

一棵二叉树满足以下条件，则称为二分搜索树：
对于任意节点 node：
其左子树中的所有节点值都 小于 node.val；
其右子树中的所有节点值都 大于 node.val；
左、右子树本身也必须是二分搜索树（递归定义）。
（可选）若需支持重复值，可约定：左子树 ≤ 当前节点 ≤ 右子树（本文默认无重复值）。

二、BST特性
1）中序遍历结果有序：对 BST 进行中序遍历（左→根→右），会得到一个升序排列的序列（核心特性，常用于验证 BST、排序、找前驱 / 后继节点）；
2）查找 / 插入 / 删除的高效性：每次操作可排除一半子树，类似二分查找；
3）无唯一形态：同一组数据可构造不同的 BST（如插入顺序不同），极端情况下会退化为单链表（如按升序插入 1,2,3,4,5）。

三、BST性能特征

四、应用场景
1）动态查找 / 排序：支持高效的插入、删除、查找，且中序遍历可直接得到有序序列；
2）集合 / 映射实现：如 Java TreeSet/TreeMap、C++ set/map（底层为红黑树，属于平衡 BST）；
3）范围查询：如找 “大于 x 且小于 y 的所有节点”，利用 BST 的有序性可快速定位边界；
4）前驱 / 后继节点查找：如在 BST 中找某个节点的前驱（比它小的最大值）、后继（比它大的最小值），用于排序、TopK 问题。

五、案例分享

题目1：给定一棵二分搜索树和两个结点，寻找这两个结点的最近公共祖先，如下图所示的二分搜索树，2和8的最近公共祖先为6，2和4的最近公共祖先为2。树形结构见下图。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (null == root) return null; // p and q are in the left side of the tree if (root.val > q.val && root.val > p.val) return lowestCommonAncestor(root.left, p, q); // p and q are in the right side of the tree if (root.val < q.val && root.val < p.val) return lowestCommonAncestor(root.right, p, q); // p and q are in the different sides of the tree，q or p may be is the root node. return root; }

题目2:给定一棵二叉树，验证其是否为二分搜索树。

思路1：根据题目的要求，结点的值大于其左孩子结点的值，而小于其右孩子结点的值，则中序遍历该二叉搜索树时，会返回一个有序的列表。但是若是left.val<=root.val<right.val，这种方式就不行了，此种方式效率较低。

import java.util.LinkedList; import java.util.List; public class LC98 { // 根据题意，中序遍历二叉树，看看是否升序排列 public boolean isValidBST(TreeNode root) { if (null == root) return true; // 此时root肯定不为空 List<Integer> nodeValueList = new LinkedList<>(); inOrder(root, nodeValueList); for(int i = 0;i < nodeValueList.size() - 1;++i) { if(nodeValueList.get(i+1) <= nodeValueList.get(i)) return false; } return true; } private void inOrder(TreeNode root, List<Integer> nodeValueList) { if(null == root) return; inOrder(root.left, nodeValueList); nodeValueList.add(root.val); inOrder(root.right, nodeValueList); } public static void main(String[] args) { TreeNode root = new TreeNode(2); root.left = new TreeNode(1); root.right = new TreeNode(3); System.out.println("result=" + new LC98().isValidBST(root)); } }

思路2：直接使用二分搜索树的性质，左<root<右

public class LC98 { // 根据题意，使用其性质直接判断 左<root<右 public boolean isValidBST(TreeNode root) { if (root == null) return true; return valid(root, Long.MIN_VALUE, Long.MAX_VALUE); } public boolean valid(TreeNode root, long leftValue, long rightValue) { if (root == null) return true; if (root.val <= leftValue || root.val >= rightValue) return false; return valid(root.left, leftValue, root.val) && valid(root.right, root.val, rightValue); } public static void main(String[] args) { TreeNode root = new TreeNode(10); root.left = new TreeNode(5); root.right = new TreeNode(15); root.right.left = new TreeNode(6); root.right.right = new TreeNode(20); System.out.println("result=" + new LC98().isValidBST(root)); } }