数据结构课件-7-树堆.pptx

数据结构计算机领域本科教育教学改革试点工作计划（“101计划”）研究成果俞勇、张铭、陈越、韩文弢上海交通大学、北京大学、浙江大学、清华大学101

12.7树堆第12章高级查找戴波电子科技大学

12.7.1树堆的定义12.7.2树堆的旋转12.7.3树堆的插入12.7.4树堆的删除12.7.5树堆小结12.7.6树堆作业

12.7.1树堆的定义12.7.1树堆的定义数据结构树堆=二叉查找树+堆树堆：给二叉查找树的每个关键字额外增加了一个随机优先级，让关键字满足二叉查找树的结构，让优先级满足二叉堆的性质。这样从关键字角度是一颗二叉查找树，从优先级角度是一个二叉堆，从而成为一棵平衡查找树。(a,b)表示该结点的a是关键字，b是优先级

12.7.1树堆的定义12.7.1树堆的定义数据结构树堆并不是一个规则形态的二叉查找树，更不是二叉堆这样的完全二叉树，也不符合AVL树或者红黑树这些平衡树的要求，是一颗近似平衡的二叉查找树。如果生成树堆的时候的优先级的随机性出现某种顺序特征，可能使得生成的树堆的高度比较高，形态接近单分支二叉树。

12.7.2树堆的旋转12.7.2树堆的旋转数据结构如果进行二叉查找树的插入或者删除操作后，使得插入结点所在子树的根的优先级比插入结点的优先级低，则需要旋转，使得子树根的优先级比孩子优先级更高，其中子树在根的左侧，需要右旋；子树在根的右侧，需要左旋。树堆的旋转

12.7.2树堆的旋转12.7.2树堆的旋转数据结构树堆三层调整(1):zig-zig型旋转zig-zig型

12.7.2树堆的旋转12.7.2树堆的旋转数据结构树堆三层调整(2):zig-zag型旋转zig-zag型

12.7.2树堆的旋转12.7.2树堆的旋转数据结构树堆的旋转让查找的结点上升到根，使得下次再次查找这个结点可以一步到位，有哪些信誉好的足球投注网站效率非常高。但是，也注意到，如下图访问结点19，从左图通过旋转将19调整到根，如右图所示。有的结点比如结点3和结点5，到根距离由3变成4，访问距离反而增加。但仅有少数位置距离根较近的结点会增加最多2层深度，而有哪些信誉好的足球投注网站路径上大多数结点会减少约一半的深度。树堆旋转调整小结

12.7.3树堆的插入12.7.3树堆的插入数据结构

12.7.3树堆的插入12.7.3树堆的插入数据结构例子：有8个关键字为12,6,7,14,1,9,31,8的数据，随机分配优先级为44,31,6,12,9,3,71,53(设数字越小，优先级越高),则按照树堆的插入结点规则，依次插入结点建立树堆。

12.7.3树堆的插入12.7.3树堆的插入数据结构例子：有8个关键字为12,6,7,14,1,9,31,8的数据，随机分配优先级为44,31,6,12,9,3,71,53(设数字越小，优先级越高),则按照树堆的插入结点规则，依次插入结点建立树堆。答案

12.7.4树堆的删除12.7.4树堆的删除数据结构树堆删除结点后从父结点到根结点回溯调整思维导图

12.7.4树堆的删除12.7.4树堆的删除数据结构例：画出下图的树堆中删除8，1和9后的树堆。

12.7.4树堆的删除12.7.4树堆的删除数据结构答案例：画出下图的树堆中删除8，1和9后的树堆。

12.7.5树堆小结12.7.5树堆小结数据结构树堆是基于堆的二叉查找树，它既不是一个规则形态的二叉查找树，更不是二叉堆这样的完全二叉树，也不符合AVL树或者红黑树这些平衡树的要求，是一棵近似平衡的二叉查找树。树堆的插入删除简单直观，速度也不错，但是这里的堆是随机生成的，所以不能保证每一个操作都在一定的时限内完成。

12.7.6树堆作业12.7.6树堆作业数据结构思考：树堆保持堆性质的随机数如果不随机，可能会出现什么情况？最坏情况如何？已知10个数据31,87,65,12,4,77,9,10,29,91,用随机数算法生成的10个随机数是44,6,88,12,9,77,18,6,9,54,请绘制树堆(数字越大优先级越高)。再绘制删除关键字65之后的树堆。

101