数据结构学习笔记-排序/队/栈/链/堆/查找树/红黑树-创新互联

排序:

信州网站制作公司哪家好,找创新互联!从网页设计、网站建设、微信开发、APP开发、成都响应式网站建设公司等网站项目制作,到程序开发,运营维护。创新互联2013年至今到现在10年的时间,我们拥有了丰富的建站经验和运维经验,来保证我们的工作的顺利进行。专注于网站建设就选创新互联。

插入排序:每次从剩余数据中选取一个最小的,插入已经排序完成的序列中

合并排序:将数据分成左右两组分别排序,然后合并,对每组数据的排序递归处理。

冒泡排序:重复交换两个相邻元素,从a[1]开始向a[0]方向冒泡,然后a[2]...当a[i]无法继续往前挤的时候说明前面的更小了,而且越往前越小(挤得越往前)

堆排序:构造大堆,每次取走根结点(自然是大的),再调用MAX-HEAPIFY算法(见后文的堆)恢复大堆的性质,重复取走根结点

快速排序(对A[r]-A[n]进行排序):

1.序列中选取一个元素作为主元并与A[n]交换,或者直接把A[n]作为主元

2.序列划分为左中右三部分,主元在中间。left中任何元素都<=主元,right中任何元素都>主元。

具体划分方式为:将序列的A[r]-A[n-1]部分划分为三个依次相连的区域:left,right,未划分,在未划分的区域遍历,如果某元素比主元大不作处理,如果比主元小,则将此元素与right区的第一个元素交换,并将新的right区的第一个元素划给left区。遍历完毕够将A[n]与right区的第一个元素交换。

([left][right][未划分][主元],也就是把未划分区域的元素不断移动到left区或保持不动变成right区的一部分)

3.划分好的左右两部分分别排序,这样递归下去,直到某一部分的元素数量少于等于三个可以直接进行排序。

队栈链堆:

:先进后出的结构,push时栈顶升高,元素放入新栈顶;pop时取出栈顶元素,栈顶降低。

(循环)队列:先进先出的结构,top指向队首的位置,tail指向新元素要加入的位置(也就是队尾的后一个位置)。

enqueue时元素放入tail,tail循环后移;dequeue时取出top元素,top循环后移。

队列的容量比数组容量少一。(否则当top和tail相等时无法判断队列是空还是满)

链表:前一个元素指向后一个元素(后一个也可能指向前一个),经典操作插入,删除,搜索,可以在头元素之前尾元素之后加入哨兵元素以简化边界判断。

大堆(最小堆同理):一颗完全二叉树,而且每个结点都是所在子树中的大结点

大堆MAX-HEAPIFY算法:当大堆的根结点的值发生了变化,可能不再是整个树中大的结点了,使用此算法可以维持大堆的性质(每次和左右结点中大的那个交换,递归下去,最终移动到合适的位置)

大堆建堆(自下而上MAX-HEAPIFY):从第max/2个结点(最后一个元素是此元素的孩子结点,此元素再往后的点都没孩子,自然都是大堆),从此结点依次往前调用MAX-HEAPIFY算法,可以保证从下到上的每个子树都是大堆,那么整体也是大堆。

用大堆实现大优先级队列:

1.取大权重元素:A.First

2.移除大权重元素:取出A.First,然后把A.Last移动到A.First并对新的A.First执行向下递归的MAX-HEAPIFY操作以维持大堆性质。

3.插入元素:在最后面新增元素(成为新的A.Last),对A.Last向着父结点方向递归交换上升到适合的位置。

4.增加A[i]的权重:A[I]向着父结点方向递归交换上升到适合的位置。

二叉查找树:

每个结点的KEY,都比其左子树的任意结点的KEY大,比其右子树的任意结点的KEY小。因此通过中序遍历可以从小到大顺序输出(中序遍历:先遍历左子树,再遍历父结点,最后遍历右子树)

查找:从父到子从上到下,想找更小的数往左拐(如果要找的数小于根结点,则一定在左子树中)。直到匹配,或者找到了NIL。

大KEY值元素:顺着右子树的右子树的右子树……找到底,因为右子树总是比较大。

