手机编辑WordPress博客,西安seo报价,邵阳网站seo,化州市建设局网站꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好#xff0c;我是xiaoxie.希望你看完之后,有不足之处请多多谅解#xff0c;让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN … ꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好我是xiaoxie.希望你看完之后,有不足之处请多多谅解让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转载还请通知˶⍤⃝˶个人主页xiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 系列专栏xiaoxie的JAVA系列专栏——CSDN博客●ᴗσσணღ*我的目标:团团等我( ◡̀_◡́ ҂) ( ⸝⸝⸝›ᴥ‹⸝⸝⸝ )欢迎各位→点赞 收藏⭐️ 留言关注互三必回! 一.二叉平衡树
1.二叉平衡树的概念
二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树:
若它的左子树不为空则左子树上所有节点的值都小于根节点的值
若它的右子树不为空则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树 从上述概念以及图中可以看出二叉搜索树具有以下特性
1. 二叉搜索树中最左侧的节点是树中最小的节点最右侧节点一定是树中最大的节点
2. 采用中序遍历遍历二叉搜索树可以得到一个有序的序列
2.二叉搜索树的主要操作
1. 查询 2.插入
1.插入的为一颗空树
直接插入即可
2.. 如果树不是空树按照查找逻辑确定插入位置插入新结点
根据二叉搜索树的性质插入节点,左小右大
对于树中的任意节点 n其左子树中的所有节点的值都小于 n 的值其右子树中的所有节点的值都大于 n 的值。在插入新节点时需要按照二叉搜索树的性质找到合适的位置插入保持树的有序性。插入节点后需要调整树的结构保证树仍然是一个二叉搜索树。
3.删除
假设删除节点cur那么cur有以下几种情况
1.cur 的左孩子为空,右孩子不为空,
2.cur 的右孩子为空,左孩子不为空.
3.cur 的左右孩子均为空.
4.cur 的左右孩子均不为空.
接下来博主将会通过画图的形式来演示这四种情况该如何删除节点
1.cur 的左孩子为空,右孩子不为空 2.cur 的右孩子为空,左孩子不为空. 3. cur 的左右孩子均为空. 4. cur 的左右孩子均不为空. 1.假设我们需要删除节点70,我们首先需要通过遍历二叉搜索树,找到70这个节点的对应位置.
2.我们发现70这个节点,左右孩子均不为空,这个时候就不可以通过简单的删除就可以了,我们需要用到替换法,即在它的右子树中寻找中序下的第一个结点(关键码最小)用它的值填补到被 删除节点中再来处理该结点的删除问题.
2.1这里解释一下为什么是在它的右子树中寻找中序下的第一个结点(关键码最小),当需要删除一个节点时如果该节点有右子树则可以在右子树中找到中序遍历下的第一个节点即右子树中最小的节点来替代当前节点。这是因为右子树中的所有节点都大于当前节点而右子树中最小的节点又小于右子树中的所有其他节点所以用右子树中的最小节点来替代当前节点可以保持二叉搜索树的性质不变。
3.找到替罪羊节点 t 后我们就需要把要删除的节点cur使他的值等于t .
4.最后删除节点t即可.
4.二叉搜索树基本操作的Java代码实现
public class BinarySearchTree {public static class TreeNode {public TreeNode left;public TreeNode right;public int val;public TreeNode(int val) {this.val val;}}public TreeNode root;/*** 查询节点是否存在* author xiaoxie* date 2024/3/6 10:44* param val* return boolean*/public boolean search(int val) {if(root null) {System.out.println();return false;}TreeNode cur root;while (cur ! null) {if(val cur.val) {cur cur.left;} else if (val cur.val) {cur cur.right;}else {System.out.println(找到了);return true;}}System.out.println(该节点val不存在);return false;}/*** 插入节点* author xiaoxie* date 2024/3/6 10:47* param val*/public void insertTreeNode(int val) {TreeNode node new TreeNode(val);if(root null) {root node;return;}TreeNode parent null;TreeNode cur root;while (cur ! null) {if(node.val cur.val) {parent cur;cur cur.left;} else if (node.val cur.val) {parent cur;cur cur.right;}else {System.out.println(节点值 val 已经存在于树中不进行插入操作);return;}}//cur nullif(node.val parent.val) {parent.left node;}else {parent.right node;}}/*** 删除节点* 可以使用替罪羊的方法来实现* author xiaoxie* date 2024/3/6 12:15* param val* return boolean*/public boolean remove(int val) {//首先先找到是哪一个节点if(root null) {return false;}TreeNode parent null;TreeNode cur root;while (cur ! null) {if(cur.val val) {parent cur;cur cur.left;} else if (cur.val val) {parent cur;cur cur.right;}else {break;}}//cur null 说明要删除的节点不在二叉搜索树上if(cur null) {return false;}// cur有多种情况//1.cur 没有左右孩子//2.cur 只有左孩子//3.cur 只有右孩子//4.cur 有左右孩子 -- 需要使用替罪羊的方法来删除if(cur.right ! null cur.left ! null) {TreeNode t cur.right;TreeNode tp cur;while (t.left ! null) {tp t;t t.left;}cur.val t.val;//使要删除的节点的值等于替罪羊节点//删除替罪羊节点if(tp.left t) {tp.left t.right;}else {//出现tp.right t 的情况,t节点一开始就是叶子节点tp.right t.right;}}else {//cur 只有右孩子if(cur.left null cur.right ! null){if(parent null) {root cur.right;}else {if(parent.val cur.val) {parent.right cur.right;}else {parent.left cur.right;}}}//cur 只有左孩子else if (cur.left ! null cur.right null) {if(parent null) {root cur.left;}else {if(parent.val cur.val) {parent.right cur.left;}else {parent.left cur.left;}}}//cur 没有左右孩子else {if(parent null) {root null;}else {if(parent.val cur.val) {parent.right null;}else {parent.left null;}}}}return true;}5.性能分析
插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。 对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二叉搜索树的深度 的函数即结点越深则比较次数越多。 但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树
1.最优情况下二叉搜索树为完全二叉树 其平均比较次数为log N;
2.最差情况下二叉搜索树退化为单支树 其平均比较次数为: 2 / N
问题如果退化成单支树二叉搜索树的性能就失去了。那能否进行改进不论按照什么次序插入关键码都可以 是二叉搜索树的性能最佳
那就需要用到AVL树了通过旋转来使二叉搜索树变成完全二叉树的形式,这里博主就不过多的赘述了,如果感兴趣,可以为博主点上一个关注,在下一篇文章中,博主将详细解读AVL树
感谢你的阅读!
