美团技术文档-线程同步问题-二叉搜索树
在刷技术文档的时候，讲到线程同步问题，第一个示例是读写同步，这个很老生常谈，第二个问题是二叉搜索树，这里我就犯难了，这些树不树的除了写算法的当下会记得，平常没咋用过记不住，因此本篇刚好也是一个学习回顾，也是看完后的总结
二叉搜索树是什么
英文：Binary Search Tree，BST
1. 首先满足以下条件：
- 左子树上所有节点的值 < 根节点的值
- 右子树上所有节点的值 > 根节点的值
- 左右子树也符合BST的规则
- 不允许重复值，左小 右大等为什么需要二叉搜索树
1. 动态查找，插入自动有序
2. 时间复杂度平均，查询、插入、删除均为O(log n)
3. AVL、红黑树、B+树的基础逻辑如何实现
public class BinarySearchTree {
// ========== 节点定义 ==========
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
private TreeNode root;
// ========== 1. 查找 ==========
// 利用BST性质：比当前小去左子树，比当前大去右子树
public TreeNode search(int target) {
TreeNode curr = root;
while (curr != null) {
if (target == curr.val) return curr;
else if (target < curr.val) curr = curr.left;
else curr = curr.right;
}
return null; // 未找到
}
// ========== 2. 插入 ==========
public void insert(int val) {
root = insertRecursive(root, val);
}
private TreeNode insertRecursive(TreeNode node, int val) {
// 找到插入位置，创建新节点
if (node == null) return new TreeNode(val);
if (val < node.val)
node.left = insertRecursive(node.left, val);
else if (val > node.val)
node.right = insertRecursive(node.right, val);
// 相等则不插入（或根据需求处理）
return node;
}
// ========== 3. 删除（最复杂）：先查找到再删除 ==========
public void delete(int val) {
root = deleteRecursive(root, val);
}
private TreeNode deleteRecursive(TreeNode node, int val) {
if (node == null) return null;
// 先找到要删除的节点
if (val < node.val) {
node.left = deleteRecursive(node.left, val);
} else if (val > node.val) {
node.right = deleteRecursive(node.right, val);
} else {
// 找到目标节点，分三种情况：
// 情况1：叶子节点（无孩子）
if (node.left == null && node.right == null) {
return null;
}
// 情况2：只有一个孩子
else if (node.left == null) {
return node.right;
} else if (node.right == null) {
return node.left;
}
// 情况3：有两个孩子
else {
// 找到右子树的最小值（或左子树的最大值）
int minVal = findMin(node.right);
node.val = minVal; // 替换值
node.right = deleteRecursive(node.right, minVal); // 删除那个最小节点
}
}
return node;
}
private int findMin(TreeNode node) {
while (node.left != null) node = node.left;
return node.val;
}
// ========== 4. 中序遍历（验证BST性质） ==========
public void inorder() {
inorderRecursive(root);
System.out.println();
}
private void inorderRecursive(TreeNode node) {
if (node == null) return;
inorderRecursive(node.left);
System.out.print(node.val + " ");
inorderRecursive(node.right);
}
// ========== 主函数测试 ==========
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
// 插入
int[] nums = {50, 30, 70, 20, 40, 60, 80};
for (int num : nums) bst.insert(num);
System.out.print("中序遍历: ");
bst.inorder(); // 输出: 20 30 40 50 60 70 80（有序！）
// 查找
System.out.println("查找40: " + (bst.search(40) != null ? "找到" : "未找到"));
// 删除叶子节点
bst.delete(20);
System.out.print("删除20后: "); bst.inorder();
// 删除有两个孩子的节点
bst.delete(50);
System.out.print("删除50后: "); bst.inorder();
}
}