heap、2-3-4树、红黑树、hash算法介绍

《heap、2-3-4树、红黑树、hash算法介绍》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Heap、2-3-4树、红黑树、hash算法介绍中国人寿梁如见liangrujian@gmail.com201305排序和查找排序算法数组排序：quick、merge、heap树排序：AVL、B(2-3-4)、red-blackHash排序动态、静态分类静态：quick、merge动态：heap、树排序、hashOracle是用hash、B-tree堆出来的heap性质：完全二叉树最大堆中每个节点都比儿节点大，根节点最大。最小堆则是每个节点比儿节点小。适合优先队列：输出优先级最大或最小的不采用链表结构，采用数组实现，

2、算法简单堆上下有序，左右无序堆排序本身不保存排序好的结果，仍需要用数组来存放结果数据。所以，无法在堆上进行查找，也无法删除指定关键字用java实现时，可以动态扩大规模。如果用c实现，可以采取申请扩大一倍的数组，然后迁移数据。heap插入：放在最后，然后向上比较、交换直到已符合堆性质摘取：摘取root，把最后一个数放入root，然后向下比较、交换直到已符合堆性质2-3-4tree性质：234指一个节点可能含有的子节点的个数每个节点存放1-3个值，2-4个指针只能在叶子上插入中间结点也存放数据全树有序，叶子等高可通过先序

3、遍历输出排序结果可实现优先队列，查找最优节点并删除2-3-4tree插入，必须在叶子上进行：从根向下找位置，遇到3值即拆为2节点（腾出空位），增加父亲值（父亲原先值非3有空缺）删除：删非页节点，则继续找到叶子为止，交换上来；如删页节点，则找到就行。如果找的过程中碰到1值则进行转换扩值，根例外（根会被叶子搞定）1、如果兄弟有多值，通过父亲交换到这边，扩自己2、如果兄弟也1值，从父亲拉下一个，变为3值。父亲应该非1值。parent如果是根，且为1值，则变短。red-blacktree性质：1)、Anodeiseither

4、redorblack.每个结点要么是红的，要么是黑的。2)、Therootisblack.根结点是黑的。3)、Allleaves(NIL)areblack.叶节点是黑的。4)、Bothchildrenofeveryrednodeareblack.如果一个结点是红的，那么它的子节点必须是黑的。5)、Everysimplepathfromagivennodetoanyofitsdescendantleavescontainsthesamenumberofblacknodes.从任何给定节点到叶节点的每条路径都包含相同数目

5、的黑结点。只能在叶子上插入红节点中间结点也存放数据全树有序可通过先序遍历输出排序结果可实现优先队列，查找最优节点并删除红黑树从根到叶子，如果全为黑最短，黑红相间最长，长度最多相差一倍，基本平衡。red-blacktree插入：只用红节点插入到叶子1)、如果是根，改为黑即可，否则去22)、如果父亲是黑，OK，否则去33)、如果叔叔也是红，则如下图，改变颜色，对G节点回1；否则表示叔叔为黑色，去4下面4和5仅显示P为G左儿子的情况，如果P为G右儿子则4为右旋5为左旋。4)、如果N为P的右儿子，左旋，去5，否则直接去55)

6、、右旋，OKred-blacktree删除，首先是把左邻（最接近被删数）或右邻交换上来（交换不影响红黑树性质），然后把被交换的节点删除。被交换的节点要么是叶子，要么只有一个儿子。删除问题演变成删除一个最多只有一个儿节点C的节点M的问题。几种形态：（2*3，M红或黑，C无、红或黑，红红不符树性质）1、M红，无C，直接删除M即可2、M红，C黑，实际上2和1是一样的，该C只能是nil，否则长度不等3、M黑，无C4、M黑，C红，C下不能再有儿子，该情况简单，删除黑节点，把子节点改为黑色即可5、M黑，C黑，实际上5和3是一样的

7、，该C只能是nil，否则长度不等问题继续演变为删除黑色叶子节点的问题如果是根，直接删除，后面不讨论red-blacktree删除续1一棵这样的树：N为删后高度减1的子树（初始时即为nil节点），P为父亲，S为兄弟（肯定有，因N原先为黑，S及其儿子必须有一黑）如何保持S这边高度不变，但N这边高度补回1初始状态下，删除N后则只剩P、S及S的儿、孙节点。初始状态（2*2*?*?，P红或黑，S红或黑，S的儿子？S的孙子？）case1、P红S黑，该情况比较简单，因为N原高度为1，决定了S的儿子空或红，S没有孙节点删除N后只有2

8、-4个节点，比较容易安排，2则父为黑，3-4则父为红case2、P黑S红，S有两黑儿子，S可能有红孙子可以转换为case1case3、P黑S黑，S可能有红儿子删除N后的节点数量有2-4个节点，3或4个节点两层黑好安排，2个节点时必须用到爷爷节点了，直接把S置为红色，然后把P（黑）作为N节点针对刚才三种情况进行转化（刚才是N变短，现在是P变短了）