100字范文,内容丰富有趣,生活中的好帮手!
100字范文 > 算法导论读书笔记(20)van Emde Boas树

算法导论读书笔记(20)van Emde Boas树

时间:2023-11-20 03:28:56

相关推荐

算法导论读书笔记(20)van Emde Boas树

第五部分 高级数据结构

第20章 van Emde Boas树

van Emde Boas树支持优先队列操作以及一些其他操作,每个操作最坏情况运行时间为O(lglgn)。而这种数据结构限制关键字必须为0~n-1的整数且无重复。

1. 基本方法

直接寻址

维护一个u位的数组A[0..u-1],以存储一个值来自全域{0, 1, 2, …, u-1}的动态集合。虽然利用位向量方法可以使insert, delete和member操作的运行时间显O(1),然而其余操作minimum, maximum, successor和predecessor在最坏情况下仍需Θ(u)的运行时间,这是因为操作需要扫描Θ(u)个元素

叠加的二叉树结构

在位向量上方叠加的一棵位二叉树的方法,来缩短对位向量的长扫描。位向量的全部元素组成了二叉树的叶子,并且每个内部结点为1当且仅当其子树中任一个叶结点包含1。换句话说,内部结点中存储的位就是其两个孩子的逻辑或。

使用这种树结构和未经修饰的位向量,具有最坏情况运行时间为Θ(u)的操作如下:

1. 查找集合中的最小值,从树根开始,箭头朝下指向叶结点,总是走最左边包含1的结点

2. 查找集合中的最大值,从树根开始,箭头朝下指向叶结点,总是走最右边包含1的结点

3. 查找x的后继,从x所在的叶结点开始,箭头朝上指向树根,直到从左侧进入一个结点,其右孩子结点z为1。然后从结点z出发箭头向下,始终走最左边包含1的结点(即查找以z为根的子树中的最小值)。

4. 查找x的前驱,从x所在的叶结点开始,箭头朝上指向树根,直到从右侧进入一个结点,其左孩子结点z为1。然后从结点z出发箭头向下,始终走最右边包含1的结点(即查找以z为根的子树中的最大值)。

叠加的一棵高度恒定的树

假设全域的大小为u = 2 ^ 2k,这里k为某个整数,那么sqrt(u)是一个整数。我们叠加一棵度为sqrt(u)的树,来代替位向量上方叠加的二叉树。结果树的高度总是为2。

1. 查找最小(最大)值,在summary数组中查找最左(最右)包含1的项,如summary[i],然后在第i个簇内顺序查找最左(最右)的1

2. 查找x的后继(前驱),先在x的簇中向右(左)查找。如果发现1,则返回这个位置作为结果否则令i =⌊ x / sqrt(u)⌋,然后从下标i开始在summary数组中向右(左)查找找到第一个包含1的位置得到这个簇的下标。再在该簇中查找最左(最右)的1,这个位置的元素就是后继(前驱)

3.删除值x,设i =⌊ x / sqrt(u)⌋。将A[x]置为0,然后置summary[i]为第i个簇中所有位的逻辑或

2.递归结构

一个给定的值x在簇编号⌊ x / sqrt(u)⌋中。如果把x看做lgu位的二进制整数,那么簇编号⌊ x / sqrt(u)⌋由x中最高(lgu)/2位决定。在x簇中,x出现在位置x mod sqrt(u)中,是由x中最低(lgu)/2位决定。因此定义以下函数:

1.high(x) = ⌊ x / sqrt(u)⌋

2.low(x) = x mod sqrt(u)

3. index(x, y) = x sqrt(u) + y

1. 原型van Emde Boas结构

对于全域{0, 1, 2, …, u-1},定义原型van Emde Boas结构,记作proto-vEB(u)。每个proto-vEB(u)的结构都包含一个给定全域大小的属性u。另外,它包含以下特征:

1. 如果u = 2,那么它是基础大小,只包含一个两个位的数组A[0..1]。

2. 否则,对某个整数k >= 1,u = 2 ^ (2^k),于是有u >= 4。除了全域大小u之外,prote-vEB(u)还具有以下属性:a. 一个名为summary的指针,指向一个prote-vEB(sqrt(u))结构。b. 一个数组cluster[1..sqrt(u)-1],存储sqrt(u)个指针,每个指针都指向一个prote-vEB(sqrt(u))结构

2.原型van Emde Boas结构上的操作

判断一个值是否在集合中

Prote-vEB-Member(V, x)if V.u == 2return V.A[x]elseProte-vEB-Member(V.cluster[high(x)], low(x))

查找最小元素

Proto-vEB-Minimum(V)if V.u == 2if V.A[0] == 1return 0else if V.A[1] == 1return 1elsemin-cluster = Proto-vEB-Minimum(V.summary)if min-cluster == NILreturn NILelseoffset = min-cluster = Proto-vEB-Minimum(V.cluster[min-cluster])return index(min-cluster, offset)

查找后继

Proto-vEB-Successor(V, x)if V.u == 2if x == 0 and V.A[1] == 1return 1elsereturn NILelseoffset = Proto-vEB-Successor(V.cluster[high(x)], low(x))if offset != NILreturn index(high(x), offset)elsesucc-cluster = Proto-vEB-Successor(V.summary, high(x))if succ-cluster == NILreturn NILelseoffset = Proto-vEB-Minimum(V.cluster[succ-cluster])return index(succ-cluster, offset)

