Java中的二叉搜索树(如果想知道Java中有关二叉搜索树的知识点,那么只看这一篇就足够了!)

秋刀鱼不做梦 2024-08-29 11:35:01 阅读 51

        前言:Java 提供了丰富的数据结构来处理和管理数据,其中 TreeSet 和 TreeMap 是基于红黑树实现的集合和映射接口。它们有序地存储数据,提供高效的搜索、插入和删除操作。


✨✨✨这里是秋刀鱼不做梦的BLOG

✨✨✨想要了解更多内容可以访问我的主页秋刀鱼不做梦-CSDN博客

先让我们看一下本文大致的讲解内容:

目录

1.二叉搜索树的认识

        (1)二叉搜索树的概念

        (2)二叉搜索树的性质

2.有关二叉搜索树的常用操作

        【1】插入操作

        【2】查找操作

        【3】删除操作

1.cur.left == null

2.cur.right == null

3.cur.left != null && cur.right != null

3.二叉树的应用场景

1. 数据结构和算法

2. 数据库和文件系统

3. 图形和游戏开发


1.二叉搜索树的认识

        (1)二叉搜索树的概念

        在开始学习TreeSet与TreeMap之前,我们需要先学习一下Java中的二叉搜索树,二叉搜索树是一种特殊的二叉树,其中每个节点都有一个值,并满足以下性质:

对于每个节点,左子树所有节点的值都小于该节点的值。

对于每个节点,右子树所有节点的值都大于该节点的值。

如图:

从上图中我们可以很明显的观察出二叉搜索树的上述两个特性。

        (2)二叉搜索树的性质

        在了解完了二叉搜索树的概念之后,我们需要学习一下有关二叉搜索树的性质,对于一棵二叉搜索树而言,其都有以下三个性质:

有序性:二叉搜索树的中序遍历结果是一个递增的有序序列。

动态性:二叉搜索树支持动态插入和删除操作,适用于需要频繁更新的数据集合。

查找效率:在理想情况下,二叉搜索树的查找、插入和删除操作的时间复杂度为 O(log n)。

        ——这里读者可能会对其中的一些性质不是很理解,没有关系,继续向下进行阅读即可,在后续的文本中,我们会慢慢的理解其中的意思。

2.有关二叉搜索树的常用操作

        【1】插入操作

        插入操作用于向二叉搜索树中插入新值。插入过程从根节点开始,根据当前节点的值与新值的比较结果,决定将新值插入到左子树还是右子树。

以下是实现该操作的代码:

<code>public void insertNode(int key) {

// 如果根节点为空,直接插入新节点作为根节点

if (root == null) {

root = new TreeNode(key);

return;

}

// 初始化当前节点为根节点,父节点为null

TreeNode cur = root;

TreeNode parent = null;

TreeNode node = new TreeNode(key);

// 寻找合适的位置插入节点

while (cur != null) {

if (cur.val < key) { // 当前值小于插入值,向右子树移动

parent = cur;

cur = cur.right;

} else if (cur.val > key) { // 当前值大于插入值,向左子树移动

parent = cur;

cur = cur.left;

} else { // 当前值等于插入值,直接返回,不插入重复值

return;

}

}

// 根据父节点值与插入值的比较结果,插入新节点到左子树或右子树

if (parent.val > key) {

parent.left = node;

} else {

parent.right = node;

}

}

读者可以跟着下面的解释来对上边的代码进行理解:

根节点为空检查

如果 root 为空,直接将新节点 TreeNode(key) 作为根节点插入,并返回。

初始化当前节点和父节点

cur 用于遍历树,从 root 开始。parent 用于记录 cur 的父节点。

寻找合适的插入位置

cur 不为空时,比较 cur.valkey

如果 cur.val 小于 key,移动到右子树。如果 cur.val 大于 key,移动到左子树。如果 cur.val 等于 key,直接返回,不插入重复值。

插入新节点

根据 parent.valkey 的比较结果,将新节点插入到 parent 的左子树或右子树。

        ——这样我们就学会了插入操作了!

        【2】查找操作

        查找操作用于在二叉搜索树中查找特定值。查找过程从根节点开始,根据当前节点的值与目标值的比较结果,决定在左子树还是右子树继续查找。

以下是实现该操作的代码:

public TreeNode search(int key) {

// 初始化当前节点为根节点

TreeNode cur = root;

// 遍历树,直到找到目标节点或遍历到空节点

while (cur != null) {

if (cur.val < key) { // 当前节点值小于目标值,移动到右子树

cur = cur.right;

} else if (cur.val > key) { // 当前节点值大于目标值,移动到左子树

cur = cur.left; // 这里应修正为cur = cur.left;

} else { // 找到目标节点

return cur;

}

}

// 如果没有找到目标节点,返回 null

return null;

}

读者可以跟着下面的解释来对上边的代码进行理解:

初始化当前节点

cur 用于遍历树,从 root 开始。

