红黑树 二叉树 b树_二叉排序树定义

二叉排序树、红黑树、AVL树最简单的理解 　　##前言 　　[为什么写这篇] 　　之前在知乎上看过一个提问：为什么红黑树比AVL树用的场景更为广泛？其实，这两者应用场景都挺广泛的。红黑树在  和  都有一定的运用。而AVL树也在  中得到了使用。既然红黑树和AVL树这么厉害，就要进一步了解一下它们到底是什么。 　　##基础准备 　　[需要懂点数据结构哦] 　　红黑树和AVL都是来源于二叉排序树，关于二叉搜索树的相关知识本文将会对一些简单的概念和操作进行分析，更多的细节需要大家自己去进一步了解。（ps:算法导论或许是一个不错的选择） 　　##二叉排序树 　　[一切为了查找、插入、删除方便] 　　我们都知道，线性表分为无序线性表和有序线性表。 　　无序线性表的数据并不是按升序或者降序来排列的，所以在插入和删除时，没有什么必须遵守的规矩而可以插入在数据尾部或者删除在数据尾部（将待删除的数据和最后一个数据交换位置），但是在查找的时候，需要遍历整个数据集，影响了效率。 　　有序线性表的数据则想法，查找的时候因为数据有序，可以用二分法、插值法、斐波那契查找法来实现，但是，插入和删除需要维护有序的结构，会耗费大量的时间。 　　为了提高插入和删除的效率，二叉排序树登场了。 　　二叉排序树的定义 　　二叉排序树  是一棵具有下列性质的二叉树。 若它的左子树不空，则左子树上所有结点的值均小于它的根结构的值若它的右子树不空，则右子树上所有结点的值均大于它的根结构的值它的左子树和右子树都是二叉排序树 　　定义中最为关键的特点是，左子树结点一定比父结点小，右子树结点一定比父结点大 　　
　　二叉排序树查找 　　通过观察上面的二叉排序树，可以知道，查找树中一个值，可以从根结点开始查找，和根结点的值做比较，比根结点的值小，就在根结点的左子树中查找，比根结点的值大，就在根结点的右子树中查找。其他结点的行为与根结点的行为也是一样的。以此出发，可以得到递归算法： 如果树是空的，则查找结束，无匹配。如果被查找的值和根结点的值相等，查找成功。否则就在子树中继续查找。如果被查找的值小于根结点的值就选择左子树，大于根结点的值就选择右子树。 　　在理想情况下，每次比较过后，树会被砍掉一半，近乎折半查找。 　　遍历打印可以使用  ，打印出来的结果是从小到大的有序数组。 　　二叉排序树插入 　　二叉排序的插入是建立在二叉排序的查找之上的，原因很简单，添加一个结点到合适的位置，就是通过查找发现合适位置，把结点直接放进去。 　　先来说一下插入函数,中指针p具有非常重要的作用： 若查找的key已经有在树中，则p指向该数据结点。若查找的key没有在树中，则p指向查找路径上最后一个结点，而这里的最后一个结点的位置和key应该被放入的位置存在着简单关系（要么当树空时直接插入作为根结点，  ）。 　　将上面的这些描述转化为代码： 　　借助了二叉排序树的查找，轻松的找到新结点该放在哪个位置，然后把新结点对号入座放进去，就完成了二叉排序树的插入操作。这中间并不会引起二叉树其他部分的结构变化。 　　二叉排序树删除 　　二叉树的删除可不再像二叉树的插入那么容易了，以为删除某个结点以后，会影响到树的其它部分的结构，比如删掉45，然后45的子孙们37、39、53将何处安放？ 　　
　　删除的时候需要考虑一下几种情况：删除的结点只有左子树、删除的结点只有右子树、删除的结点既有左子树又有右子树。 　　考虑前两种情况，直接将左子树或者右子树替换被删除的结点即可。 　　第三种情况，有左子树和右子树的情况。 　　
　　当把二叉排序树进行中序遍历，在序列中可以得到一个删除结点s的直接前驱（或者直接后继），用直接前驱p来替代s。 　　重点来看一下二叉排序树的结点 　　这段大码的内容分析了左右子树均不为空（暂时不考虑删除节点为根节点的）的情况，目的就是在与找到p的  （因为右尽头是待删除结点的前驱结点），这个寻找的步骤就是while循环里面指针s指向自身的右孩子：s=s->rchild. 　　找到右尽头后，就要把右尽头的左子树（因为是右尽头了，所以右尽头只有左子树没有右子树）拼接到q上，完成树的移植工作。 　　ps:替换删除节点有两种方案：左子树的右尽头，或者是，右子树的左尽头。 　　二叉排序树极端情况 　　二叉排序树的优点在于保持了插入删除不用移动素只要修改指针的优点。在查找上，查找次数等于待查找的结点在二叉排序树的层级。 　　来看一种极端情况： 　　
　　这种有序数组，查找最后一个结点99需要经历非常多的层级，其实查找次数还是偏多的。这样的情况下，树是不平衡的，右侧太重。 　　我们为了提高二叉排序树的查找效率，需要把树构建得更为平衡，从而不出现左右偏重的情况。 　　这就引出了AVL树和红黑树这两种平衡二叉树了。 　　##AVL树 　　AVL树的定义 　　平衡二叉树  是一种二叉排序树，其中每一个结点的左子树和右子树的高度差不超过1（小于等于1）。 　　二叉树的平衡因子  等于该结点的左子树深度减去右子树深度的值称为平衡因子。平衡因子只可能是－1，0，1。 　　距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的自述，称为最小不平衡子树。 　　AVL树的实现思路 　　平衡二叉树就是二叉树的构建过程中，每当插入一个结点，看是不是因为树的插入破坏了树的平衡性，若是，则找出最小不平衡树。在保持二叉树特性的前提下，调整最小不平衡子树中各个结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。简记为：  。 　　AVL树的实现过程 　　[左旋与右旋] 　　如上面提到的非平衡二叉树，查找的层级太多，如何减少这些曾经呢？这就要提到左旋和右旋了。先来看张图 　　
　　左旋和右旋的过程我们可以看到平衡因子从（0，1，2）变为（0，0，0），即是一种将非平衡状态转换为平衡状态的过程，这也是AVL树步步调整的核心。 　　再来观察一种复杂的情况 　　
　　新插入一个结点17，使得13的BF（－2）和21的BF（1）符号相反，如果直接左旋，调整后的树就不再是二叉排序树了。因此，正确做法是先在step1中调整符号，然后才能在step2中进行平衡操作。 　　由此，可以总结出平衡操作中非常必要的符号统一操作： 　　最小不平衡子树的BF和它的子树的BF符号相反时，就需要对结点先进行一次旋转使得符号相同，再  才能够完成平衡操作。 　　[左旋代码实现] 　　这部分代码最好在纸上自己画左旋图更容易理解 　　[右旋代码实现] 　　这部分代码最好在纸上自己画右旋图更容易理解 　　AVL树的左旋平衡、右旋平衡 　　AVL树要在旋转前要处理符号统一，这一步骤简称为  和  。 　　[左平衡旋转处理代码] 　　右旋平衡的函数与左旋平衡的函数一样，都是对插入新结点后，判断是否需要做符号统一从而作双旋操作。 　　AVL树的实现算法 　　[主函数] 　　代码内容比较多，核心在于对插入结点时，分配进入左右子树，同时左旋平衡或右旋平衡并调整相应结点的bf。 　　至此，AVL树的内容基本都囊括进去了，我们可以看到AVL树每一步都要平衡，平衡因子不大于1。这种平衡是非常严格的平衡，还有其他形式的平衡，如多路查找树  和   。 　　##红黑树 　　[不同方式的平衡] 　　平衡方式不只有AVL树这种极端平衡的情况，还有其他的拓展平衡方式。 　　多路查找树 　　多路查找树包括B树和拓展的B＋树，和二叉排序树每个结点只能存储一个素，每个结点的孩子数不多于两个的性质不一样的是，  。 　　比如最简单的2-3树就是这样一棵多路查找树：每一个结点都具有两个孩子（称为2结点）或三个孩子（称为3结点）。需要注意的是： 一个2结点要么没有孩子，要么就要有两个孩子，不能只有一个孩子。一个3结点包含一大一小两个素，要么没有孩子，要么就要有三个孩子，不能只有一个或两个孩子。 　　来看一下一个典型的2-3树是什么样子的： 　　
　　2-3树的插入删除可以想象的到：涉及的操作有结点的分裂、合并、补位，这里不做过多讲解。 　　多路查找树的用途 　　2-3只是多路查找树的简单特例，2－3树是3阶的B树，在B树上查找的过程是一个  。 　　现在来说说B树的用途，B树的数据结构就是为内外村的数据交互准备的。 　　外存（如硬盘）是将  。如果要处理的硬盘数据量很大，无法一次全部装入内存中，就要对B树进行调整，是的B树的阶数（或结点的素）与硬盘存储的页面大小相匹配。比如一棵B树的阶为1001（1个结点可以包含1000个素），高度为2，它可以存储超过10亿（1000X1000X1000）个关键字，我们只要让根结点持久的保留在内存中，那么在这棵树上，寻找某一个关键字至多需要两次硬盘的读取。通过这种方式，在有限内存的情况下，每一次磁盘的访问都可以获得最大数量的数据。 　　而B＋树更是在B树的基础上，加上了在叶子结点的新的素组织方式，将叶子结点链接在一起。即   　　 。 　　如图，B+树中的根结点素4、6、9都被保留到叶子结点中，叶子结点也保留指向叶子结点的指针。 　　
　　红黑树的定义 　　红黑树是一棵二叉排序树，它在每个结点上增加了一个存储位来表示结点的颜色，可以是RED或BLACK。通过对任一条从根到叶子的简单路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其它路径长2倍，因此是近乎平衡的。 　　树中的结点包含5个属性：color、key、left、right和p。如果一个结点没有子结点或父结点，则该结点相应指针属性值为NIL。 　　上面提到的这些都是为了让大家有个直观的感受，在具体的操作中，我们肯定是要在插入或者删除结点的过程中时刻保持着红黑树的性质。 　　一棵红黑树是具有如下性质的二叉排序树： 每个结点的颜色只能是红色或黑色的。根结点是黑色的。每个叶子结点（NIL）是黑色的。如果一个结点是红色的，那么它的两个子结点都是黑色的。对每个结点，从该结点到其所有后代叶子简单的简单路径上，均包含相同数目的黑色结点。 　　来看一个最典型的红黑树，以为叶子结点都是黑色的，所以统一出来当成NIL结点。红色结点表示RED，灰色结点表示BLACK。 　　
　　红黑树的旋转 　　为了维护上述红黑树的性质，必须调整结点的颜色和指针结构。 　　指针结构的修改是通过旋转完成的。这是一种能保持二叉排序树性质的局部调整操作。这里的左旋右旋操作和AVL树中的左旋右旋一样，具体代码可回到AVL树部分去查看。 　　
　　红黑树的插入 　　将新结点z插入到树T中，然后将z涂成红色，并调用  （在AVL树中是旋转平衡）来把插入新结点后的树调整为红黑树。 　　RB_INSERT(T,z) 　　RB_INSERT_FIXUP(T,z) 　　
　　根据这个红黑树插入新结点的情况，我们来过一下代码流程。 　　(a)插入结点z。由于z和它的副结点z.p都是红色的，违反了性质4（红结点的后代要是黑结点）。由于z的叔结点y也是红色的，适用于case1。结点被重新着色，并且指针z沿树上升，如(b)所示。再一次z及其父结点都是红色的，但z的叔结点y是黑色的。因为z是z.p的右孩子，可以应用case2。在执行一次左旋后，所得结果树为（c）。现在，z是其父结点的左孩子，可以应用case3。重新着色并执行一次右旋后得（d）中的树，它是一棵红黑树。 　　红黑树的删除 　　从一棵红黑树中删除结点的过程需要调用子过程RB_TRANSPLANT。 　　RB_TRANSPLANT(T,u,v) 　　红黑树的删除和普通的二叉树删除一样，只是需要对结点的颜色添加判断，需要用更多的代码来记录结点y的踪迹，y有可能导致红黑性质的破坏。当想要删除结点z，且此事z的子结点少于2个时，z从树中删除，并让y成为z。当z有两个子结点时，y应该是z的后继，并且y将移至树中的z位置。在结点被移除或者在树中移动之前，必须记住y的颜色，并且纪录结点x的踪迹，将x移至树中y的原来位置，因为结点x也可能引起红黑性质的破坏。删除结点z之后，RB_DELETE调用一个辅助过程RB_DELETE_FIXUP，该过程通过改变颜色和旋转来恢复红黑性质。 　　RB_DELETE(T,z) 　　上面的代码是跟随结点y的移动追踪过程。如果结点y是黑色的，红黑树性质遭到破坏，需要调用RB_DELETE_FIXUP进行补救。 　　RB_DELETE_FIXUP(T,x) 　　while循环的目标是将额外的黑色沿树上移，直到： x指向红黑结点，将x着色为黑色x指向根结点，可以简单的“移除”额外的黑色执行适当的旋转和重新着色，退出循环 　　分析下面几个状态：红色结点表示RED，灰色结点表示BLACK，棕红色结点表示RED或BLACK，用c和c’表示。 　　
　　(a)通过结点B和D颜色交换和执行左旋，可将case 1转化为case 2； 　　(b)在case 2中，将结点D着为红色，并将x设为指向结点B后，由指针x所表示的额外黑色沿树上升。如果通过case 1进入case 2，则while循环结束，因为新的结点x是红黑的，因此其color属性c是RED. 　　©通过结点C和D交换颜色并执行一次右旋，可以将case 3转换成case 4。 　　(d)case 4中，通过改变某些结点的颜色并执行一次左旋，可以将由x表示的额外黑色去掉，终止循环。 　　这是最正宗的红黑树理解方式，还有一种方式是通过2－3树分裂操作替换成颜色操作，具体请看博文查找（一）史上最简单清晰的红黑树讲解 　　##总结 　　作为平衡二叉排序树众多的实现之一，红黑树特别的  这一个约束条件保持树的平衡。通过旋转可以降低树的高度并转换颜色。 　　红黑树的插入和删除操作是比较难理解的：它们都是建立在红黑树是平衡的情况下，加入一个结点或者删除一个结点，影响了平衡，就需要向兄弟结点、父结点、叔结点进行借调和颜色互换，这一操作是通过旋转实现的。但是换完以后，是否还是平衡的呢，这是不一定的，需要从被借调结点出发开始向上调整，直到整个树都是平衡的。修复过程中，插入具体分3种情况，删除分4中情况。 　　红黑树和AVL树都是从树的平衡性出发，找到合适的平衡方式，一个通过颜色标识限定，一个通过树高差限定，使树都处于平衡状态，提高了算法的实用性和效率。 　　参考资料 算法导论（第三版）大话数据结构数据结构（严蔚敏）红黑树深入剖析及Java实现（美团点评技术团队） 　　附录 　　红黑树的java实现： 　　全栈，遇见更好的自己。