造价通

反馈
取消

热门搜词

造价通

取消 发送 反馈意见

左偏树基本性质

2018/06/19107 作者:佚名
导读: [性质1] 节点的键值小于或等于它的左右子节点的键值。即key(i)≤key(parent(i)) 这条性质又叫堆性质。符合该性质的树是堆有序的(Heap-Ordered)。有了性质1,我们可以知道左偏树的根节点是整棵树的最小节点,于是我们可以在O(1) 的时间内完成取最小节点操作。[性质2] 节点的左子节点的距离不小于右子节点的距离。即dist(left(i))≥dist(right(i)

[性质1] 节点的键值小于或等于它的左右子节点的键值。

即key(i)≤key(parent(i)) 这条性质又叫堆性质。符合该性质的树是堆有序的(Heap-Ordered)。有了性质1,我们可以知道左偏树的根节点是整棵树的最小节点,于是我们可以在O(1) 的时间内完成取最小节点操作。

[性质2] 节点的左子节点的距离不小于右子节点的距离。

即dist(left(i))≥dist(right(i)) 这条性质称为左偏性质。性质2是为了使我们可以以更小的代价在优先队列的其它两个基本操作(插入节点、删除最小节点)进行后维持堆性质。在后面我们就会看到它的作用。

这两条性质是对每一个节点而言的,因此可以简单地从中得出,左偏树的左右子树都是左偏树。

由这两条性质,我们可以得出左偏树的定义:左偏树是具有左偏性质的堆有序二叉树。

我们知道,一个节点必须经由它的子节点才能到达外节点。由于性质2,一个节点的距离实际上就是这个节点一直沿它的右边到达一个外节点所经过的边数,也就是说,我们有

[性质3] 节点的距离等于它的右子节点的距离加1。

即dist( i ) = dist( right( i ) ) + 1 外节点的距离为0,由于性质2,它的右子节点必为空节点。为了满足性质3,故前面规定空节点的距离为-1。

我们的印象中,平衡树是具有非常小的深度的,这也意味着到达任何一个节点所经过的边数很少。左偏树并不是为了快速访问所有的节点而设计的,它的目的是快速访问最小节点以及在对树修改后快速的恢复堆性质。从图中我们可以看到它并不平衡,由于性质2的缘故,它的结构偏向左侧,不过距离的概念和树的深度并不同,左偏树并不意味着左子树的节点数或是深度一定大于右子树。

*文章为作者独立观点,不代表造价通立场,除来源是“造价通”外。
关注微信公众号造价通(zjtcn_Largedata),获取建设行业第一手资讯

热门推荐

相关阅读