张北网站制作【张北网站优化】张北建网站、张北微信公众号运营、张北网页设计、张北微信小程序商城

张北网站制作【张北网站优化】张北建网站、张北微信公众号运营、张北网页设计、张北微信小程序商城

河北省张家口市张北县地处河北省西北部，内蒙古高原南缘的坝上地区，境域东西109公里，南北67公里，东南部与崇礼区交界，桦皮岭为全县最高点，海拔2128米；北、中部地势平坦，向西北渐低，安固里淖为最低点，海拔1300米。全县总面积4185平方公里，辖18个乡镇、366个行政村、1167个自然村，总人口37.2万人。居民以汉族为主，占总人口的98%，还有蒙古族、回族、满族等。张北县是离京津地区最近的高原地区，夏天气候凉爽是避暑胜地。

张北县被列为第一批国家新型城镇化综合试点地区。 [1]  2019年11月，入选第二批节水型社会建设达标县（区）名单。 [2]  2020年2月29日，退出贫困县序列，正式脱贫“摘帽”。 [3]  2020年12月，入选河北省数字乡村试点地区名单。

5.8.3　一般情况

图5-42所示情况和图5-43所示情况哪个更普遍？其实，两者在实践中都不常见，不过图5-43中的完全树提供的词典操作效率与一般情况的效率是近似的。也就是说，平均情况下，查找、插入和删除花费的都是对数时间。

要证明一般二叉树可以提供对数时间的词典操作是很难的。证明的要点在于，从这样的树的根节点到某个随机节点的路径长度的期望值是O(logn)。本节习题中将给出这一期望值的递推等式。

不过，我们可以直观地看出这为什么应该是正确的运行时间，理由如下。二叉树的根节点会将除它自己之外的节点分为两棵子树。在最平均的分布中，一棵有k 个节点的树将会有两棵各有约k/2个节点的子树。如果根节点元素刚好是在一列有序元素的正中位置，就会形成这种情况。而在最坏的分布中，根节点元素是词典中的第一个或最后一个元素，这样就会使一棵子树为空，而另一棵子树中有k-1个元素。

平均而言，可以预期根节点是在已排序表正中和极端之间，而且可以预期约有k/4个节点在较小的子树中，另外的3k/4个节点在较大子树中。假设在向下探索树的过程中，每次递归调用时始终移动到较大子树的根节点，而且类似的假设适用于每层元素的分布。在第一层，较大子树会按照1:3的比例划分，在第二层留下共有(3/4)(3k/4)，即9k/16个节点的最大子树。因此，可以预见在第d 层的最大子树约有(3/4)dk 个节点。

如果d 变得足够大，那么(3/4)dk 的量会接近1。而且可以预见，在这一层，最大子树将是由一个叶子节点组成的。因此要问，d 为什么值可以使(3/4)dk≤1？如果取以2为底的对数，就得到

d log2(3/4)+log2k≤log21　　　　　　(5.1)

现有log21=0，且log2(3/4)是一个负常数，约为-0.4。因此可将(5.1)式重新写为log2k≤0.4d，或a≥(log2k )/0.4=2.5log2k。

换句话说，在深度约为节点数以2为底的对数的2.5倍的位置（或是在更高的层数），就有望全是叶子节点了。这一论述证实了（但并未证明）一般二叉查找树的高度与该树节点数的对数成正比这一陈述。

5.8.4　习题

1. 如果树T 高度为h，而且分支系数为b，那么树T 最多可以有多少个节点，最少有多少个节点？

2. ** 进行如下实验，从n 个不同值的n !种顺序中任选一种，并按照这一顺序将这些值插入一棵空的二叉查找树中。设P(n)是实验后这n 个值中某个特定值v 所在节点的深度的期望值。

(a) 证明，对n≥2，

(b) 证明P(n)是O(logn)。

5.9　优先级队列和偏序树

到目前为止，我们只看到一种抽象数据类型——词典，以及它的一种实现——二叉查找树。本节将研究另一种抽象数据类型以及它最有效率的一种实现。这种叫作优先级队列的抽象数据类型是各自有优先级与之关联的一组元素。例如，这些元素可以是一些记录，而优先级则可能是记录中某个字段的值。与优先级队列ADT有关的两种操作如下：

1. 向集合中插入一个元素（insert）；

2. 从集合中找出优先级最高的元素并将其删除（这种组合操作称为deletemax），被删除的元素由该函数返回。

示例 5.26

分时操作系统从多个来源接受服务请求，而这些作业的优先级可能不尽相同。例如，优先级最高的可能是系统进程，这些进程中可能包含监控传入数据（比如在终端的按键动作生成的信号，或是局域网上数据包的到达所生成的信号）的“守护进程”。接着可能是用户进程，那些由普通用户发出的指令。再下来就可能是某些特定的后台作业，比如向磁带备份数据，或是用户已指定以低优先级运行的长计算。

作业可以表示为记录，这种记录由对应作业的整数ID和对应作业优先级的整数组成。也就是说，可以使用如下结构体

struct ETYPE {
    int jobID;
    int priority;};复制代码

表示优先级队列中的元素。在初始化新的作业时，它会得到一个ID和一个优先级。然后对等待服务的作业构成的优先级队列执行这一元素的插入操作。当处理器资源可用时，系统就会来到优先级队列，并执行deletemax操作。由该操作返回的元素就是等待服务的作业中优先级最高的作业，而该作业正是接下来要执行的。

示例 5.27

我们可以使用优先级队列ADT实现排序算法。假设有一列整数a1、a2、…、an 要排序，可以将这些整数放入一个优先级队列，分别使用这些元素的值作为各自的优先级。如果随后执行deletemax操作n 次，这些整数就会按照从大到小的顺序依次被选出来。5.10节还会更详细地讨论这种称为堆排序的算法。

5.9.1　偏序树

实现优先级队列的一种有效方式是使用偏序树（Partially Ordered Tree，POT），这是一种具有如下属性的带标号二叉树。

1. 节点的标号是具有“优先级”的元素，该优先级可以是元素的值，也可以是元素某个组成部分的值。

2. 存储在节点中的元素的优先级，不小于存储在其子节点中的元素的优先级。

属性(2)说明，任何子树根节点处的元素总是该子树中最大的元素。我们将属性(2)称为偏序树属性，或POT属性。

示例 5.28

图5-44展示了一棵具有10个元素的偏序树。在这里以及本节的其他部分中，我们都将用元素的优先级来表示它们，就像元素和它们的优先级是一回事那样。请注意，相等的元素可能出现在树中的不同层级。要说明偏序树属性在根节点得到满足，请注意，根节点处的元素18不小于其子节点处的元素18和16。同样，可以验证在该树的每个内部节点处偏序树属性都成立。因此，图5-44是一棵偏序树。

偏序树为优先级队列提供了一种实用的抽象实现。简单地说，要执行deletemax操作，就要找到根节点，它肯定是最大的，并用底层的最右节点代替它。不过，这样做时，偏序树属性可能被破坏，因此必须还原偏序树属性，要让新放置在根节点处的元素“向下沉”，直到它到达合适的层次，使得它小于它的父节点，并且不小于它的子节点。要执行插入操作，就要在底层尽可能左的位置增加一个新的叶子节点，如果底层没有空位置，就要新添加一个层级，并将该节点放在新一层的左端。这样也可能对偏序树属性造成破坏，如果造成破坏，就要让新元素“向上冒”，直到它找到合适的位置。

图 5-44　有10个节点的偏序树

张北网站制作【张北网站优化】张北建网站、张北微信公众号运营、张北网页设计、张北微信小程序商城