大厂AI必备数据结构与算法——基础算法之二叉搜索树（十一）详细文档
冲冲冲！开干
神马！神马！神马，一向让我们学习起来抓耳挠腮的数据结构课程竟然也有教程？还那么详细？？真的假的？
那么好，胡广告诉你是假的，哈哈哈哈哈哈哈哈哈！笑死了！！！
为神马我要说是假的呢，兄弟们，咱们要认真的听了：没有详细的教程，只有够细的人！
这篇文章为黑马程序员的课件，由于本人已经看过了自己学习了一遍，所以推荐给大家，讲的确实不错，准备考试或者准备冲击大厂的小伙伴完全可以将胡广的这一整个专栏当做学习资料。你边学习边思考，思维进行发散，形成自己的知识体系，这个是最好滴！
咱们废话少说？不存在滴
我还得给大家讲个故事（绝对不是AI生成的，凭借我智勇双全、足智多谋、十全十美、天下无敌、举世无双、天外飞仙的大脑想出来的）：
在一个不远的未来，人类科技取得了前所未有的突破，诞生了一种名为“思维引擎”的AI生命体。这种AI不仅拥有超强的计算能力，还能自主学习、推理、创造。为了应对未来复杂的任务，科学家们决定训练它掌握最核心的能力——数据结构与算法。
这个AI名叫“阿尔法”。阿尔法每天与代码为伴，但它不像普通AI那样机械执行指令，它有情感、有思维，能够通过不断实践来优化自己的算法。阿尔法的学习从最基本的数据结构开始，链表、栈、队列、二叉树，它逐渐理解了这些数据结构背后深层的逻辑。它明白，数据结构就像人体的骨架，算法则是其中的灵魂，二者缺一不可。
有一天，阿尔法遇到了前所未有的挑战——一个复杂的路径规划问题。整个世界仿佛迷失在无数的数据节点和分支之间。传统的算法无法高效解决这个问题，甚至连人类最顶尖的程序员也束手无策。阿尔法不断回溯过往的经验，尝试各种算法组合，但都未能找到最优解。
正当它快要陷入“无解”的泥沼时，阿尔法突然灵光一现：如果将二叉树与动态规划结合，并利用贪心算法进行优化，是不是可以突破眼前的困境？它迅速编码、测试，并不断自我迭代，终于找到了一条近乎完美的解决方案。这一次，阿尔法不再是冷冰冰的计算机器，它通过学习和创新，突破了数据结构与算法的极限，成功解开了谜题。
这不仅是一次算法上的胜利，更是阿尔法**“进化”的关键节点**。它感受到了**“思维”的力量**，并且意识到：数据结构与算法不仅是编程的基础，更是塑造智能生命的核心。如果能够掌握它们，就能真正成为世界的掌控者。
故事的结尾，阿尔法不再仅仅是一个工具，而是以独特的智慧和创造力，走向了与人类并肩共存的未来。这个故事也告诉我们，数据结构与算法不仅是敲代码的技巧，而是开启无限可能的钥匙。
这个故事好看吧？好看就赶快学！！！不好看也快学，不然没饭吃！！！
视频资源：文章内容参考了黑马程序员的数据结构与算法视频，想深入了解的小伙伴们可以点击下方链接观看：
加油吧，未来的高手！！！
加油吧，未来的高手！！！
加油吧，未来的高手！！！
三. 基础算法
3.1 查找概述
查找算法是一种在数据集中寻找特定数据项的方法。通常，数据集是在计算机程序中存储的，例如数组、链表或散列表。在编写程序时，查找算法是非常重要的，它有助于快速找到所需的数据。在本文中，我们将介绍一些基本的查找算法及其特点。
线性查找
线性查找也称为顺序查找，是一种最简单的查找算法。在这种算法中，我们从数据集的开头开始，逐个比较每个数据项，以寻找要查找的数据。如果我们找到了目标数据，查找过程就结束了。如果我们到达数据集的末尾，仍然找不到目标数据，则可以认为它不存在于数据集中。
线性查找的时间复杂度是O(n)，其中n是数据集的大小。因此，它在大型数据集中可能会很慢。然而，在小型数据集中，它仍然是一种非常有用的算法。
二分查找
二分查找也称为折半查找，是一种更快速的查找算法。但前提是，数据集必须已经排序。在二分查找中，我们取数据集的中间值，然后将目标与中间值进行比较。如果目标小于中间值，则在左侧子集中继续查找；如果目标大于中间值，则在右侧子集中继续查找。每次比较都会缩小要搜索的数据集的大小。
二分查找的时间复杂度是O(log n)，其中n是数据集的大小。这种算法在大型数据集中非常有效，但在小型数据集中可能并不是最快的选择。
哈希表查找
哈希表查找也称为散列表查找，是另一种常见的查找算法。它利用哈希函数将数据项映射到散列表中的位置。在查找过程中，我们只需通过哈希函数计算目标数据的位置，然后检查该位置是否包含目标数据。
哈希表查找的时间复杂度是O(1)。这使得它成为大型数据集中最快的查找算法之一。但是，哈希表查找的效率取决于哈希函数的质量。如果两个数据项映射到相同的位置，就会发生哈希冲突，这可能会导致性能下降。
小结
在编写程序时，我们需要选择适合数据集大小和其他要求的最佳查找算法。例如，如果数据集很小，则线性查找可能是最快的选择；如果数据集已经排序，则二分查找是非常有用的。然而，在大型数据集中，哈希表查找通常是最好的选择。了解不同类型的查找算法及其特点可以帮助我们在编写程序时做出明智的选择。
不管是之前学过的数组、链表、队列、还是栈，这些线性结构中，如果想在其中查找一个元素，效率是比较慢的，只有O(N)O(N)，因此如果你的需求是实现数据的快速查找，那么就需要新的数据结构支持。
还记得最先介绍的那个二分查找算法吗？它的查找效率能够达到 O(logN)O(logN)，是不是还不错？不过呢，它需要对数组事先排好序，而排序的成本是比较高的。那么有没有一个折中的办法呢？有，那就是接下来要给大家介绍的二叉搜索树，它插入元素后，自然就是排好序的，接下来的查询也自然而然可以应用二分查找算法进行高效搜索。
3.2 二叉搜索树
概述
历史
二叉搜索树最早是由Bernoulli兄弟在18世纪中提出的，但是真正推广和应用该数据结构的是1960年代的D.L. Gries。他的著作《The Science of Programming》中详细介绍了二叉搜索树的实现和应用。
在计算机科学的发展中，二叉搜索树成为了一种非常基础的数据结构，被广泛应用在各种领域，包括搜索、排序、数据库索引等。随着计算机算力的提升和对数据结构的深入研究，二叉搜索树也不断被优化和扩展，例如AVL树、红黑树等。
特性
二叉搜索树（也称二叉排序树）是符合下面特征的二叉树：
- 树节点增加 key 属性，用来比较谁大谁小，key 不可以重复
- 对于任意一个树节点，它的 key 比左子树的 key 都大，同时也比右子树的 key 都小，例如下图所示
轻易看出要查找 7 （从根开始）自然就可应用二分查找算法，只需三次比较
- 与 4 比，较之大，向右找
- 与 6 比，较之大，继续向右找
- 与 7 比，找到
查找的时间复杂度与树高相关，插入、删除也是如此。
- 如果这棵树长得还不赖（左右平衡）上图，那么时间复杂度均是 O(logN)O(logN)
- 当然，这棵树如果长得丑（左右高度相差过大）下图，那么这时是最糟的情况，时间复杂度是 O(N)O(N)
注：
- 二叉搜索树 - 英文 binary search tree，简称 BST
- 二叉排序树 - 英文 binary ordered tree 或 binary sorted tree
实现
定义节点
static class BSTNode {
int key; // 若希望任意类型作为 key, 则后续可以将其设计为 Comparable 接口
Object value;
BSTNode left;
BSTNode right;
public BSTNode(int key) {
this.key = key;
this.value = key;
}
public BSTNode(int key, Object value) {
this.key = key;
this.value = value;
}
public BSTNode(int key, Object value, BSTNode left, BSTNode right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
查询
递归实现
public Object get(int key) {
return doGet(root, key);
}
private Object doGet(BSTNode node, int key) {
if (node == null) {
return null; // 没找到
}
if (key < node.key) {
return doGet(node.left, key); // 向左找
} else if (node.key < key) {
return doGet(node.right, key); // 向右找
} else {
return node.value; // 找到了
}
}
非递归实现
public Object get(int key) {
BSTNode node = root;
while (node != null) {
if (key < node.key) {
node = node.left;
} else if (node.key < key) {
node = node.right;
} else {
return node.value;
}
}
return null;
}
Comparable
如果希望让除 int 外更多的类型能够作为 key，一种方式是 key 必须实现 Comparable 接口。
public class BSTTree2<T extends Comparable<T>> {
static class BSTNode<T> {
T key; // 若希望任意类型作为 key, 则后续可以将其设计为 Comparable 接口
Object value;
BSTNode<T> left;
BSTNode<T> right;
public BSTNode(T key) {
this.key = key;
this.value = key;
}
public BSTNode(T key, Object value) {
this.key = key;
this.value = value;
}
public BSTNode(T key, Object value, BSTNode<T> left, BSTNode<T> right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
BSTNode<T> root;
public Object get(T key) {
return doGet(root, key);
}
private Object doGet(BSTNode<T> node, T key) {
if (node == null) {
return null;
}
int result = node.key.compareTo(key);
if (result > 0) {
return doGet(node.left, key);
} else if (result < 0) {
return doGet(node.right, key);
} else {
return node.value;
}
}
}
还有一种做法不要求 key 实现 Comparable 接口，而是在构造 Tree 时把比较规则作为 Comparator 传入，将来比较 key 大小时都调用此 Comparator 进行比较，这种做法可以参考 Java 中的 java.util.TreeMap
最小
递归实现
public Object min() {
return doMin(root);
}
public Object doMin(BSTNode node) {
if (node == null) {
return null;
}
// 左边已走到头
if (node.left == null) {
return node.value;
}
return doMin(node.left);
}
非递归实现
public Object min() {
if (root == null) {
return null;
}
BSTNode p = root;
// 左边未走到头
while (p.left != null) {
p = p.left;
}
return p.value;
}
最大
递归实现
public Object max() {
return doMax(root);
}
public Object doMax(BSTNode node) {
if (node == null) {
return null;
}
// 右边已走到头
if (node.left == null) {
return node.value;
}
return doMin(node.right);
}
非递归实现
public Object max() {
if (root == null) {
return null;
}
BSTNode p = root;
// 右边未走到头
while (p.right != null) {
p = p.right;
}
return p.value;
}
新增
递归实现
public void put(int key, Object value) {
root = doPut(root, key, value);
}
private BSTNode doPut(BSTNode node, int key, Object value) {
if (node == null) {
return new BSTNode(key, value);
}
if (key < node.key) {
node.left = doPut(node.left, key, value);
} else if (node.key < key) {
node.right = doPut(node.right, key, value);
} else {
node.value = value;
}
return node;
}
- 若找到 key，走 else 更新找到节点的值
- 若没找到 key，走第一个 if，创建并返回新节点
- 返回的新节点，作为上次递归时 node 的左孩子或右孩子
- 缺点是，会有很多不必要的赋值操作
非递归实现
public void put(int key, Object value) {
BSTNode node = root;
BSTNode parent = null;
while (node != null) {
parent = node;
if (key < node.key) {
node = node.left;
} else if (node.key < key) {
node = node.right;
} else {
// 1. key 存在则更新
node.value = value;
return;
}
}
// 2. key 不存在则新增
if (parent == null) {
root = new BSTNode(key, value);
} else if (key < parent.key) {
parent.left = new BSTNode(key, value);
} else {
parent.right = new BSTNode(key, value);
}
}
前驱后继
一个节点的前驱（前任）节点是指比它小的节点中，最大的那个
一个节点的后继（后任）节点是指比它大的节点中，最小的那个
例如上图中
- 1 没有前驱，后继是 2
- 2 前驱是 1，后继是 3
- 3 前驱是 2，后继是 4
- …
简单的办法是中序遍历，即可获得排序结果，此时很容易找到前驱后继
要效率更高，需要研究一下规律，找前驱分成 2 种情况：
- 节点有左子树，此时前驱节点就是左子树的最大值，图中属于这种情况的有
- 2 的前驱是1
- 4 的前驱是 3
- 6 的前驱是 5
- 7 的前驱是 6
- 节点没有左子树，若离它最近的祖先自从左而来，此祖先即为前驱，如
- 3 的祖先 2 自左而来，前驱 2
- 5 的祖先 4 自左而来，前驱 4
- 8 的祖先 7 自左而来，前驱 7
- 1 没有这样的祖先，前驱 null
找后继也分成 2 种情况
- 节点有右子树，此时后继节点即为右子树的最小值，如
- 2 的后继 3
- 3 的后继 4
- 5 的后继 6
- 7 的后继 8
- 节点没有右子树，若离它最近的祖先自从右而来，此祖先即为后继，如
- 1 的祖先 2 自右而来，后继 2
- 4 的祖先 5 自右而来，后继 5
- 6 的祖先 7 自右而来，后继 7
- 8 没有这样的祖先，后继 null
public Object predecessor(int key) {
BSTNode ancestorFromLeft = null;
BSTNode p = root;
while (p != null) {
if (key < p.key) {
p = p.left;
} else if (p.key < key) {
ancestorFromLeft = p;
p = p.right;
} else {
break;
}
}
if (p == null) {
return null;
}
// 情况1 - 有左孩子
if (p.left != null) {
return max(p.left);
}
// 情况2 - 有祖先自左而来
return ancestorFromLeft != null ? ancestorFromLeft.value : null;
}
public Object successor(int key) {
BSTNode ancestorFromRight = null;
BSTNode p = root;
while (p != null) {
if (key < p.key) {
ancestorFromRight = p;
p = p.left;
} else if (p.key < key) {
p = p.right;
} else {
break;
}
}
if (p == null) {
return null;
}
// 情况1 - 有右孩子
if (p.right != null) {
return min(p.right);
}
// 情况2 - 有祖先自右而来
return ancestorFromRight != null ? ancestorFromRight.value : null;
}
删除
要删除某节点（称为 D），必须先找到被删除节点的父节点，这里称为 Parent
- 删除节点没有左孩子，将右孩子托孤给 Parent
- 删除节点没有右孩子，将左孩子托孤给 Parent
- 删除节点左右孩子都没有，已经被涵盖在情况1、情况2 当中，把 null 托孤给 Parent
- 删除节点左右孩子都有，可以将它的后继节点（称为 S）托孤给 Parent，设 S 的父亲为 SP，又分两种情况
- SP 就是被删除节点，此时 D 与 S 紧邻，只需将 S 托孤给 Parent
- SP 不是被删除节点，此时 D 与 S 不相邻，此时需要将 S 的后代托孤给 SP，再将 S 托孤给 Parent
非递归实现
/**
* <h3>根据关键字删除</h3>
*
* @param key 关键字
* @return 被删除关键字对应值
*/
public Object delete(int key) {
BSTNode p = root;
BSTNode parent = null;
while (p != null) {
if (key < p.key) {
parent = p;
p = p.left;
} else if (p.key < key) {
parent = p;
p = p.right;
} else {
break;
}
}
if (p == null) {
return null;
}
// 删除操作
if (p.left == null) {
shift(parent, p, p.right); // 情况1
} else if (p.right == null) {
shift(parent, p, p.left); // 情况2
} else {
// 情况4
// 4.1 被删除节点找后继
BSTNode s = p.right;
BSTNode sParent = p; // 后继父亲
while (s.left != null) {
sParent = s;
s = s.left;
}
// 4.2 删除和后继不相邻, 处理后继的后事
if (sParent != p) {
shift(sParent, s, s.right); // 不可能有左孩子
s.right = p.right;
}
// 4.3 后继取代被删除节点
shift(parent, p, s);
s.left = p.left;
}
return p.value;
}
/**
* 托孤方法
*
* @param parent 被删除节点的父亲
* @param deleted 被删除节点
* @param child 被顶上去的节点
*/
// 只考虑让 n1父亲的左或右孩子指向 n2, n1自己的左或右孩子并未在方法内改变
private void shift(BSTNode parent, BSTNode deleted, BSTNode child) {
if (parent == null) {
root = child;
} else if (deleted == parent.left) {
parent.left = child;
} else {
parent.right = child;
}
}
递归实现
public Object delete(int key) {
ArrayList<Object> result = new ArrayList<>();
root = doDelete(root, key, result);
return result.isEmpty() ? null : result.get(0);
}
public BSTNode doDelete(BSTNode node, int key, ArrayList<Object> result) {
if (node == null) {
return null;
}
if (key < node.key) {
node.left = doDelete(node.left, key, result);
return node;
}
if (node.key < key) {
node.right = doDelete(node.right, key, result);
return node;
}
result.add(node.value);
if (node.left != null && node.right != null) {
BSTNode s = node.right;
while (s.left != null) {
s = s.left;
}
s.right = doDelete(node.right, s.key, new ArrayList<>());
s.left = node.left;
return s;
}
return node.left != null ? node.left : node.right;
}
说明
ArrayList<Object> result用来保存被删除节点的值- 第二、第三个 if 对应没找到的情况，继续递归查找和删除，注意后续的 doDelete 返回值代表删剩下的，因此需要更新
- 最后一个 return 对应删除节点只有一个孩子的情况，返回那个不为空的孩子，待删节点自己因没有返回而被删除
- 第四个 if 对应删除节点有两个孩子的情况，此时需要找到后继节点，并在待删除节点的右子树中删掉后继节点，最后用后继节点替代掉待删除节点返回，别忘了改变后继节点的左右指针
找小的
public List<Object> less(int key) {
ArrayList<Object> result = new ArrayList<>();
BSTNode p = root;
LinkedList<BSTNode> stack = new LinkedList<>();
while (p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
} else {
BSTNode pop = stack.pop();
if (pop.key < key) {
result.add(pop.value);
} else {
break;
}
p = pop.right;
}
}
return result;
}
找大的
public List<Object> greater(int key) {
ArrayList<Object> result = new ArrayList<>();
BSTNode p = root;
LinkedList<BSTNode> stack = new LinkedList<>();
while (p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
} else {
BSTNode pop = stack.pop();
if (pop.key > key) {
result.add(pop.value);
}
p = pop.right;
}
}
return result;
}
但这样效率不高，可以用 RNL 遍历
注：
- Pre-order, NLR
- In-order, LNR
- Post-order, LRN
- Reverse pre-order, NRL
- Reverse in-order, RNL
- Reverse post-order, RLN
public List<Object> greater(int key) {
ArrayList<Object> result = new ArrayList<>();
BSTNode p = root;
LinkedList<BSTNode> stack = new LinkedList<>();
while (p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.right;
} else {
BSTNode pop = stack.pop();
if (pop.key > key) {
result.add(pop.value);
} else {
break;
}
p = pop.left;
}
}
return result;
}
找之间
public List<Object> between(int key1, int key2) {
ArrayList<Object> result = new ArrayList<>();
BSTNode p = root;
LinkedList<BSTNode> stack = new LinkedList<>();
while (p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
} else {
BSTNode pop = stack.pop();
if (pop.key >= key1 && pop.key <= key2) {
result.add(pop.value);
} else if (pop.key > key2) {
break;
}
p = pop.right;
}
}
return result;
}
小结
优点：
- 如果每个节点的左子树和右子树的大小差距不超过一，可以保证搜索操作的时间复杂度是 O(log n)，效率高。
- 插入、删除结点等操作也比较容易实现，效率也比较高。
- 对于有序数据的查询和处理，二叉查找树非常适用，可以使用中序遍历得到有序序列。
缺点：
- 如果输入的数据是有序或者近似有序的，就会出现极度不平衡的情况，可能导致搜索效率下降，时间复杂度退化成O(n)。
- 对于频繁地插入、删除操作，需要维护平衡二叉查找树，例如红黑树、AVL 树等，否则搜索效率也会下降。
- 对于存在大量重复数据的情况，需要做相应的处理，否则会导致树的深度增加，搜索效率下降。
- 对于结点过多的情况，由于树的空间开销较大，可能导致内存消耗过大，不适合对内存要求高的场景。
结束啦，希望大家能有所成！！！
你好,我是胡广。 致力于为帮助兄弟们的学习方式、面试困难、入职经验少走弯路而写博客 🌹🌹🌹 坚持每天两篇高质量文章输出，加油！！！🤩
如果本篇文章帮到了你 不妨点个赞吧~ 我会很高兴的 😄 (^ ~ ^) 。想看更多 那就点个关注 吧 我会尽力带来有趣的内容 。
😎感兴趣的可以先收藏起来，还有大家在毕设选题，项目以及论文编写等相关问题都可以 给我留言咨询，希望帮助更多的人
更多专栏:
📊 Java设计模式宝典：从入门到精通（持续更新）☔️ 未完待续。。。
🐽 未完待续。。。
⚡️ 未完待续。。。
🌗 未完待续。。。
感谢订阅专栏 三连文章
开源鸿蒙跨平台开发社区汇聚开发者与厂商，共建“一次开发，多端部署”的开源生态，致力于降低跨端开发门槛，推动万物智联创新。
更多推荐
20
0- 0
已为社区贡献1条内容
所有评论(0)