遍历树

cur 不为空时,比较 cur.valkey

如果 cur.val 小于 key,移动到右子树 (cur = cur.right)。如果 cur.val 大于 key,移动到左子树 (cur = cur.left)。如果 cur.val 等于 key,返回当前节点。

返回结果

如果遍历完整棵树没有找到目标节点,返回 null

        【3】删除操作

        删除操作用于从二叉搜索树中删除指定值。删除节点分为三种情况:叶子节点、只有一个子节点的节点和有两个子节点的节点。

        由于删除操作比较哦啊复杂,所以我们这里重点讲解一下,对于删除操作,我们可能会有以下的可能情况:

——现在我们假设待删除结点为 cur, 待删除结点的双亲结点为 parent:

1.cur.left == null

        1. cur 是 root,则 root = cur.right

        2. cur 不是 root,cur 是 parent.left,则 parent.left = cur.right

        3. cur 不是 root,cur 是 parent.right,则 parent.right = cur.right

2.cur.right == null

        1. cur 是 root,则 root = cur.left

        2. cur 不是 root,cur 是 parent.left,则 parent.left = cur.left

        3. cur 不是 root,cur 是 parent.right,则 parent.right = cur.left

3.cur.left != null && cur.right != null

        这时我们就需要使用替换法进行删除,即在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删除节点中,再来处理该结点的删除问题

我们大致了解了删除的三种可能的大情况之后,现在让我们尝试着编写一下代码:

public void remove(int key) {

TreeNode parent = null; // 父节点初始化为 null

TreeNode cur = root; // 当前节点初始化为根节点

// 遍历树,寻找要删除的节点

while (cur != null) {

if (cur.val < key) { // 当前值小于目标值,移动到右子树

parent = cur;

cur = cur.right;

} else if (cur.val > key) { // 当前值大于目标值,移动到左子树

parent = cur;

cur = cur.left;

} else { // 找到目标节点

removeNode(parent, cur); // 调用辅助方法删除节点

return; // 删除节点后退出方法

}

}

}

private void removeNode(TreeNode parent, TreeNode cur) {

if (cur.right == null) { // 当前节点没有右子树

if (cur == root) { // 当前节点是根节点

root = root.left; // 根节点指向左子树

} else if (parent.left == cur) { // 当前节点是父节点的左子节点

parent.left = cur.left; // 父节点左子节点指向当前节点的左子树

} else { // 当前节点是父节点的右子节点

parent.right = cur.left; // 父节点右子节点指向当前节点的左子树

}

} else if (cur.left == null) { // 当前节点没有左子树

if (cur == root) { // 当前节点是根节点

root = root.right; // 根节点指向右子树

} else if (parent.left == cur) { // 当前节点是父节点的左子节点

parent.left = cur.right; // 父节点左子节点指向当前节点的右子树

} else { // 当前节点是父节点的右子节点

parent.right = cur.right; // 父节点右子节点指向当前节点的右子树

}

} else { // 当前节点有两个子节点

TreeNode targetParent = cur; // 目标节点的父节点初始化为当前节点

TreeNode target = cur.right; // 目标节点初始化为当前节点的右子节点

// 寻找右子树中的最左节点

while (target.left != null) {

targetParent = target;

target = target.left;

}

cur.val = target.val; // 用右子树中最左节点的值替换当前节点的值

// 调整指针以删除目标节点

if (targetParent.left == target) {

targetParent.left = target.right;

} else {

targetParent.right = target.right;

}

}

}

——这里我们给每一条代码都加上了注释,读者可以根据注释来对上述代码进行理解!!!

这样我们就了解了二叉搜索树中常用的操作了.

3.二叉树的应用场景

        学习完二叉树的概念以及其基本的使用之后,让我们来学习一些二叉树的应用场景,二叉树(Binary Tree)在日常中有着广泛的应用。以下是一些主要的实际应用场景:

1. 数据结构和算法

二叉搜索树(BST):用于实现高效的搜索、插入和删除操作,时间复杂度平均为 O(log n)。

平衡树(如AVL树、红黑树):这些是自平衡二叉搜索树,确保树的高度保持在 O(log n),从而提供高效的操作。

堆(Heap):二叉堆用于实现优先队列。最大堆用于实现高效的最大值查找,最小堆用于最小值查找。

2. 数据库和文件系统

B树和B+树:这些是多路搜索树,常用于数据库索引和文件系统索引,以提高查询和检索的效率。

Trie树:一种多叉树,用于实现前缀匹配,常用于字典存储和自动补全功能。

3. 图形和游戏开发

四叉树和八叉树:用于空间分割,以提高碰撞检测、渲染和其他空间查询操作的效率。

场景图(Scene Graph):在3D图形引擎中,场景图是一个树状结构,用于管理和渲染场景中的对象。

这样我们就大致的了解了二叉树在今后的日常中有哪些用武之地了!!!


以上就是本篇文章的主要内容了!!!



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。