下载网站的服务器文件,水果门户网站建设,咨询机构,廊坊头条新闻最新消息新闻平衡二叉树左旋右旋与红黑树
平衡二叉树
定义
平衡二叉树是二叉搜索树的一种特殊形式。二叉搜索树#xff08;Binary Search Tree#xff0c;BST#xff09;是一种具有以下性质的二叉树#xff1a;
对于树中的每个节点#xff0c;其左子树中的所有节点都小于该节点的值…平衡二叉树左旋右旋与红黑树
平衡二叉树
定义
平衡二叉树是二叉搜索树的一种特殊形式。二叉搜索树Binary Search TreeBST是一种具有以下性质的二叉树
对于树中的每个节点其左子树中的所有节点都小于该节点的值。对于树中的每个节点其右子树中的所有节点都大于该节点的值。左子树和右子树都必须是二叉搜索树。
而平衡二叉树Balanced Binary Tree在满足了二叉搜索树的所有性质的基础上还额外保证了树的高度尽可能小即任意节点的左右子树高度差不超过1。
举例
以下是平衡二叉树的几个例子 旋转机制
平衡二叉树通过旋转操作来保持其平衡性。旋转操作主要有两种类型左旋转和右旋转。这些旋转操作通常应用于AVL树和红黑树等平衡二叉树的调整过程中。
左旋转左旋转是一种操作将一个节点的右子节点提升为新的根节点原来的根节点成为新根节点的左子节点。左旋转的目的是减小树的整体高度以维持平衡。
右旋转右旋转是一种操作将一个节点的左子节点提升为新的根节点原来的根节点成为新根节点的右子节点。右旋转的目的也是减小树的整体高度以维持平衡。
触发时机当添加一个节点之后该树不再是一颗平衡二叉树
左旋
当我们想给 这个二叉树中插入一个新的节点12这个平衡二叉树就会变为 此时我们就会发现二叉树不平衡了为了重新平衡我们就需要进行旋转了。
为了进行旋转我们需要去寻找支点从添加的节点开始不断的往父节点找不平衡的节点 这里我们从节点12开始往上找 节点11平衡节点10不平衡 所以节点10为支点 左旋的步骤
以不平衡的点作为支点把支点左旋降级变成左子节点晋升原来的右子节点
旋转后的二叉树为 以上为较为简单的左旋下面为较为复杂的左旋 已知二叉树不平衡 还是需要从添加的节点向上找不平衡的节点 节点11平衡节点10平衡节点7不平衡 节点7为支点 而此时旋转的步骤和刚才的就有所不同了
以不平衡的点作为支点将根节点的右侧往左拉原先的右子节点变成新的父节点并把多余的左子节点出让给已经降级的根节点当右子节点
在上面的二叉树中多余的节点为节点9节点9为节点10的左子结点很重要。
下面为具体步骤 先将节点9多余的左子节点分离 以节点7为支点进行左旋 将多余的节点进行分配 因为节点9之前为节点10的左子结点所以此时9节点应该继续接才节点10的左边此处应该放在节点7的右节点上 右旋
右旋与左旋在处理上是类似的就不再粘贴图示了
步骤
以不平衡的点作为支点就是将根节点的左侧往右拉原先的左子节点变成新的父节点并把多余的右子节点出让给已经降级的根节点当左子节点
需要旋转的四种情况
1.左左一次右旋
当根节点左子树的左子树有节点插入导致二叉树不平衡 有两种添加情况 以节点7为根节点
我们只需要进行一次右旋就可以了 2.左右两次旋转
当根节点左子树的右子树有节点插入导致二叉树不平衡 添加节点 此时仅仅一次右旋就不能实现平衡了。
我们需要先一4为支点先局部左旋再整体右旋就可以实现了 3.右右一次旋转
当根节点右子树的右子树有节点插入导致二叉树不平衡 添加节点12 以节点7为支点进行左旋一次就能实现平衡 4.右左两次旋转
当根节点右子树的左子树有节点插入导致二叉树不平衡 添加节点8 先局部右旋再整体左旋 红黑树
红黑树是一种自平衡的二叉查找树是计算机科学中用到的一种数据结构。1972年出现当时被称之为平衡二叉B树。后来1978年被修改为如今的红黑树它是一种特殊的二叉查找树红黑树的每一个节点上都有存储位表示节点的颜色每一个节点可以是红或者黑;红黑树不是高度平衡的它的平衡是通过红黑规则进行实现的 红黑规则
每一个节点或是红色的或者是黑色的根节点必须是黑色如果一个节点没有子节点或者父节点则该节点相应的指针属性值为Nǐl这些Nil视为叶节点每个叶节点(Nil)是黑色的如果某一个节点是红色那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)对每一个节点从该节点到其所有后代叶节点的简单路径上均包含相同数目的黑色节点
添加节点规则
默认颜色添加节点默认是红色的(效率高)
举例
假设我们需要添加三个节点201823
1.假设三个节点都是黑色的 先添加节点20 然后添加节点18 此时我们发现我们的红黑树已经违背了红黑规则第五条规则
如果我们把节点18变为红色则就满足了红黑规则 下来存节点23 依旧违背红黑规则将23变为红色 一共调整了两次节点颜色
2.假设节点颜色都为红色
那么先添加节点20 违背了规则2
将节点变为黑色后插入节点18 并没有违背红黑规则不需要调整
下来添加节点23 依然不需要调整。
一共调整了一次节点颜色
所以我们得出结论默认颜色添加节点默认是红色的(效率高)
小结
本篇博客到这里就结束了如果有错误麻烦大家指正感谢阅读
已经到底啦
