当前位置：文档之家 › 红黑树讲义

红黑树讲义

  • 格式：pdf
  • 大小：1.02 MB
  • 文档页数：32
nil
14
會違反那些規則呢?
• 規則們:
nil
17
• 1. 每個node不是黑就是紅 • 2. root是黑色的 • 3. 每個leaf (external node, or nil)都是黑色
nil
nil
• 4. 如果一個node是紅的, 則它的children都是黑的
• 5. 對每個node來說, 從它到他的所有子孫葉子node的路徑上
情形一: x的弟弟是紅的
change color of B and D and left rotate(B) B A x D w B C E new w x A C E D
轉換成情形二、三、或四
28
情形二： x的弟弟是黑的&它的姪子們都是黑的
B A x D w
new x
B D
A
C
E
C
E
29
情形三: x的弟弟是黑的 它的姪子們都是左紅右黑
變成case 4 B A x D w C和D顏色改變 right rotate(D) B A x new w C D
C
E
E
30
情形四: x的弟弟是黑的 它的姪子右邊那一個是紅的
B,D,E顏色改變 left rotate(B) B A x D w A C E new x=root B C D
E
31
parent(z): 你爸 A
16
情形一: 你的叔叔是紅的
你是你爸左邊的小孩 C D z: 你 C y:叔叔 B D parent(z): 你爸 B
A z: 你
A
注意看每一個步驟是否有保持 紅黑樹第五個條件
17
情形二與三: 你的叔叔是黑的
parent(z): 你爸 A z: 你 C y:叔叔 left rotate(A) B z: 你 A right rotate(C) 你是你爸右邊的小孩 你是你爸左邊的小孩 z: 你 A B C parent(z): 你爸 B C y:叔叔
20 1
nil
nil
1
nil nil
1
nil
nil
7
巨大的紅黑樹例子
3 26 3 17 2 2 10 1 7 1 3 nil 12 1 1 15 20 1 16 2 21 1 1 19 23 1 1 28
bh(x)們
2 41 1 2 30 1 38 35 39 47
14
1
1
8
來點證明
• 定理: 一個有n個node的紅黑樹, 最高為2 log(n+1) • 第一步驟: 證明node x底下的subtree最少有2 • • •
1個
• • •
internal node 歸納法證明: 1. 當x的height為0, 則x是個葉子. bh(x)=0. 2 1 0. 的確 subtree有0個internal node. 2. 假設當x的height為正整數, 且是一個有兩個children的 internal node. 每個小孩的black height為bh(x) or bh(x)‐1. (看 該小孩是黑是紅) 假設小孩的subtree都至少有2 1個internal node 3. 則x底下的subtree應該有 2 1 2 1 1 2 1(成功了!)
• 執行一次即完成. O(1). (所以比O(log n)小)
• 另外, 最多rotate只需要執行兩次. (不會再發生第二次情形二
or三)
20
如何刪掉一個node? (binary search tree 複習)
• 首先要先找到那個node • 接著, 有各種不同情形: • 如果沒有手(degree=0) • 直接拿掉
含有一樣數目的黑色node
5
黑高度
• Black height: bh(x) = 從x到任何一個它的子孫葉子node遇到
的black node個數 (因為都一樣, 所以可以是任何一個) • 不包含node x自己 • external node或nil(葉子node)的black height為0
11
22
如何刪掉一個node? (binary search tree 複習)
• 如果兩手都有東西呢? (degree=2) • 例如刪掉12 • 找左邊child底下最大的 • (或者是右邊child底下最小的)
10 15 25 12 22 20
• 刪掉它並把它移到原本刪掉的位置
11
• 問題: 那如果那個最大的底下還有child呢? • 直接拿上來(最多只會有左邊一隻手) • 這時被移上去的node顏色改變成新位置原本node的顏色
26
怎麼修正紅黑樹以符合規則呢?
• 假設x為移動到y位置的node • (如果忘記了的話, y是被刪掉或被移動的node) • y原本是黑的, 則x好像要”有兩個黑”, 這樣black height才會正
確
• 每次x都指到一個”兩個黑”的node (或者也有可能是”紅與黑”) • 依序修正
27
6
巨大的紅黑樹例子
3 26 3 17 2 2 10 1 7 1 3
nil nil nil nil nil nil nil nil
bh(x)們
2 41 2 21 1 1 19
nil nil
1 2 1 23 1 28
nil nil nil
14
30 1 38 35 39
47
nil nil
16 1 1 12 15
11
24
拿掉一個node, 什麼時候會違反規則?
• B. 如果y是被移動的, 假設y有
children也是黑色的, 不會造成 問題
12 15
20
• 3. y如果是紅色, 它不會是root.
22
所以也不會有造成違反root是 黑色的規定
10
25
• 綜合以上三點, 只有當y為黑色
11
時才會造成問題, 需要調整
注意看每一個步驟是否有保持 紅黑樹第五個條件
需要繼續往上層看嗎? 不用! 因為B還是黑的!
18
黑板練習時間
3 26 3 17 2 2 10 1 7 1 3 1. 加入40? 2. 加入4? 12 1 1 15 20 1 35 1 39 1 16 2 21 1 1 19 23 1 1 28 38 2 41 1 2 30 1 47
•2 •
1 2 log
2
1個node. 2 1 1 . 耶.
• 假設node個數為n, 則
10
以上證明…
• 說明為什麼 • 1. 找 • 4. 找最大or找最小element • 等operation可以在O(log n)內完成 • 那麼insert和delete呢? • 問題: 插入或殺掉之後, 可能不滿足紅黑樹的條件
10 15 25 12 20
22
11
21
如何刪掉一個node? (binary search tree 複習)
• 如果只有一隻手 (degree=1) • 則把那個唯一的child拿上來接到parent上 • 例如: 拿掉22
10 12 15 20
22
25
• 問題: 要怎麼接? • 怎麼記得parent是誰?
14
19
要花多少時間呢?
• 原本正常的binary tree insert要花O(log n)的時間 • 因為高度最高為2 log(n+1) • 那麼花費在調整的時間呢? • 最糟的狀況? 情形一一直重複發生, 每次z往上移兩層 • 執行時間最糟要花跟高度成正比的時間 • 也是O(log n)
• 那如果發生情形二or三呢?
紅黑樹
• 可以幹嘛? • 是棵平衡的樹: 保證從root到某個leaf的simple path一定不會
超過從root到任何一條其他這樣的path的兩倍長 • 大概平衡operation可以都在O(log n)內完成. 耶.
• 那些operation? • 1. 找 • 2. 插入某element • 3. 殺掉某element • 4. 找最大or找最小element
11
Representation
parent color data
left
right
12
Rotate
• 等一下會用到的
left‐rotate(T,x) y right‐rotate(T,y) x y x
13
Insertion
• 首先, 用原本的binary search tree插入的方法 • insert(z) • 不同的地方: • 1. z的兩個children都指到nil node • 2. z為紅色 • 3. 我們最後要處理不符合紅黑樹規則的部分 • 怎麼處理?
4
紅黑樹
• 每個node都分配一個顏色: 紅或黑 • 使用extended binary tree: 沒有children的地方都補上external
node, 又叫nil
• 規則們: • 1. 每個node不是黑就是紅 • 2. root是黑色的 • 3. 每個leaf (external node, or nil)都是黑色 • 4. 如果一個node是紅的, 則它的children都是黑的 • 5. 對每個node來說, 從它到他的所有子孫葉子node的路徑上
含有一樣數目的黑色node
• 5.不會違反因為z是紅的, z取代掉一個nil, 而z的兩個children
都是nil • 如果違反2, 則z是root, 整棵樹只有z: 很容易處理 • 來看違反4的情形: z’s parent is also redBiblioteka 5情形一: 你的叔叔是紅的
繼續看新z爸爸是不是紅的 你是你爸右邊的小孩 C y:叔叔 D B z: 你 A z: 你 C D B

