c++红黑树.ppt

红黑树 可以干嘛? 是棵平衡的树: 保证从根到某个叶结点的简单路径一定不会超过从根到任何一条其它這样的路径的兩倍长 大致平衡?操作可以都在O(log2n)內完成。 操作 1. 有哪些信誉好的足球投注网站 2. 插入结点 3. 删除结点 4. 找最大或最小值 * 红黑树 每个结点都分配一个颜色: 红或黑 使用扩充二叉树: 沒有子女的地方都外上外结点, 又叫nil 规则: 1. 每个结点不是黑就是红 2. 根是黑色的 3. 每个叶结点 (external node, 或 nil)都是黑色 4. 如果一个结点是红的, 則它的子女都是黑的 5. 对每个结点來说, 从它到他的所有子孙叶子结点的路径上含有一样数目的黑色结点 * 黑高度 Black height: bh(x) = 从x到任何一个它的子孙叶子结点遇到的black 结点个数 (因为都一样, 所以可以是任何一个) 不包含结点 x自己 external 结点或nil(叶子结点)的black height为0 * 巨大的红黑树例子 * 26 17 41 47 nil 30 35 39 38 28 14 21 10 16 19 23 20 15 12 7 nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil 3 nil nil 1 2 1 1 1 1 2 3 1 2 3 2 1 1 1 1 2 1 1 1 bh(x)們 巨大的红黑树例子 * 26 17 41 47 30 35 39 38 28 14 21 10 16 19 23 20 15 12 7 3 1 2 1 1 1 1 2 3 1 2 3 2 1 1 1 1 2 1 1 1 bh(x) nil 來點证明 * 來點证明 * 以上证明… 说明为什么 1. 有哪些信誉好的足球投注网站 4. 找最大或找最小element 等操作可以在O(log n)內完成 那麼insert和delete呢? 問題: 插入或删除之后, 可能不滿足红黑树的条件 * Representation * data parent left right color Rotate 等一下会用到的 * y x x y left-rotate(T,x) right-rotate(T,y) Insertion 首先, 用原本的binary search tree插入的方法 insert(z) 不同的地方: 1. z的兩个子女都指到nil 结点 2. z为红色 3. 我們最后要处理不符合红黑树规则的部分 怎么处理? * nil 会违反那些规则呢? * nil nil nil 17 情形一: 你的叔叔是红的 * D A B C z: 你 y:叔叔 parent(z): 你爸 D A B C z: 你 继续看新z爸爸是不是红的 你是你爸右边的小孩 情形一: 你的叔叔是红的 * D B A C z: 你 y:叔叔 parent(z): 你爸 D B A C z: 你 你是你爸左边的小孩 注意看每一个步骤是否保持了 红黑树第五个条件 情形二、三: 你的叔叔是黑的 * A B C z: 你 y:叔叔 parent(z): 你爸 B A C z: 你 parent(z): 你爸 y:叔叔 B A C z: 你 你是你爸右边的小孩 你是你爸左边的小孩 left rotate(A) right rotate(C) 需要继续往上层看吗? 不用! 因为B还是黑的! 注意看每一个步骤是否有保持 红黑树第五个条件 练习 * 26 17 41 47 30 35 39 38 28 14 21 10 16 19 23 20 15 12 7 3 1 2 1 1 1 1 2 3 1 2 3 2 1 1 1 1 2 1 1 1 2. 加入4? 1. 加入40? 要花多少時間呢? 原本正常的binary tree insert要花O(log n)的時間 因为高度最高为2 log(n+1) 那麼花費在調整的時間呢? 最糟的狀況? 情形一一直重复发生, 每次z往上移兩层 执行時間最糟要花跟高度成正比的時間 也是O(log n) 那如果发生情形二或三呢? 执行一次即完成. O(1). (所以比O(log n)小) 另外, 最多rotate只需要执行兩次. (不会再发生第二次情形二或三) * 如何刪掉一个结点? (binary search tree 复習) 首先要先找到那个结点 接著, 有各種不同情形: 如果沒有手(degree=0) 直接拿掉 * 20 12 22 25 10 15 11 如何刪掉一个结点? (binary search tree 复習) 如果只有一隻手 (degree=1) 則把那个唯一的child拿上來接到p