怎么查网站做404页面没,最好用的免费建站平台,亚马逊在电子商务网站建设,网站后台添加表格我们的心永远向前憧憬
尽管活在阴沉的现在
一切都是暂时的,转瞬即逝,
而那逝去的将变为可爱 #x1f31d;(俄) 普希金 假如生活欺骗了你 1.二叉搜索树的概念
概念:搜索树#xff08;Search Tree#xff09;是一种有序的数据结构#xff0c;用于存储和组…我们的心永远向前憧憬
尽管活在阴沉的现在
一切都是暂时的,转瞬即逝,
而那逝去的将变为可爱 (俄) 普希金 假如生活欺骗了你 1.二叉搜索树的概念
概念:搜索树Search Tree是一种有序的数据结构用于存储和组织一组元素。它提供高效的搜索、插入和删除操作。 组成:搜索树是由节点Node组成的树状结构每个节点包含一个关键字Key和相关的数据Data。通过比较节点的关键字可以确定元素在搜索树中的位置。
常见的搜索树包括二叉搜索树Binary Search Tree和平衡二叉搜索树Balanced Binary Search Tree如红黑树Red-Black Tree、AVL树等。
本篇文章主要讲的是二叉搜索树
在二叉搜索树中每个节点最多有两个子节点且左子节点的关键字小于父节点的关键字右子节点的关键字大于父节点的关键字。这种有序性质使得在搜索树中进行搜索操作时可以通过比较关键字的大小来决定搜索方向从而快速地找到目标元素,简而言之如下:
若它的左子树不为空则左子树上所有节点的值都小于根节点的值 若它的右子树不为空则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树 比如有一组数组:
int array[] {{5,3,4,1,7,8,2,6,0,9}
则它的二叉搜索树为: 2.二叉搜索树的定义类
public class BinarySearchTree {static class TreeNode{public int val;//元素public TreeNode left;//左子树public TreeNode right;//右子树public TreeNode(int val){this.val val;}}public TreeNode root;
}
3.实现二叉搜索树的查找
执行步骤:
从root根节点开始将要查找的关键字与当前节点的关键字进行比较。如果要查找的key关键字等于当前节点的关键字则找到了目标元素查找成功。如果要查找的key关键字小于当前节点的关键字则继续在当前节点的左子树中进行查找。如果要查找的key关键字大于当前节点的关键字则继续在当前节点的右子树中进行查找。如果当前节点的左子树或右子树为空表示查找失败目标元素不存在于树中。重复步骤1-5直到找到目标元素或确定目标元素不存在。
例子解释:
现在有一组数据:查找关键字8
int array[] {{5,3,4,1,7,8,2,6,0,9}
逻辑思路:
初始化一个指针将其指向根节点例如使用cur指针并将其初始值设置为根节点。进入一个循环循环条件是当前节点不为空即cur不为null。在循环中比较当前节点的关键字与目标关键字的大小关系。如果当前节点的关键字小于目标关键字说明目标元素应该在当前节点的右子树中将当前节点指针cur移动到右子节点即cur cur.right。如果当前节点的关键字大于目标关键字说明目标元素应该在当前节点的左子树中将当前节点指针cur移动到左子节点即cur cur.left。如果当前节点的关键字等于目标关键字表示已经找到了目标元素可以返回true或执行其他相应的操作。如果循环结束仍然没有找到目标元素即当前节点为空表示查找失败可以返回false或执行其他相应的操作。
如视频展示: 二叉树搜索树-寻找 代码如下:
public boolean search(int key){TreeNode cur root; // 初始化当前节点指针cur为根节点rootwhile(cur ! null){ // 循环条件当前节点cur不为空if(cur.val key){ // 如果当前节点的值小于目标关键字keycur cur.right; // 移动当前节点指针cur到右子节点}else if(cur.val key){ // 如果当前节点的值大于目标关键字keycur cur.left; // 移动当前节点指针cur到左子节点}else {return true; // 当前节点的值等于目标关键字key找到了目标元素返回true}}return false; // 循环结束仍然没有找到目标元素返回false表示查找失败
}
时间复杂度
平均情况下二叉搜索树的查找操作时间复杂度为O(log n)其中n是二叉搜索树中的节点数。每次比较都可以将搜索范围缩小一半。最坏情况下(只有左子树或右子树)如果二叉搜索树是非平衡树查找操作的时间复杂度可能达到O(n)其中n是二叉搜索树中的节点数。树的结构类似于链表需要遍历从根节点到叶子节点的路径。
空间复杂度
在迭代方式的二叉搜索树查找中只使用了常数级别的额外空间即只有一个额外的指针用于保存当前节点的引用因此空间复杂度为O(1)。 4.实现二叉搜索树的插入
执行步骤:
首先检查根节点root是否为空。如果为空表示该二叉搜索树为空树将新节点TreeNode(val)作为根节点插入并返回true表示插入成功。如果根节点不为空初始化当前节点指针cur为根节点root父节点指针parent为null。进入循环条件为当前节点cur不为空。在循环中比较当前节点cur的值与待插入值val的大小关系循环结束后表明找到了合适的插入位置。创建新节点TreeNode(val)。判断父节点parent的值与待插入值val的大小关系返回true表示插入成功。
视频展示如下: 二叉树搜索树-插入 代码如下:
public boolean insert(int val){if(root null){ // 如果根节点为空将新节点作为根节点插入root new TreeNode(val);return true;}TreeNode cur root; // 初始化当前节点指针cur为根节点rootTreeNode parent null; // 初始化父节点指针parent为空while(cur ! null){ // 循环条件当前节点cur不为空if(cur.val val){ // 如果当前节点的值小于待插入值valparent cur; // 更新父节点指针为当前节点cur cur.right; // 移动当前节点指针cur到右子节点} else if (cur.val val) { // 如果当前节点的值大于待插入值valparent cur; // 更新父节点指针为当前节点cur cur.left; // 移动当前节点指针cur到左子节点} else{ // 如果当前节点的值等于待插入值val即已存在相同值的节点return false; // 返回false表示插入失败不允许插入重复值}}TreeNode node new TreeNode(val); // 创建新节点if(parent.val val){ // 如果父节点的值大于待插入值valparent.left node; // 将新节点插入为父节点的左子节点}else {parent.right node; // 将新节点插入为父节点的右子节点}return true; // 返回true表示插入成功
}
时间复杂度 在最坏情况下即二叉搜索树是一个非平衡树的情况下插入操作的时间复杂度为O(n)其中n是二叉搜索树中的节点数。这种情况下树的结构类似于链表每次插入都需要遍历从根节点到叶子节点的路径。
在平均情况下二叉搜索树的插入操作的时间复杂度为O(log n)其中n是二叉搜索树中的节点数。每次插入操作都可以将搜索范围减半因此插入操作的时间复杂度是对数级别的。
空间复杂度 在二叉搜索树的插入操作中只需要使用常数级别的额外空间即只有几个指针变量用于保存当前节点和父节点的引用。因此插入操作的空间复杂度为O(1)。 5.实现二叉搜索树的删除
具体删除操作分三种情况:
第一种情况待删除节点cur没有左子节点。
如果cur是根节点直接将根节点指向其右子节点cur.right。如果cur是父节点parent的左子节点将父节点的左子节点指向cur.right。如果cur是父节点parent的右子节点将父节点的右子节点指向cur.right。
视频展示: 二叉搜索树-删除-1 第二种情况待删除节点cur没有右子节点。
如果cur是根节点直接将根节点指向其左子节点cur.left。如果cur是父节点parent的左子节点将父节点的左子节点指向cur.left。如果cur是父节点parent的右子节点将父节点的右子节点指向cur.left。
视频展示 二叉树搜索树-删除-2 第三种情况待删除节点cur既有左子节点又有右子节点。
注意:待删除结点的数据将来放的数据一定是比左边都大,比右边都小的数据 如何寻找数据?要么在左树里面找到最大的数据[即左树最右边的数据]
要么在右树里面找到最小的数据[即右数最左边的数据]
下面我使用的是在右数找最小值
执行步骤:
找到待删除节点cur的右子树中的最小节点target即右子树中最左侧的节点。将最小节点target的值赋给待删除节点cur相当于将cur节点的值替换为target节点的值。删除最小节点target即对最小节点target执行第一种或第二种情况的删除操作。 视频展示: 二叉搜索树-删除-3 注意:
当target没有左孩子时,应当时targetParent.right target.right 代码如下:
public void remove(int key){TreeNode cur root; // 初始化当前节点指针cur为根节点rootTreeNode parent null; // 初始化父节点指针parent为空while(cur ! null){ // 循环条件当前节点cur不为空if(cur.val key){ // 如果当前节点的值cur.val小于待删除值keyparent cur; // 更新父节点指针parent为当前节点curcur cur.right; // 将当前节点指针cur移动到右子节点cur.right} else if (cur.val key) { // 如果当前节点的值cur.val大于待删除值keyparent cur; // 更新父节点指针parent为当前节点curcur cur.left; // 将当前节点指针cur移动到左子节点cur.left} else { // 当前节点的值cur.val等于待删除值key找到待删除节点removeNode(cur, parent); // 调用removeNode函数执行删除操作}}
}private void removeNode(TreeNode cur, TreeNode parent) {// 第一种情况待删除节点cur没有左子节点if(cur.left null){if(cur root){ // 如果待删除节点cur是根节点root cur.right; // 直接将根节点指向其右子节点cur.right} else if (cur parent.left) { // 如果待删除节点cur是父节点parent的左子节点parent.left cur.right; // 将父节点的左子节点指向cur.right} else { // 如果待删除节点cur是父节点parent的右子节点parent.right cur.right; // 将父节点的右子节点指向cur.right}}// 第二种情况待删除节点cur没有右子节点else if(cur.right null){if(cur root){ // 如果待删除节点cur是根节点root cur.left; // 直接将根节点指向其左子节点cur.left} else if(cur parent.left){ // 如果待删除节点cur是父节点parent的左子节点parent.left cur.left; // 将父节点的左子节点指向cur.left} else { // 如果待删除节点cur是父节点parent的右子节点parent.right cur.left; // 将父节点的右子节点指向cur.left}}// 第三种情况待删除节点cur既有左子节点又有右子节点else {TreeNode targetParent cur; // 初始化目标节点的父节点指针为curTreeNode target cur.right; // 初始化目标节点指针为cur的右子节点while(target.left ! null){ // 寻找cur右子树中的最小节点targetParent target; // 更新目标节点的父节点指针为targettarget target.left; // 将目标节点指针移动到左子节点target.left}cur.val target.val; // 将目标节点的值赋给待删除节点cur相当于替换值if(targetParent.left target){ // 如果目标节点是其父节点的左子节点targetParent.left target.right; // 将目标节点的右子节点连接到目标节点的父节点的左子节点上} else { // 如果目标节点是其父节点的右子节点targetParent.right target.right; // 将目标节点的右子节点连接到目标节点的父节点的右子节点上}}
}
时间复杂度
在平均情况下二叉搜索树的高度为O(log N)其中N是树中节点的总数。在删除节点的过程中需要遍历树以找到待删除节点的位置这需要沿着树的高度移动。因此平均情况下删除节点的时间复杂度为O(log N)。在最坏情况下如果二叉搜索树是一个不平衡的树即所有节点都只有一个子节点删除节点的时间复杂度可以达到O(N)其中N是树中节点的总数。这种情况发生在树没有进行平衡操作或者插入和删除操作导致树失去平衡的情况下。
空间复杂度
删除节点的过程中使用了常数级别的额外空间主要是用于存储当前节点指针cur和父节点指针parent。因此删除节点的空间复杂度为O(1)。 6.总结
二叉搜索树的查找、插入和删除操作都是基于节点值的比较来进行的。查找操作的时间复杂度为O(log N)其中N是树中节点的总数。插入和删除操作的时间复杂度也是O(log N)但在最坏情况下树不平衡时间复杂度可能达到O(N)。二叉搜索树的插入和删除操作可以保持树的有序性但如果插入和删除操作频繁且不平衡可能会导致树的高度增加降低操作效率。为了解决不平衡问题可以使用平衡二叉搜索树如AVL树、红黑树等数据结构来保持树的平衡性以提高查找、插入和删除操作的性能。 结语:
二叉搜索树提供了一种简洁而强大的数据结构它不仅仅是一棵树更是一种思想。通过理解和应用二叉搜索树的原理我们可以解决各种问题如数据的排序、查找最小/最大值、范围查询等。
在结束之际让我们怀着对二叉搜索树的敬意继续探索和学习更多的数据结构和算法为解决复杂的计算问题开辟新的道路。无论是在计算机科学的领域中还是在生活的各个方面二叉搜索树的智慧将继续指引我们前行。