合集下载

【算法】红黑树原理和算法介绍

【算法】红黑树原理和算法介绍

【算法】红⿊树原理和算法介绍红⿊树介绍⼆叉查找树 学红⿊树，⾸先理解⼆叉查找树 ⼆叉查找树（BST）具备特性1. 左⼦树上所有结点的值均⼩于或等于它的根结点的值。

2. 右⼦树上所有结点的值均⼤于或等于它的根结点的值。

3. 左、右⼦树也分别为⼆叉排序树。

⼆叉查找树是⼆分查找的思想，查找所需的最⼤次数等同于⼆叉树的⾼度。

在插⼊节点的时候也是利⽤类似的⽅法，⼀层⼀层⽐较⼤⼩，找到合适的插⼊位置。

如下图，这样虽然满⾜了⼆叉查找树的条件，但是这个是瘸腿的⼆叉查找树，就和链表没有区别了。

这是⼆叉查找树的缺点解决⼆叉查找树多次插⼊新节点⽽导致的不平衡的⽅法，就是使⽤红⿊树。

红⿊树是⼀种⾃平衡的⼆叉查找树。

红⿊树 R-B Tree，全称是Red-Black Tree，⼜称为“红⿊树”，它⼀种特殊的⼆叉查找树。

红⿊树的每个节点上都有存储位表⽰节点的颜⾊，可以是红(Red)或⿊(Black)。

