Schoolof Co buten Seicuac aud technology Page177132-2 。证明:在任何一棵有n个结点的二叉搜索树中,恰有n-1种可能的旋转。 解:直观解释or递归证明都可以。 直观解释 每个结点均可以和 parent结点进行一次旋转,共有n-1个结点存在 parent 结点,共n-1种可能的旋转 递归证明 a.n=1,个root结点无法旋转(0) b.假设k个node有k-1种旋转,现插入一个新node,若为其 parent结点 的et子节点,则增加一种右旋,若为 right子节点,增加一种左旋, 即k+1个结点有k种旋转 20221
Page177 13.2-2 2021/2/11 12 。证明：在任何一棵有n个结点的二叉搜索树中，恰有n-1种可能的旋转。 解：直观解释or 递归证明都可以。 • 直观解释 每个结点均可以和parent结点进行一次旋转，共有n-1个结点存在parent 结点，共n-1种可能的旋转 • 递归证明 a. n=1 ,一个root结点无法旋转（0） b. 假设k个node有k-1种旋转，现插入一个新node，若为其parent结点 的left子节点，则增加一种右旋，若为right子节点，增加一种左旋， 即k+1个结点有k种旋转
Schoolof Co buten Seicuac aud technology Page18213.3-1 。在RB- INSERT中,为什么将新插入的点着红色而非黑色? 解: RB-Tree性质 结点 red or black 根结点为 black NI叶节点均为back 红结点的子节点均为黑 每个节点到所有后代叶节点的简单路径上,均包含相同数目的黑结点 新插入结点着黑色,不违反性质4,必违反性质5 新插入结点着红色,不违反性质5,可能违反性质4 20221
Page182 13.3-1 2021/2/11 13 。在RB-INSERT中，为什么将新插入的点着红色而非黑色？ 解： RB-Tree性质： • 结点red or black • 根结点为black • NIL叶节点均为black • 红结点的子节点均为黑 • 每个节点到所有后代叶节点的简单路径上，均包含相同数目的黑结点 新插入结点着黑色，不违反性质4，必违反性质5 新插入结点着红色，不违反性质5，可能违反性质4
Schoolof Co buten Seicuac aud technology Page33021.3-2 。写出使用路径压缩的FND-SET过程的非递归版本。 解: 1./*递归版本*/ 2. FIND-SET(X) 3. if p 4 x p= FIND-SET(x p) 5. return X p 递归查找root 将路径中所有节点直接指向root,即 node p=root return root 思路1:循环査找并记录root结点;循环更新每个结点的 parent指向。(更新xp前 需先记录xp) 思2:使用 stack模拟递归过程 20221
Page330 21.3-2 2021/2/11 14 。写出使用路径压缩的FIND-SET过程的非递归版本。 解： 1. /* 递归版本 */ 2. FIND-SET(x) 3. if x != x.p 4. x.p = FIND-SET(x.p) 5. return x.p • 递归查找root • 将路径中所有节点直接指向root，即node.p = root • return root 思路1： 循环查找并记录root结点；循环更新每个结点的parent指向。（更新x.p前 需先记录x.p） 思路2： 使用stack模拟递归过程
Schoolof Co buten Seicuac aud technology Page33021.3-2 方法1:循环更新 ·方法2:使用 stack FIND-SET(X) 1. FIND-SET(X) 2. Initialize an empty stack s 2. root =x 3. while(root =root p)3, while(x != xp root oot 4 5. While(x ! root) p =xp 6.while(!s empty o) 7 X p= root y =spopo) 8 X temp return x 常见错误 9. return root 1. FIND-SET(X) 3. while(x ! root) p root 6. return root 20221
Page330 21.3-2 2021/2/11 15 • 方法1：循环更新 1. FIND-SET(x) 2. root = x 3. while(root != root.p) 4. root = root.p 5. while(x != root) 6. temp = x.p 7. x.p = root 8. x = temp 9. return root • 方法2：使用stack 1.FIND-SET(x) 2.Initialize an empty stack s. 3.while(x != x.p) 4. s.push(x) 5. x = x.p 6.while(!s.empty()) 7. y = s.pop() 8. y.p = x 9.return x 常见错误： 1.FIND-SET(x) 2.... 3.while(x != root) 4. x.p = root 5. x = x.p 6.return root
Schoolof Co buten Seicuac aud technology Page593324-1 。计算对应于模式 ababbabbabbababbabbl的前缀函数丌。 11234567891011|12|13141516171819 PU a b a b b b b b a [i]00120 a1 2012012345678 20221
Page593 32.4-1 2021/2/11 16 。计算对应于模式ababbabbabbababbabb的前缀函数𝜋。 i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 P[i] a b a b b a b b a b b a b a b b a b b 𝝅 𝒊 0 0 1 2 0 1 2 0 1 2 0 1 2 3 4 5 6 7 8