最小KEY值元素:同理,顺着左子树找到底。

后继(中序遍历中下一个遍历到的结点):

1.如果结点有右子树,则后继是右子树RT的左下角(左中右,下一个遍历到的一定是RT的左子树的左子树的左子树的左子树。。。)

2.如果结点(设为c)不含有右子树,则一路向上找祖先,直到找到某个结点s,使得c在这个结点的左子树中(也就是说s的左孩子也是c的祖先,或者就是c),此时c的左子树刚遍历完毕即将遍历s,自然s就是c的后继了

前驱(和后继问题对称)

1.如果含有左子树,则一定是左子树的大结点

2.如果没有左子树,则F所在的某颗右子树马上要被遍历了,找前驱顺着父节点往上找就是(直到找到某个结点S,使得S的右孩子也是F的祖先)

插入

像查找一样从上到下根据和父结点大小的对比,选择左转还是右转,直到落到合适的空位上。

删除:

1.如果F没有孩子结点,直接删,什么都不影响

2.如果F有一个孩子结点,删除该结点,并且将它的孩子节点(C)连接到父结点(S)上

(这样并不会改变S的左子树所有结点比S小,右子树所有结点比S大的局面)

3.如果F有两个孩子结点,则把F的后继删除,然后用后继替换F(后继是右子树左下角,最多只有一个右孩子,用1或2的方式删了无影响;由于F和其后继大小相邻,替换后中序遍历依然从小到大,说明没有破坏查找树的性质)

红黑树:

根节点和最底下无数据的叶子结点(Nil结点)为黑色,任意父子结点不能同时为红(这样可以保证每个路径红的数量不大于黑),任意路径的黑结点数量相同(配合前面的性质,保证了最长的路径最多不超过最短路径的二倍,一种平衡策略)。插入删除操作都是 0(lnN), 且最多旋转三次

旋转:

分左旋和右旋。旋转改变某个结点和它的左孩子或右孩子的关系。因为改变上下的同时也改变了左右,因此不影响左<中<右的查找树性质。一定的旋转和变色操作可以恢复红黑树的性质。

左旋:结点F绕着右孩子R逆时针旋转90度,结果F变成了R的左孩子,R原来的左孩子分给了F的右边,F原来的父结点被R连上了。左旋导致了右孩子的右侧分支变短了。

右旋:结点F绕着左孩子L顺时针旋转90度,指针变更和左旋同理,导致左孩子的左分支变短了。

红黑树的插入:(插入的位置如同普通查找树,每次只插入红的,这样只破坏红色不相邻的性质):

如果红黑树是空的:放入根结点的位置,变成黑色

如果父结点是黑的。不破坏性质。

之后以新结点的父结点是爷爷结点的左孩子为例;右孩子的情形与此对称:

1.父结点和叔父结点都是红的:

让父结点和叔父结点变黑,祖父变红,这样解决了父子同红的问题。如果恰好曾祖父为红,则递归向上解决问题。

2.父红,叔父黑,新结点是父结点的右孩子。则左旋父结点,这样父子左右关系颠倒,变成情况3

3.父红,叔父黑,新节点是父结点的左孩子。则右旋祖父结点(按照预设,父结点是祖父结点的左孩子)。此时父子双红的左分支高度降低,原来的父节点位置变低,跑到右侧。此时再交换原祖父结点和父结点的颜色,就左右均衡了。

删除

如果红黑树只有一个结点,直接删除;

如果删除的结点有两个孩子,则实际删除的是其后继,变成没有或者一个孩子的情况。

如果有一个孩子,则必定是黑结点红孩子,直接用孩子结点替代父结点并且把颜色变黑即可。

如果结点没有孩子且结点为红色,直接删除即可。

因此唯一需要讨论的就是要删除的结点为黑色而且没有孩子结点。

包含多种情况,使用变色旋转等技巧可以使树平衡。看了好久好久也没整理下来,不继续浪费时间了

另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


网站栏目:数据结构学习笔记-排序/队/栈/链/堆/查找树/红黑树-创新互联
转载来于:http://pwwzsj.com/article/desshs.html