[工学]Ch1314 Part3 红黑树、数据结构扩张.pptVIP

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * §14.1 动态顺序统计 (续) 维护子树的Size OSSelect和OSRank之所以能快速地计算，原因是OS树中给出了Size信息。但若在修改RB树的基本操作中不能有效地维护Size信息，这些新操作就失去了意义。一般地： 对基本数据结构进行扩充信息，必须保证能有效地维护这些信息，所谓有效维护附加信息是指：扩充后的基本操作（主要是指修改）与扩充前的基本操作的渐近时间相同 * §14.1 动态顺序统计 (续) 插入 RB树上插入分两阶段 Phase1：从根自下，插入新结点，增加Size后，只要将：有哪些信誉好的足球投注网站插入位置路径上各结点的Size加1，新结点Size置为1即可，附加成本O(lgn) Phase2：从叶子向上调整：变色，旋转；仅旋转改变了RB树结构，故为维护Size，只需考虑对该操作修改。 旋转操作是局部操作，仅有执行旋转的边上（轴）的两个结点的Size域可能违反其定义，故只需在旋转操作尾部加上相应修改Size操作即可 * §14.1 动态顺序统计 (续) 例如LeftRotate(T,x) (右旋与此对称) size[y]?size[x]; //y取代x为子树的根 size[x]?size[left[x]]+size[right[x]]+1;//旋转后的结点数 ∵每个旋转操作时间O(1)，而插入过程中，至多有两个旋转 ∴OS树上作插入总时间代价仍为O(lgn)，与RB树相同 * §14.1 动态顺序统计 (续) 删除 RB树上删除亦为两阶段 Phase1：物理上删去y，从y上溯至根的路径上各结点size减1，额外时间O(lgn) Phase2：至多有三个旋转会改变结构，故旋转操作所花的修改size时间为O(1)。 结论：在OS树上删除操作的时间仍为O(lgn) * §14.2 怎样扩充一个数据结构 在算法设计中，经常需要扩充一个基本的数据结构，使之： 支持某些附加功能（开发新操作） 加速某些已有功能（加速已有操作） 扩充步骤 选择一基本数据结构 确定附加info（不一定仅是数据，亦可能是指针） 维护附加info（有效） 开发新操作 * §14.2 怎样扩充一个数据结构（续） 不一定非得按上述次序进行，如，若第三步不能有效维护附加info，step2，4就无讨论的必要。OS树按此次序设计: Step1：选择RB作为～，∵它有效地支持全序下的动态集合的操作（求最大/小，前趋，后继等） Step2：在RB树中增加Size，使OSSelect和OSRank能快速实现，在RB树上时间会更多 Step3：有效性 Step4：新操作OSSelect和OSRank Note：若在RB树中增加rank域，则OSSelect和OSRank能快速进行，但插删可能引起树中每结点上Rank的修改，其时间为O(n)，得不偿失 * §14.2 怎样扩充一个数据结构（续） 扩充RB树定理 当扩充RB树时，能否有效维护附加Info呢？若满足下述定理，则附加info可有效维护之。 Th14.1：设f是在RB树T的n个结点上扩充的域，对任意x∈T，假设结点x的f域的内容f[x]能够仅通过结点x，left[x]，right[x]的info（包括f[left[x]] 和 f[right[x]]）计算，则可以在插删时维护T中所有结点的f域而不改变这些操作的渐近时间O(lgn) Pf：基本思想：f[x]的变化只会传播到x的祖先，即改变f[x]只可能影响f[p[x]]的变化，而修改f[p[x]]只可能引起f[p[p[x]]]的修改，…如此向上传播，直至f[root[T]]被修改后，没有其他节点需修改为止。附加成本O(lgn)。具体插删的证明（略） * §14.2 怎样扩充一个数据结构（续） Ex 14.1-4 Ex 14.1-7 * §14.3 区间树 将RB树扩充为支持区间… 闭区间：实数有序对[t1,t2]使得t1 ≤ t2，一区间代表一集合：{t ∈ : t1 ≤ t ≤ t2} 开、半开区间： 本节只讨论闭区间，其结果易扩展到开/半开区间上 区间可用来表示一个事件所占用的时间，故在一时间区间数据库中，可询问某一给定区间上所有发生的事件 区间[t1,t2]可表示为一对象i，它有两属性： low[i]=t1 //起点 high[i]=t