红⿊树的特性: （1）每个节点或者是⿊⾊，或者是红⾊。

（2）根节点是⿊⾊。

（3）每个叶⼦节点（NIL）是⿊⾊。

[注意：这⾥叶⼦节点，是指为空(NIL或NULL)的叶⼦节点！] （4）如果⼀个节点是红⾊的，则它的⼦节点必须是⿊⾊的。

（5）从⼀个节点到该节点的⼦孙节点的所有路径上包含相同数⽬的⿊节点。

上⾯⼀系列的规则，保证了红⿊树的⾃平衡。

红⿊树从根到叶⼦的最长路径不会超过最短路径的2倍当插⼊或删除节点的时候，红⿊树的规则有可能被打破，这个时候需要进⾏调整来维持红⿊树的规则。

如下图，如果向原红⿊树插⼊值为21的新节点，由于⽗节点22是红⾊节点，因此这种情况打破了红⿊树的规则4（每个红⾊节点的两个⼦节点都是⿊⾊），必须进⾏调整，使之重新符合红⿊树的规则。

调整的⽅法有两种：1. 变⾊：红变⿊，⿊变红2. 旋转：左旋转和右旋转变换规则旋转和颜⾊变换规则：所有插⼊的点默认为红⾊1. 变颜⾊的情况：当前结点的⽗亲是红⾊，且它的祖⽗结点的另⼀个⼦结点也是红⾊（叔叔结点）：（1）把⽗节点设为⿊⾊（2）把叔叔也设为⿊⾊（3）把祖⽗也就是⽗亲的⽗亲设为红⾊（爷爷）（4）把指针定义到祖⽗结点设为当前要操作的（爷爷）分析的点变换的规则2. 左旋：当前⽗结点是红⾊，叔叔是⿊⾊的时候，且当前的结点是右⼦树。

算法导论-8.红黑树详解

算法导论-8.红黑树详解

算法导论-8.红⿊树详解红⿊树是⼀种相当复杂的数据结构，⼀种能够保持平衡的⼆叉查找树。

如果条件极端，随机⽣成的⼆叉树可能就是⼀个单链表，深度为 $n$，⽽红⿊树的⾼度，即使在最坏情况下也是 $\Theta(n)$ ，红⿊树通过满⾜以下5条性质来保证这⼀点：1. 节点是红⾊或者⿊⾊的。

2. 根节点的⿊⾊的。

3. NIL节点时⿊⾊的。

4. 每个红⾊节点的左⼦节点和右⼦节点必定是⿊⾊的。

5. 任意叶⼦节点的⿊深度相等。

注：这⾥以及下⽂的叶⼦节点是指真正的有意义的“叶⼦节点”⽽不是NIL节点。

如：这是⼀颗红⿊树，注意所有NIL节点其实都是⼀个节点。

我仔细研究了红⿊树，并⾃⼰实现了它，这是⼀个多⽉来看《算法导论》给我带来成就感最⼤的⼀次。

我改进了之前⼆叉查找树的代码，使⽤⼆叉树-⼆叉查找树-红⿊树和⼆叉树节点-红⿊树节点的继承关系链；并且，为了增强算法复杂部分代码的可读性，我对部分功能函数实现了⼀些看上去有点累赘的重载。

这篇博⽂可能不会分析这些⽐较简单的重载，但是完整的代码可以下载（⽅便起见，我将实现和定义全部写在⼀个头⽂件中）。

这篇博⽂参考了《算法导论》第12、13章和维基百科的“红⿊树”词条，所⽤的⽰意图也来⾃于维基百科中，这⾥先作说明。

此外，这⼀篇仅分析红⿊树的实现，不设计章节后⾯的习题。

⼆叉树⼆叉树是最简单的，我提供了⼀些基本的功能。

我尽量使变量名和函数名不⾔⾃明，所以不会作过多解释。

