网站布局方案,wordpress 外链图片自动,wordpress无法设置中文,网站建设什么公司好红黑树简介及左旋、右旋、变色 红黑树(Red Black Tree)是一种自平衡二叉搜索树(二叉查找树)#xff0c;是一种特殊的二叉搜索树#xff0c;在进行插入和删除时通过特定操作保持二叉树自身的平衡#xff0c;从而获得较高的查找性能。
红黑树的平衡操作通过左旋、右旋和变色来…红黑树简介及左旋、右旋、变色 红黑树(Red Black Tree)是一种自平衡二叉搜索树(二叉查找树)是一种特殊的二叉搜索树在进行插入和删除时通过特定操作保持二叉树自身的平衡从而获得较高的查找性能。
红黑树的平衡操作通过左旋、右旋和变色来实现平衡的过程是比较复杂的但通过平衡操作可以获得更高效的性能。对二叉搜索树进行平衡后最坏情况的运行时间得到优化可以在O(logN)的时间复杂度内完成查找、插入和删除N是二叉搜索树中的节点数。
一、二叉搜索树的性能分析
红黑树是一种特殊的二叉搜索树所以本文先从二叉搜索树说起。
二叉搜索树是一种特殊的二叉树具有如下特性
1. 如果二叉树的左子树不为空则左子树上所有节点的值均小于它的根节点的值。
2. 如果二叉树的右子树不为空则右子树上所有节点的值均大于它的根节点的值。
3. 如果独立地看左子树、右子树也分别为二叉搜索树。
二叉搜索树的实现可以参考Python实现二叉搜索树_小斌哥ge的博客-CSDN博客
向二叉搜索树中插入数据时为了满足二叉搜索树的特性会递归地比较插入节点的值与根节点的值将数据插入正确的位置。
如在一棵空二叉搜索树中插入 [50, 77, 55, 29, 10, 30, 66, 80, 51, 18, 90] 得到的二叉搜索树结构如下图 二、红黑树简介
红黑树是一种自平衡二叉搜索树每个节点都有颜色颜色为红色或黑色红黑树由此得名。除了满足二叉搜索树的特性以外红黑树还具有如下特性
1. 节点是红色或黑色。
2. 根节点是黑色。
3. 所有叶子节点都是黑色的空节点。(叶子节点是NIL节点或NULL节点)
4. 每个红色节点的两个子节点都是黑色节点。(从每个叶子节点到根的所有路径上不能有两个连续的红色节点)
5. 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。
要知道什么是红黑树必须记住这5条特性。这5条特性其实是5条规定只有满足这5条规定才属于红黑树。对于二叉搜索树的特性只要理解了很容易记住但对于红黑树的5条特性需要“死记硬背”。
如上面例子中的二叉搜索树可以加上颜色变成一颗红黑树。(实际的红黑树是一个节点一个节点插入的如下的构造过程只是为了先理解红黑树的5条特性)
1. 先加上叶子节点并把所有节点都标记为黑色。 2. 这棵二叉树显然不满足红黑树的特性5如节点10到左子树的叶子节点的路径上有一个黑节点到右子树的叶子节点的路径上有两个黑节点所以要将一些黑节点变成红节点。
从根节点50开始使根节点到每个叶子节点的路径上都有4个黑节点得到的红黑树如下。 当然也可以使根节点到每个叶子节点的路径上都有3个黑节点得到的红黑树如下。 现在看一下这两棵树是否满足红黑树的5条特性可以一条一条的对比至于构造的过程先不管(这其实是硬拼出来的)后面再讲怎么构造。
根据红黑树的特性5任意节点到其所有叶节点的路径上的黑节点数都相同从而保持红黑树的平衡。如果只看黑节点这种平衡是完美的平衡所以红黑树的平衡也称为黑色完美平衡。当然因为红节点的存在红黑树并不是完美平衡的甚至有可能不满足平衡二叉树的特性。
当在红黑树中插入节点或删除节点时红黑树的平衡很可能会被破坏(不满足其中一条或多条特性)要立即对红黑树进行调整使红黑树重新满足5条特性。
调整平衡的操作包含左旋、右旋和变色下面依次对这些操作进行介绍。
三、红黑树的左旋和右旋操作
对于一棵红黑树它满足红黑树的5条特性。插入或删除节点之后红黑树就发生了变化很可能不再完全满足红黑树的5条特性了也就是不再是一棵红黑树了而是一棵普通的二叉搜索树。这时候为了使二叉搜索树重新变成红黑树就需要对二叉搜索树进行操作使它满足红黑树的5条特性。
通过旋转可以使二叉搜索树重新满足红黑树的5条特性。旋转分为左旋和右旋。
1. 红黑树的左旋
左旋以某个节点作为支点(旋转节点)其右子节点变为旋转节点的父节点右子节点的左子节点变为旋转节点的右子节点旋转节点的左子节点保持不变。右子节点的左子节点相当于从右子节点上“断开”重新连接到旋转节点上。
为了不失一般性可以看下图中的例子。左边是左旋前的红黑树局部结构先不考虑整体只看局部左旋前不满足红黑树的特性5。
左旋时旋转节点为节点50左旋后旋转节点的右子节点70变为旋转节点50的父节点右子节点的左子节点60从右子节点70上“断开”成为旋转节点50的右子节点。
2. 红黑树的右旋
右旋以某个节点作为支点(旋转节点)其左子节点变为旋转节点的父节点左子节点的右子节点变为旋转节点的左子节点旋转节点的右子节点保持不变。左子节点的右子节点相当于从左子节点上“断开”重新连接到旋转节点上。
不难看出左旋和右旋是相反的可逆的。
下图中的例子仍然是红黑树的局部左边的结构不满足红黑树的特性5。
右旋时旋转节点为节点70右旋后旋转节点的左子节点50变为旋转节点70的父节点左子节点的右子节点60从左子节点50上“断开”成为旋转节点70的左子节点。右旋后(右图)重新满足了红黑树的特性5。
四、红黑树的变色操作
当对红黑树进行插入或删除节点之后如果不再完全满足红黑树的5条特性除了旋转变色也可以使二叉搜索树重新满足红黑树的5条特性。
变色将节点的颜色由红变黑或由黑变红。
向红黑树中插入节点时新节点的颜色都设置为红色。不管新节点是什么颜色特性3都不可能被破坏特性1、2、4都有可能被破坏。如果插入的节点是黑色则一定会破坏特性5需要进行调整如果插入的节点是红色则一定不会破坏特性5。所以将新节点设置为红色可以降低破坏红黑树特性的可能性。
MySQL 基础架构
下图是 MySQL 的一个简要架构图从下图你可以很清晰的看到客户端的一条 SQL 语句在 MySQL 内部是如何执行的。 从上图可以看出 MySQL 主要由下面几部分构成
连接器 身份认证和权限相关(登录 MySQL 的时候)。查询缓存 执行查询语句的时候会先查询缓存MySQL 8.0 版本后移除因为这个功能不太实用。分析器 没有命中缓存的话SQL 语句就会经过分析器分析器说白了就是要先看你的 SQL 语句要干嘛再检查你的 SQL 语句语法是否正确。优化器 按照 MySQL 认为最优的方案去执行。执行器 执行语句然后从存储引擎返回数据。 执行语句之前会先判断是否有权限如果没有权限的话就会报错。插件式存储引擎主要负责数据的存储和读取采用的是插件式架构支持 InnoDB、MyISAM、Memory 等多种存储引擎。
