二叉排序树：数据存储的艺术
原创
前言
- hello，大家好，我是 Lorin，今天给大家带来数据结构系列，二叉树中的一种特殊类型-二叉搜索树BST，又称二叉排序树或二叉查找树，比如我们我们常见的 AVL 树、B树、B+树都是BST的变种。
二叉搜索树（Binary Search Tree，BST）
定义
- 二叉搜索树，又称二叉排序树或二叉查找树，是一种常见的二叉树数据结构。它具有以下特点：
1、每个节点最多有两个子节点，分别为左子节点和右子节点。
2、左子节点的值小于或等于父节点的值。右子节点的值大于父节点的值。
3、对BST进行中序遍历，可以得到升序排列的节点值序列。时间复杂度
- 查找（Search）：O(log n) - 平均情况，最坏情况为O(n)，当BST退化成链表时。
- 插入（Insertion）：O(log n) - 平均情况，最坏情况为O(n)。
- 删除（Deletion）：O(log n) - 平均情况，最坏情况为O(n)。
空间复杂度
- 空间复杂度为O(n)，其中n是BST的节点数量，主要是用于存储树结构本身。
树操作
插入
从根节点开始，比较待插入的值与当前节点的值。
若待插入的值小于当前节点的值，移至左子树；否则，移至右子树。
重复以上步骤，直到找到一个为空的位置，将待插入的值放入此位置。查找
从根节点开始，比较待查找的值与当前节点的值。
若待查找的值等于当前节点的值，返回当前节点；若小于当前节点的值，移至左子树；否则，移至右子树。
重复以上步骤，直到找到目标值或者遇到空节点。删除
先查找到待删除节点。
如果节点没有子节点，直接删除；如果有一个子节点，用子节点替代待删除节点；
如果有两个子节点，用右子树中的最小值节点（或左子树的最大值节点）替代待删除节点，然后删除最小值节点（或最大值节点）。Java 版实现
元素：54,25,36,47,36,88,11,86,60
import java.util.ArrayList;
import java.util.Arrays;
class TreeNode {
Integer val;
TreeNode left, right;
public TreeNode(Integer val) {
this.val = val;
}
}
public class Test2 {
public static void main(String[] args) {
ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(54, 25, 36, 47, 36, 88, 11, 86, 60
));
// 构建BST
TreeNode root = null;
for (Integer val : arr) {
if (root == null) {
root = new TreeNode(val);
}
addNode(root, val);
}
// 54 25 11 36 47 88 86 60
dlr(root);
System.out.println();
ldr(root);
System.out.println();
System.out.println(searchNode(root, 1));
System.out.println(searchNode(root, 54));
System.out.println(searchNode(root, 33));
// del
assert root != null;
final int delVal = 54;
delNode(root, delVal, null);
dlr(root);
System.out.println();
ldr(root);
}
private static void del(TreeNode node, TreeNode preRoot) {
// 判断节点是否存在子节点 若不存在直接删除该节点
if (node.left == null && node.right == null) {
// 判断 node 是 preRoot 的左节点还是右节点
if (node.val > preRoot.val) {
preRoot.right = null;
} else {
preRoot.left = null;
}
} else if (node.left == null) {
preRoot.right = node.right;
} else if (node.right == null) {
preRoot.left = node.left;
} else {
// 使用左子树的最大节点代替待删除节点并删除最大节点
TreeNode maxNode;
if (node.left.right == null) {
maxNode = node;
preRoot.left = maxNode.left;
} else {
maxNode = getAndDelLeftTreeMax(node.left, node);
}
node.val = maxNode.val;
}
}
/**
* 获取最大左子树最大节点，并移除该节点
*
* @param node
* @param preRoot
* @return
*/
private static TreeNode getAndDelLeftTreeMax(TreeNode node, TreeNode preRoot) {
if (node.right == null) {
preRoot.right = node.left;
return node;
}
return getAndDelLeftTreeMax(node.right, node);
}
/**
* if not found ,return -1
* or return searchVal
*
* @param root
* @param searchVal
* @return
*/
private static Integer searchNode(TreeNode root, int searchVal) {
if (root == null) {
return -1;
}
if (root.val == searchVal) {
return root.val;
} else if (searchVal > root.val) {
return searchNode(root.right, searchVal);
} else {
return searchNode(root.left, searchVal);
}
}
/**
* 删除树中的节点值
*
* @param root
* @param val
* @param preNode
* @return
*/
private static boolean delNode(TreeNode root, int val, TreeNode preNode) {
if (root == null) {
return false;
}
if (root.val == val) {
del(root, preNode);
return true;
} else if (val > root.val) {
return delNode(root.right, val, root);
} else {
return delNode(root.left, val, root);
}
}
/**
* 添加节点
*
* @param node
* @param val
*/
private static void addNode(TreeNode node, Integer val) {
if (node.val.equals(val)) {
return;
}
if (node.val > val) {
if (node.left != null) {
addNode(node.left, val);
} else {
node.left = new TreeNode(val);
}
} else {
if (node.right != null) {
addNode(node.right, val);
} else {
node.right = new TreeNode(val);
}
}
}
/**
* 先根遍历
*
* @param root
*/
private static void dlr(TreeNode root) {
// 二叉树的先根遍历
if (root != null) {
System.out.print(root.val + " ");
dlr(root.left);
dlr(root.right);
}
}
/**
* 中根遍历
*
* @param root
*/
private static void ldr(TreeNode root) {
// 二叉树的先根遍历
if (root != null) {
ldr(root.left);
System.out.print(root.val + " ");
ldr(root.right);
}
}
}优缺点
优点
快速的查找操作
- BST的查找操作平均时间复杂度为O(log n)，使得它在大多数情况下非常高效。这是因为每次比较都能将搜索范围减半。
有序性
- BST中的数据以有序的方式存储，中序遍历BST可以输出有序的数据序列，这对某些应用非常有用，如范围查询。
支持插入和删除操作
- BST可以轻松支持插入和删除操作，并且在平均情况下，它们的时间复杂度也是O(log n)。
内存效率
- 相对于一些其他数据结构（如哈希表），BST通常具有更好的内存使用效率，因为它们只需要存储节点和指针，不需要提前分配大块的内存。
缺点
不平衡性
- BST在最坏情况下可能会退化成一个链表，导致查找、插入和删除操作的时间复杂度变为O(n)。为了解决这个问题，需要使用平衡二叉搜索树（如AVL树、红黑树）来确保树的平衡性。
对数据分布敏感
- BST的性能高度依赖于数据的分布。如果数据按照某种有序方式插入，树将会变得不平衡，从而影响性能。
删除操作复杂性
- BST中的删除操作相对复杂，因为它需要考虑多种情况，包括节点没有子节点、有一个子节点或有两个子节点。这可能需要额外的代码来处理。
使用场景
- 由于BST的不平衡性和对数据库分布敏感的原因，实际运用中并不会直接使用BST而是基于BST的变种平衡二叉搜索树（如AVL树、红黑树）或多叉树（如B树、B+树）等，运用于数据库索引、文件系统等场景。
个人简介
👋 你好，我是 Lorin 洛林，一位 Java 后端技术开发者！座右铭：Technology has the power to make the world a better place.
🚀 我对技术的热情是我不断学习和分享的动力。我的博客是一个关于Java生态系统、后端开发和最新技术趋势的地方。
🧠 作为一个 Java 后端技术爱好者，我不仅热衷于探索语言的新特性和技术的深度，还热衷于分享我的见解和最佳实践。我相信知识的分享和社区合作可以帮助我们共同成长。
💡 在我的博客上，你将找到关于Java核心概念、JVM 底层技术、常用框架如Spring和Mybatis 、MySQL等数据库管理、RabbitMQ、Rocketmq等消息中间件、性能优化等内容的深入文章。我也将分享一些编程技巧和解决问题的方法，以帮助你更好地掌握Java编程。
🌐 我鼓励互动和建立社区，因此请留下你的问题、建议或主题请求，让我知道你感兴趣的内容。此外，我将分享最新的互联网和技术资讯，以确保你与技术世界的最新发展保持联系。我期待与你一起在技术之路上前进，一起探讨技术世界的无限可能性。
📖 保持关注我的博客，让我们共同追求技术卓越。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
云数据库 MySQL
腾讯云数据库 MySQL（TencentDB for MySQL）为用户提供安全可靠，性能卓越、易于维护的企业级云数据库服务。其具备6大企业级特性，包括企业级定制内核、企业级高可用、企业级高可靠、企业级安全、企业级扩展以及企业级智能运维。通过使用腾讯云数据库 MySQL，可实现分钟级别的数据库部署、弹性扩展以及全自动化的运维管理，不仅经济实惠，而且稳定可靠，易于运维。
腾讯云开发者