插入元素

Proto-vEB-Insert(V, x)if V.u == 2V.A[x] = 1elseProto-vEB-Insert(V.cluster[high(x)], x)Proto-vEB-Insert(V.summary, high(x))

3.van Emde Boas树及其操作

proto-vEB结构已接近运行时间为O(lglgu)的目标,其缺点是大多数操作需要进行多次递归。

重定义:

1. high(x) = ⌊ x / ⌊sqrt(u)⌋ ⌋

2. low(x) = x mod ⌊sqrt(u)⌋

3. index(x, y) = x * ⌊sqrt(u)⌋ + y

1.van Emde Boas树

一棵vEB树含有proto-vEB结构中没有的两个属性:

1.min存储vEB树中的最小元素

2.max存储vEB树中的最大元素

存储在min中的元素并不出现在任何递归的vEB(⌊sqrt(u)⌋)树中,这些树是由cluster数组指向它们的。

存储在min中的元素不出现在任何簇中,而存储在max中的元素却不是这样

在一棵不包含任何元素的vEB树中,不管全域的大小u如何,min和max均为NIL

min和max属性是减少vEB树上这些操作的递归调用次数的关键,这两个属性有4个方面的作用:

1.minimum和maximum操作不需要递归,因为可以直接返回min和max的值

2.successor操作可以避免一个用于判断值x的后继是否位于high(x)中的递归调用。这是因为x的后继位于x簇中,当且仅当x严格小于x簇的max。对于prodecessor和min情况,可以对照得到。

3.通过min和max的值,可以在常数时间内告知一棵vEB树是否为空、仅含一个元素或两个以上元素。如何min和max都为NIL,那么vEB树为空,如何min和max都不为NIL但彼此相等,那么vEB树仅含一个元素。如果min和max***都不为NIL且不等,那么vEB树包含两个或两个以上元素*。

4. 如果一棵vEB树为空,那么可以仅更新它的min和max值为实现插入一个元素

2.van Emde Boas树的操作

查找最小元素和最大元素

vEB-Tree-Minimum(V)return V.min

vEB-Tree-Maximum(V)return V.max

判断一个值是否在集合中

vEB-Tree-Member(V, x)if x == V.min or x == V.maxreturn trueelse if V.u == 2return falseelsereturn vEB-Tree-Member(V.cluster[high(x)], low(x))

查找后继和前驱

vEB-Tree-Successor(V, x)if V.u == 2if x == 0 and V.max == 1return 1elsereturn NILelse if V.min != NIL and x < V.minreturn V.minelsemax-low = vEB-Tree-Maximum(V.cluster[high(x)])if max-low != NIL and low(x) < max-lowoffset = vEB-Tree-Successor(V.cluster[high(x)], low(x))return index(high(x), offset)elsesucc-cluster = vEB-Tree-Successor(V.summary, high(x))if succ-cluster == NILreturn NILelseoffset = vEB-Tree-Miniimum(V.cluster[succ-cluster])return index(succ-cluster, offset)

vEB-Tree-Predecessor(V, x)if V.u == 2if x == 1 and V.min == 0return 0elsereturn NILelse if V.max != NIL and x > V.maxreturn V.maxelsemin-low = vEB-Tree-Minimum(V.cluster[high(x)])if min-low != NIL and low(x) > min-lowoffset = vEB-Tree-Predecessor(V.cluster[high(x)], low(x))return index(high(x), offset)elsepred-cluster = vEB-Tree-Predecessor(V.summary, high(x))if pred-cluster == NILif V.min != NIL and x > V.maxreturn V.minelsereturn NILelseoffset = vEB-Tree-Minimum(V.cluster[pred-cluster])return index(pred-cluster, offset)

插入一个元素

vEB-Empty-Tree-Insert(V, x)V.min = xV.max = x

vEB-Tree-Insert(V, x)if V.min == NILvEB-Empty-Tree-Insert(V, x)elseif x < V.minexchange x with x.minif V.u > 2if vEB-Tree-Minimum(V.cluster[high(x)]) == NILvEB-Tree-Insert(V.summary, high(x))vEB-Empty-Tree-Insert(V.cluster[high(x)], low(x))elsevEB-Tree-Insert(V.cluster[high(x)], low(x))if x > V.maxV.max = x

删除一个元素

vEB-Tree-Delete(V, x)if V.min == V.maxV.min = NILV.max = NILelse if V.u == 2if x == 0V.min = 1elseV.min = 0V.max = V.minelseif x == V.minfirst-cluster = vEB-Tree-Minimum(V.summary)x = index(first-cluster, vEB-Tree-Minimum(V.cluster[first-cluster]))V.min =xvEB-Tree-Delete(V.cluster[high(x)], low(x))if vEB-Tree-Minimum(V.cluster[high(x)]) == NILvEB-Tree-Delete(V.summary, high(x))if x = V.maxsummary-max = vEB-Tree-Maximum(V.summary)if summary-max == NILV.max = V.minelseV.max = index(summary-max, vEB-Tree-Maximum(V.cluster[summary-max]))elseif x == V.maxV.max = index(high(x), vEB-Tree-Maximum(V.cluster[high(x)]))

本内容不代表本网观点和政治立场,如有侵犯你的权益请联系我们处理。
网友评论
网友评论仅供其表达个人看法,并不表明网站立场。