先看⼆叉树节点：template <typename T> class xBinaryTreeNode{public:xBinaryTreeNode();xBinaryTreeNode(T val);T data;xBinaryTreeNode<T>* leftChild;xBinaryTreeNode<T>* rightChild;xBinaryTreeNode<T>* father;};template <typename T> xBinaryTreeNode<T>::xBinaryTreeNode(){leftChild = rightChild = father = NULL;}template <typename T> xBinaryTreeNode<T>::xBinaryTreeNode(T val){data = val;leftChild = rightChild = father = NULL;}然后看⼆叉树的声明：template <typename T> class xBinaryTree{public:xBinaryTree();xBinaryTreeNode<T>* getHead();bool isEmpty();bool doesExit(xBinaryTreeNode<T>* node);bool isRoot(xBinaryTreeNode<T>* node);bool hasLeftChild(xBinaryTreeNode<T>* node);bool hasRightChild(xBinaryTreeNode<T>* node);xBinaryTreeNode<T>** getSelfFromFather(xBinaryTreeNode<T>* node);xBinaryTreeNode<T>** getBrother(xBinaryTreeNode<T>* node);protected:xBinaryTreeNode<T>* nilNode;};有⼏点需要说明：nilNode是⼀个存在的“空节点”，是根节点（或称头结点）的⽗节点，也是所有叶⼦节点实际上的⼦节点。

教你透彻了解红黑树概论

教你透彻了解红黑树概论

红黑树系列，六篇文章于今日已经完成：1、教你透彻了解红黑树2、红黑树算法的实现与剖析3、红黑树的c源码实现与剖析4、一步一图一代码，R-B Tree5、红黑树插入和删除结点的全程演示6、红黑树的c++完整实现源码------------------------------一、红黑树的介绍先来看下算法导论对R-B Tree的介绍：红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red 或Black。

通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

前面说了，红黑树，是一种二叉查找树，既然是二叉查找树，那么它必满足二叉查找树的一般性质。

下面，在具体介绍红黑树之前，咱们先来了解下二叉查找树的一般性质：1.在一棵二叉查找树上，执行查找、插入、删除等操作，的时间复杂度为O（lgn）。

因为，一棵由n个结点，随机构造的二叉查找树的高度为lgn，所以顺理成章，一般操作的执行时间为O（lgn）。

//至于n个结点的二叉树高度为lgn的证明，可参考算法导论第12章二叉查找树第12.4节。

2.但若是一棵具有n个结点的线性链，则此些操作最坏情况运行时间为O（n）。

而红黑树，能保证在最坏情况下，基本的动态几何操作的时间均为O（lgn）。

ok，我们知道，红黑树上每个结点内含五个域，color，key，left，right，p。

如果相应的指针域没有，则设为NIL。

一般的，红黑树，满足以下性质，即只有满足以下全部性质的树，我们才称之为红黑树：1）每个结点要么是红的，要么是黑的。

2）根结点是黑的。

3）每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的。

4）如果一个结点是红的，那么它的俩个儿子都是黑的。

5）对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。

（注：上述第3、5点性质中所说的NULL结点，包括wikipedia.算法导论上所认为的叶子结点即为树尾端的NIL指针，或者说NULL结点。

红黑树

红黑树


红黑树的删除
删除节点后对RBT性质的影响讨论：
若删除结点为红色，则对RBT性质没有影响，原因？ • 树中各结点的黑高没有变化 • 不存在两个相邻的红色结点 • 因为删除结点为红色，就不可能是根，所以根仍然 为黑
若删除结点为黑色，则对RBT性质会产生影响，因此 需要调整
红黑树的删除
删除的调整算法 讨论
红黑树
目录
§.1 红黑树的定义
§.2 红黑树的性质
§.3 红黑树的旋转
§.4 红黑树的插入
§.5 红黑树的删除
红黑树的插入
step 1：将z节点按二叉查找树规则插入红 黑树中，z是叶子节点； step 2：将z涂红； step 3：调整使其满足红黑树的性质；
红黑树的插入
插入算法示例
• RBInsert(T, z) { y ← nil[T]; x ← root[T]; while x ≠ nil[T] do { y ← x; if key[z] ＜ key[x] then x ← left[x]; else x ← right[x]; } p[z] ← y; if y = nil[T] then
红黑树的删除
Case1：z为叶结点 Case2：z只有一个孩子
处理方法：删除z，连接x。这里x是z的中序后继
注： • case 1是case 2的特例，因为处理模式是一样的 • z是p[z]的左孩子，类似讨论
红黑树的删除
Case3：z两个孩子均非空 实际删除的结点为y！
处理方法： (1)找z的中序后继，即找z的右子树中最左下节点y (2)删除y，将y的内容copy到z，再将y的右子连到 p[y]左下。
root[T] ← z;
//y用于记录当前扫描节点的双亲节点 //从根开始扫描 //查找插入位置 //z插入x的左边