1. 概述

红⿊树（R-B Tree）是由Rudolf Bayer在1972发明。是⼀种⾃平衡⼆叉搜索树，其中每个结点都有⼀个额外的位，存储该结点的颜⾊（红⾊或⿊⾊）

1.1 特性

  • 时间复杂度：插⼊、搜索和删除操作O(logn)

  • 空间复杂度：O(n)

  • 红⿊树还添加了⼀种特殊类型的结点 ，称为NIL结点。NIL结点将做为红⿊树的伪叶⼦结点出现

  • 对于任意⼀个结点n

    • 结点的颜⾊只能是红⾊或者⿊⾊

    • 根结点是⿊⾊的

    • 从根到任何叶结点的每条路径必须具有相同数量的⿊⾊结点

    • 没有两个红⾊结点可以相连，即⼀个红⾊结点不能是另⼀个红⾊结点的⽗结点或⼦结点

    • NIL结点的颜⾊是⿊⾊

    • 如果结点的颜⾊是红⾊，则其⼦结点均为⿊⾊

    • 具有n个结点的红⿊树的⾼度为：h <= 2log(n + 1)

    • 红⿊树的⿊⾊⾼度是从根结点到叶结点的路径上的⿊⾊结点数。叶结点也算作⿊⾊结点。因此，⾼度为h的红⿊树的⿊⾊⾼度 >= h / 2

  • 在每次插⼊或删除后，如果任何结点的平衡因⼦不遵循平衡属性

    • 左旋

    • 右旋

1.2 优势

  • ⼤多数BST操作，例如：搜索、最⼤值、最⼩值、插⼊、删除，都需要O(h)时间，其中h是BST的⾼度

  • 如果我们确保每次插⼊和删除后树的⾼度始终为O(log n)，那么就可以保证所有这些操作的上限为O(log

n)。红⿊树的⾼度始终为O(log n)，其中n是树中的结点数

  • 红⿊树主要⽤于实现频繁执⾏插⼊或删除

  • ⼤多数⾃平衡BST库函数，如C++中的map和set，或Java中的TreeSet和TreeMap都使⽤红⿊树

  • MySQL还使⽤红⿊树作为表索引

  • 实现Linux的CPU调度

1.3 对比AVL树

AVL树 VS 红⿊树：

  • 红⿊树是不符合AVL树的平衡条件的，即每个结点的左⼦树和右⼦树的⾼度最多差1的⼆叉查找树

  • 红⿊树是⽤⾮严格的平衡来换取增删结点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决

  • AVL是严格平衡树，因此在增加或者删除结点的时候，根据不同情况，旋转的次数⽐红⿊树要多。所以红⿊树的插⼊效率更⾼

  • AVL在查询频繁的系统⾥⽐红⿊树更⾼效，原因是AVL树的平均⾼度⽐红⿊树更⼩

  • AVL树主要用于搜索，红⿊树主要用于插入和删除

2. 2-3-4树

红黑树是2-3-4树的一种转型，而2-3-4树是四阶的B树（Balance Tree）

  • 结点存储1，2或者3个key，并且拥有2，3或者4个孩⼦

  • 所有叶⼦结点都拥有相同的深度

  • 1 / 2log(N + 1 ) ≤ height ≤ log(N + 1)

B树和平衡二叉树稍有不同，B树属于多叉树又名平衡多路查找树（查找路径不只两个），数据库索引技术里大量使用者B树和B+树的数据结构

B+树是B树的一个升级版，相对于B树来说，B+树更充分的利用了结点的空间，让查询速度更加稳定，其速度完全接近于二分法查找

2.1 形态

两个结点，和⼆叉树⼀样：
image.png

三个结点，有两个key和三个孩⼦：
image.png

四个结点，有三个key和四个孩⼦：
image.png

假设：2-3-4树中每个结点都拥有相同数量的孩⼦结点d：
image.png

  • 整个2-3-4树的搜索时间为O(log(d)N)

  • 如果d = N¹⁄² ，那么该树的⾼度为2

  • 2-3-4树可以保证O(logN)，如果每个结点只有2，3或者4个孩⼦

2.2 插⼊

插入元素g，结点从两个变为三个：
image.png

插⼊元素f，结点从三个变为四个：
image.png

插⼊元素e，每当我们到达⼀个4结点，把它分成两个2结点，并将中间元素向上移动进⽗结点
image.png

插⼊元素g，每当我们到达⼀个4结点，把它分成两个2结点，并将中间元素向上移动进⽗结点
image.png

2.3 特性

  • 搜索的时间复杂度是O(log N)

  • 插⼊的时间复杂度是O(log N)

  • 删除的时间复杂度是O(log N)

优点：

  • 平衡

  • O(log N)

缺点：

  • 数据结构复杂

我们将2-3-4树的优点带⼊到⼆叉树中，就是红⿊树。它继承了2-3-4树的优点，将搜索、插入、删除的时间控制在O(log N)

3. 红黑树

2-3-4树的每一个结点都对应红黑树的一种结构，所以每一棵2-3-4树也都对应一棵红黑树

3.1 形态

2-3-4树与红黑树的对应形态：

两个结点，对应红黑树结构：
image.png

三个结点，对应红黑树结构：
image.png

  • a和b谁作为根结点，取决于它们的插入顺序，先插入的元素为根结点

四个结点，对应红黑树结构：
image.png

  • 依次插入结点a、b、c，a作为根结点，b为a的右孩子，c为b的右孩子，此时结构为一棵右斜树

  • 根据红黑树特性，根结点a一定为黑色，而b和c作为新插入结点为红色

  • 由于红黑树不允许两个红⾊结点相连，故此进行左旋修复

  • 修复后的红黑树b为根结点，a、c分别为b的左、右孩子，同时树结构达到平衡

3.2 特性

  • N：结点总数

  • L：叶⼦数量 = N + 1

  • H：⾼度

  • B：⿊⾊结点的⾼度（从根结点到叶结点的路径上的⿊⾊结点数）

  • 规律1：2 ^ B <= N + 1 <= 4 ^ B

  • 规律2：1/2log(N + 1) <= B <= log(N + 1)

  • 规律3：log(N + 1) <= H <= 2log(N + 1)

4. 结点插入

插入的基本流程：

  • 标准⼆叉搜索树，搜索找到要添加的位置

  • 执⾏替换，颜⾊设置为红⾊

  • 新结点添加叶⼦结点（NIL结点），颜⾊设置为⿊⾊

  • 如果该⽗结点也为红⾊，需要修复

  • 如何修复取决于⽗结点的sibling（兄弟结点）

4.1 思路分析

4.1.1 情况⼀（A）

新结点的⽗结点是⿊⾊结点，什么也不做
image.png

4.1.2 情况⼀（B）

新结点的父结点是红色，但它同时作为根结点，直接将其颜色修改为黑色
image.png

4.1.3 情况二（A）

新结点的⽗结点是红⾊结点，它的叔叔结点是⿊⾊结点，⽗结点处沿插⼊结点的相反⽅向旋转，此时是右旋。⽗结点重新设置为⿊⾊，祖父结点设置为红⾊
image.png

4.1.4 情况二（B）

新结点的⽗结点是红⾊结点，它的叔叔结点是⿊⾊结点，⽗结点处沿插⼊结点的相反⽅向旋转，此时是左旋。⽗结点重新设置为⿊⾊，祖父结点设置为红⾊
image.png

4.1.5 情况二（C）

新结点的⽗结点是红⾊结点，不在⼀边。它的叔叔结点是⿊⾊结点，先左旋，再右旋
image.png

4.1.6 情况二（D）

新结点的⽗结点是红⾊结点，不在⼀边。它的叔叔结点是⿊⾊结点，先右旋，再左旋
image.png

3.2.7 情况三

新结点的⽗结点是红⾊结点，它的叔叔结点是红⾊结点。将⽗结点和叔叔结点重新着⾊为⿊⾊，将祖⽗结点重新着⾊为红⾊。如果祖⽗结点为根结点，重新着⾊为黑⾊
image.png

如果祖⽗结点着⾊为红⾊，有可能还会面临红色相连的结点，例如：R、U
image.png

需要将祖⽗结点进行递归修复
image.png

4.2 代码实现

4.2.1 枚举定义

  1. class RBTree<Element: Comparable> {
  3.     enum RBColor : Int {
  4.         case Red = 0
  5.         case Black = 1
  6.     }
  8.     enum RBRotating : Int {
  9.         case Left = 0
  10.         case Right = 1
  11.     }
  12. }

4.2.2 结点结构

  1. class RBTree<Element: Comparable> {
  3.     fileprivate class RBNode: Equatable {
  5.         static func == (lhs: RBTree<Element>.RBNode, rhs: RBTree<Element>.RBNode) -> Bool {  
  6.             let obj1 = Unmanaged<AnyObject>.passUnretained(lhs).toOpaque();
  7.             let obj2 = Unmanaged<AnyObject>.passUnretained(rhs).toOpaque();
  9.             return obj1 == obj2;
  10.         }
  12.         static func != (lhs: RBTree<Element>.RBNode, rhs: RBTree<Element>.RBNode) -> Bool {
  13.             let obj1 = Unmanaged<AnyObject>.passUnretained(lhs).toOpaque();
  14.             let obj2 = Unmanaged<AnyObject>.passUnretained(rhs).toOpaque();
  16.             return obj1 != obj2;
  17.         }
  19.         // 颜色
  20.         var color : RBColor;
  21.         // 元素
  22.         var data : Element?;
  23.         // 左孩子
  24.         var leftChild : RBNode?;
  25.         // 右孩子
  26.         var rightChild : RBNode?;
  27.         // 父结点
  28.         var parent : RBNode?;
  30.         // 初始化
  31.         init(data: Element?, parent: RBNode?) {
  33.             if(parent == nil) {
  34.                 // 根结点，默认黑色
  35.                 self.color = RBColor.Black;
  36.             }
  37.             else if(data == nil) {
  38.                 // NIL结点，默认黑色
  39.                 self.color = RBColor.Black;
  40.             }
  41.             else {
  42.                 // 其他新创建的结点，默认红色
  43.                 self.color = RBColor.Red;
  44.             }
  46.             self.data = data;
  47.             self.parent = parent;
  49.             if(data != nil){
  50.                 self.leftChild = RBNode(data: nil, parent: self);
  51.                 self.rightChild = RBNode(data: nil, parent: self);
  52.             }
  53.         }
  55.         // 颜色格式化
  56.         var colorFormat: String {
  58.             if(self.color == RBColor.Red){
  59.                 return "red";
  60.             }
  62.             return "black";
  63.         }
  65.         // 当前结点是否为根结点
  66.         var isRoot: Bool {
  68.             if(self.parent == nil){
  69.                 return true;
  70.             }
  72.             return false;
  73.         };
  75.         // 当前结点是否为左孩子结点
  76.         var isLeftChild: Bool {
  77.             get{
  79.                 if(self.isRoot){
  80.                     return false;
  81.                 }
  83.                 if(self.parent!.leftChild == self) {
  84.                     return true;
  85.                 }
  87.                 return false;
  88.             }
  89.         };
  91.         // 当前结点是否为右孩子结点
  92.         var isRightChild: Bool {
  93.             get{
  95.                 if(self.isRoot){
  96.                     return false;
  97.                 }
  99.                 if(self.parent!.rightChild == self) {
  100.                     return true;
  101.                 }
  103.                 return false;
  104.             }
  105.         };
  107.         // 当前结点是否存在父结点
  108.         var isExistParent: Bool {
  109.             get{
  111.                 if(self.isRoot){
  112.                     return false;
  113.                 }
  115.                 return true;
  116.             }
  117.         };
  119.         // 当前结点是否存在祖父结点
  120.         var isExistGrandparent: Bool {
  121.             get{
  123.                 if(!self.isExistParent){
  124.                     return false;
  125.                 }
  127.                 return self.parent!.isExistParent;
  128.             }
  129.         };
  131.         // 获取祖父结点
  132.         var grandparent: RBNode? {
  134.             if(!self.isExistGrandparent){
  135.                 return nil;
  136.             }
  138.             return self.parent?.parent;
  139.         };
  141.         // 当前结点是否为叶子结点
  142.         var isLeaf: Bool {
  143.             get{
  145.                 if(self.leftChild == nil && self.rightChild == nil){
  146.                     return true;
  147.                 }
  149.                 return false;
  150.             }
  151.         };
  153.         // 当前结点是否NIL结点
  154.         var isNilLeaf: Bool {
  155.             get{
  157.                 if(self.data == nil && self.color == RBColor.Black && self.isLeaf){
  158.                     return true;
  159.                 }
  161.                 return false;
  162.             }
  163.         };
  165.         // 是否存在兄弟结点
  166.         var isExistSibling: Bool {
  167.             get{
  169.                 if(self.isRoot){
  170.                     return false;
  171.                 }
  173.                 return true;
  174.             }
  175.         };
  177.         // 获取兄弟结点
  178.         var sibling: RBNode? {
  179.             get{
  181.                 if(!self.isExistSibling){
  182.                     return nil;
  183.                 }
  185.                 if(self.isLeftChild){
  186.                     return self.parent!.rightChild;
  187.                 }
  189.                 return self.parent!.leftChild;
  190.             }
  191.         };
  193.         // 是否存在叔叔结点
  194.         var isExistUncle: Bool {
  195.             get{
  197.                 if(self.isRoot){
  198.                     return false;
  199.                 }
  201.                 if(self.parent!.isRoot){
  202.                     return false;
  203.                 }
  205.                 return true;
  206.             }
  207.         };
  209.         // 获取叔叔结点
  210.         var uncle: RBNode? {
  212.             if(!self.isExistUncle){
  213.                 return nil;
  214.             }
  216.             return self.parent!.sibling;
  217.         }
  218.     }
  219. }

4.2.3 添加元素

  1. class RBTree<Element: Comparable> {
  3.     fileprivate var _root: RBNode?;
  5.     // 添加元素
  6.     func add(data: Element) {
  8.         // 添加，返回新结点
  9.         let node = addNode(data: data);
  11.         // 新结点为空，添加失败，直接返回
  12.         if(node == nil){
  13.             return;
  14.         }
  16.         // 修复
  17.         addFixup(node: node!);
  18.     }
  20.     // 添加结点
  21.     fileprivate func addNode(data: Element) -> RBNode? {
  23.         // 根结点为空
  24.         if(_root == nil){
  25.             // 创建根结点
  26.             _root = RBNode(data: data, parent: nil);
  27.             return _root!;
  28.         }
  30.         var node = _root!;
  32.         while(!node.isNilLeaf) {
  34.             if(data < node.data!){
  36.                 if(node.leftChild!.isNilLeaf) {
  37.                     node.leftChild = RBNode(data: data, parent: node);
  38.                     return node.leftChild!;
  39.                 }
  41.                 node = node.leftChild!;
  42.                 continue;
  43.             }
  45.             if(node.rightChild!.isNilLeaf) {
  46.                 node.rightChild = RBNode(data: data, parent: node);
  47.                 return node.rightChild!;
  48.             }
  50.             node = node.rightChild!;
  51.         }
  53.         return nil;
  54.     }
  55. }

4.2.4 结点修复

  1. class RBTree<Element: Comparable> {
  3.     // 修复
  4.     fileprivate func addFixup(node: RBNode) {
  6.         // 当前结点为根结点
  7.         if(node.isRoot) {
  8.             // 着色为黑色
  9.             node.color = RBColor.Black;
  10.             // 直接返回
  11.             return;
  12.         }
  14.         // 没有父结点，直接返回
  15.         if(!node.isExistParent) {
  16.             return;
  17.         }
  19.         // 获取父结点
  20.         let parent = node.parent!;
  22.         // 【情况⼀（A）】新结点的⽗结点是⿊⾊结点，什么也不做
  23.         if(parent.color == RBColor.Black) {
  24.             return;
  25.         }
  27.         // 【情况⼀（B）】新结点的父结点是红色，但它同时作为根结点，直接将其颜色修改为黑色
  28.         if(parent.color == RBColor.Red && parent.isRoot){
  29.             parent.color = RBColor.Black;
  30.             return;
  31.         }
  33.         // 没有叔叔结点，或没有祖父结点，直接返回
  34.         if(!node.isExistUncle || !node.isExistGrandparent) {
  35.             return;
  36.         }
  38.         // 获取叔叔结点
  39.         let uncle = node.uncle!;
  40.         // 获取祖父结点
  41.         let grandparent = node.grandparent!;
  43.         // 【情况二】新结点的⽗结点是红⾊结点，它的叔叔结点是⿊⾊结点
  44.         if(parent.color == RBColor.Red && uncle.color == RBColor.Black){
  46.             // 保存当前结点
  47.             var currNode = node;
  49.             // 【情况二（C）】不在⼀边，先左旋
  50.             if(parent.isLeftChild && currNode.isRightChild) {
  51.                 // 左旋
  52.                 rotating(node: parent, rbRotating: RBRotating.Left);
  53.                 // 旋转后当前结点改变，更新当前结点
  54.                 currNode = parent;
  55.             }
  56.             // 【情况二（D）】不在⼀边，先右旋
  57.             else if(parent.isRightChild && currNode.isLeftChild) {
  58.                 // 右旋
  59.                 rotating(node: parent, rbRotating: RBRotating.Right);
  60.                 // 旋转后当前结点改变，更新当前结点
  61.                 currNode = parent;
  62.             }
  64.             // ⽗结点重新设置为⿊⾊
  65.             currNode.parent!.color = RBColor.Black;
  66.             // 祖父结点设置为红⾊
  67.             currNode.grandparent!.color = RBColor.Red;
  69.             // 【情况二（A）】父结点与新结点在同一边，⽗结点处沿插⼊结点的相反⽅向旋转，此时是右旋
  70.             if(currNode.isLeftChild) {
  71.                 rotating(node: currNode.grandparent!, rbRotating: RBRotating.Right);
  72.             }
  73.             // 【情况二（B）】父结点与新结点在同一边，⽗结点处沿插⼊结点的相反⽅向旋转，此时是左旋
  74.             else {
  75.                 rotating(node: currNode.grandparent!, rbRotating: RBRotating.Left);
  76.             }
  78.             return;
  79.         }
  81.         // 【情况三】新结点的⽗结点是红⾊结点，它的叔叔结点是红⾊结点。将⽗结点和叔结点重新着⾊为⿊⾊，将祖⽗结点重新着⾊为红⾊
  82.         if(parent.color == RBColor.Red && uncle.color == RBColor.Red) {
  84.             // 将⽗结点重新着⾊为⿊⾊
  85.             parent.color = RBColor.Black;
  86.             // 将叔叔结点重新着⾊为⿊⾊
  87.             uncle.color = RBColor.Black;
  88.             // 将祖⽗结点重新着⾊为红⾊
  89.             grandparent.color = RBColor.Red;
  91.             // 如果祖⽗结点着⾊为红⾊，有可能还会面临红色相连的结点，传入祖⽗结点进行递归修复
  92.             addFixup(node: grandparent);
  93.         }
  94.     }
  95. }

4.2.5 结点旋转

  1. class RBTree<Element: Comparable> {
  3.     // 旋转
  4.     fileprivate func rotating(node: RBNode, rbRotating: RBRotating) {
  6.         // 左旋
  7.         if(rbRotating == RBRotating.Left){
  9.             // 获取当前结点的右孩子
  10.             let rightNode = node.rightChild;
  12.             // 当前结点为根结点
  13.             if(node.isRoot){
  14.                 // 将根结点，赋值为当前结点的右孩子
  15.                 _root = rightNode;
  16.                 // 当前结点右孩子的父结点，赋值为nil
  17.                 rightNode?.parent = nil;
  18.             }
  19.             else {
  20.                 // 获取当前结点的父结点
  21.                 let parent = node.parent;
  23.                 // 判断当前结点是左孩子、还是右孩子
  24.                 if(node.isLeftChild){
  25.                     // 当前结点为左孩子，将父结点的左孩子，赋值为当前结点的右孩子
  26.                     parent?.leftChild = rightNode;
  27.                 }
  28.                 else{
  29.                     // 当前结点为右孩子，将父结点的右孩子，赋值为当前结点的右孩子
  30.                     parent?.rightChild = rightNode;
  31.                 }
  33.                 // 当前结点右孩子的父结点，赋值为父结点
  34.                 rightNode?.parent = parent;
  35.             }
  37.             // 获取当前结点右孩子的左孩子
  38.             let rightLeftNode = rightNode?.leftChild;
  39.             // 当前结点的右孩子，赋值为当前结点右孩子的左孩子
  40.             node.rightChild = rightLeftNode;
  41.             // 当前结点右孩子的左孩子的父结点，赋值为当前结点
  42.             rightLeftNode?.parent = node;
  44.             // 当前结点右孩子的左孩子，赋值为当前结点
  45.             rightNode?.leftChild = node;
  46.             // 当前结点的父结点，赋值为当前结点的右孩子
  47.             node.parent = rightNode;
  48.         }
  49.         // 右旋
  50.         else {
  52.             // 获取当前结点的左孩子
  53.             let leftNode = node.leftChild;
  55.             // 当前结点为根结点
  56.             if(node.isRoot){
  57.                 // 将根结点，赋值为当前结点的左孩子
  58.                 _root = leftNode;
  59.                 // 当前结点左孩子的父结点，赋值为nil
  60.                 leftNode?.parent = nil;
  61.             }
  62.             else {
  64.                 // 获取当前结点的父结点
  65.                 let parent = node.parent;
  67.                 // 判断当前结点是左孩子、还是右孩子
  68.                 if(node.isLeftChild){
  69.                     // 当前结点为左孩子，将父结点的左孩子，赋值为当前结点的左孩子
  70.                     parent?.leftChild = leftNode;
  71.                 }
  72.                 else{
  73.                     // 当前结点为右孩子，将父结点的右孩子，赋值为当前结点的左孩子
  74.                     parent?.rightChild = leftNode;
  75.                 }
  77.                 // 当前结点左孩子的父结点，赋值为父结点
  78.                 leftNode?.parent = parent;
  79.             }
  81.             // 获取当前结点左孩子的右孩子
  82.             let leftRightNode = leftNode?.rightChild;
  83.             // 当前结点的左孩子，赋值为当前结点左孩子的右孩子
  84.             node.leftChild = leftRightNode;
  85.             // 当前结点左孩子的右孩子的父结点，赋值为当前结点
  86.             leftRightNode?.parent = node;
  88.             // 当前结点左孩子的右孩子，赋值为当前结点
  89.             leftNode?.rightChild = node;
  90.             // 当前结点的父结点，赋值为当前结点的左孩子
  91.             node.parent = leftNode;
  92.         }
  93.     }
  94. }

4.2.6 红黑树打印

  1. class RBTree<Element: Comparable> {
  3.     func traverse() {
  5.         if(_root == nil){
  6.             print("[]");
  7.             return;
  8.         }
  10.         let str = traverse(node: _root!, top: "", root: "", bottom: "");
  11.         print("\(str)");
  12.     }
  14.     fileprivate func traverse(node: RBNode, top: String, root: String, bottom: String) -> String {
  16.         if (node.isNilLeaf) {
  17.             return "\(root)nil【\(node.colorFormat)】\n";
  18.         }
  20.         if (node.isLeaf) {
  21.             return "\(root)nil【\(node.colorFormat)】\n";
  22.         }
  24.         let ri = traverse(node: node.rightChild!, top: "\(top)    ", root: "\(top)┌───", bottom: "\(top)│   ");
  25.         let mi = "\(root)\(node.data!)【\(node.colorFormat)】\n";
  26.         let li = traverse(node: node.leftChild!, top: "\(bottom)│   ", root: "\(bottom)└───", bottom: "\(bottom)    ");
  28.         return "\(ri)\(mi)\(li)";
  29.     }
  30. }

5. 结点删除

普通二叉搜索树的删除操作：查找当前结点最近的前驱或者后继结点，进行替换

  • 前驱结点：对⼀棵⼆叉树进⾏中序遍历，遍历后的顺序，当前结点的前⼀个结点为该节点的前驱结点。左⼦树的最右结点

  • 后继节点：对⼀棵⼆叉树进⾏中序遍历，遍历后的顺序，当前结点的后⼀个节点为该结点的后继结点。右⼦树的最左结点

示例：删除结点7
image.png

  • 中序遍历：2，4，5，7，8，9

  • 选择最近的前驱结点5进行替换

红黑树的删除操作：

  • 删除结点为红⾊，正常删除，执行BST的删除逻辑即可

  • 删除结点为⿊⾊，⼦结点为红⾊，正常删除，执行BST的删除逻辑即可

  • 删除结点为⿊⾊，⼦结点也为⿊⾊，先执行BST的删除逻辑，再将当前位置的结点变为double black，缩写DB

5.1 思路分析

DB结点可以理解为一个占位结点，针对DB结点进行不同情况的后续处理。它的主要工作，就是将这个double black转换为single black

5.1.1 情况一

如果DB结点为根结点，或者DB结点的颜色为红色

  • 将DB节点变为正常节点，把颜⾊变为⿊⾊

5.1.2 情况二（A）

如果DB兄弟是⿊⾊的，并且DB兄弟孩⼦中的最远⼀个为红⾊
image.png

  • 交换DB⽗节点的颜⾊与DB兄弟的颜⾊

  • DB⽗节点向DB⽅向进⾏旋转

  • 将DB节点变为正常节点，把颜⾊变为⿊⾊

  • 将DB兄弟离DB最远的红⾊孩⼦节点变为⿊⾊

5.1.3 情况二（B）

如果兄弟是⿊⾊的，并且兄弟孩⼦中的最远⼀个为⿊⾊，最近的为红⾊
image.png

  • 交换DB兄弟节点和DB兄弟节点中红⾊孩⼦节点的颜⾊

  • DB兄弟节点向DB反⽅向进⾏旋转

  • 此时DB兄弟孩⼦中的最远⼀个为红⾊，按情况一（A）进行处理

5.1.4 情况二（C）

如果兄弟是⿊⾊的，并且兄弟孩⼦节点颜⾊为⿊⾊，DB⽗节点是红⾊
image.png

  • 将DB节点变为正常节点，把颜⾊变为⿊⾊

  • 将DB的兄弟节点变为红⾊

  • DB⽗节点是红⾊，将其变为⿊⾊

5.1.5 情况二（D）

如果兄弟是⿊⾊的，并且兄弟孩⼦节点颜⾊为⿊⾊，DB⽗节点是⿊⾊
image.png

  • 将DB节点变为正常节点，把颜⾊变为⿊⾊

  • 将DB的兄弟节点变为红⾊

  • 如果DB的⽗节点是⿊⾊，将其变为DB节点，继续进行祖⽗节点、兄弟结点、兄弟孩子结点的综合判断。满⾜哪种情况，进行相应的后续处理

5.1.6 情况三

如果DB兄弟是红⾊节点
image.png

  • 交换DB⽗节点与DB兄弟节点颜⾊

  • DB⽗节点向DB⽅向旋转

  • 观察此时满⾜哪种情况，进行相应的后续处理

5.2 代码实现

5.2.1 获取兄远 & 兄近

  1. class RBTree<Element: Comparable> {
  3.     fileprivate class RBNode: Equatable {
  5.         // 获取兄弟孩⼦中的最远⼀个
  6.         var siblingChildFar: RBNode? {
  8.             if(self.sibling!.isNilLeaf) {
  9.                 return nil;
  10.             }
  12.             if(self.isLeftChild) {
  13.                 return self.sibling!.rightChild;
  14.             }
  16.             return self.sibling!.leftChild;
  17.         }
  19.         // 获取兄弟孩⼦中的最近⼀个
  20.         var siblingChildNear: RBNode? {
  22.             if(self.sibling!.isNilLeaf) {
  23.                 return nil;
  24.             }
  26.             if(self.isLeftChild) {
  27.                 return self.sibling!.leftChild;
  28.             }
  30.             return self.sibling!.rightChild;
  31.         }
  32.     }
  33. }

5.2.2 查找元素

  1. class RBTree<Element: Comparable> {
  3.     // 找到指定元素所对应的结点
  4.     fileprivate func search(data: Element) -> RBNode? {
  6.         if(_root == nil) {
  7.             return nil;
  8.         }
  10.         var node = _root!;
  12.         while(!node.isNilLeaf) {
  14.             if(node.data! == data) {
  15.                 return node;
  16.             }
  18.             if(data > node.data!) {
  19.                 node = node.rightChild!;
  20.                 continue;
  21.             }
  23.             node = node.leftChild!;
  24.         }
  26.         return nil;
  27.     }
  28. }

5.2.3 删除元素

  1. class RBTree<Element: Comparable> {
  3.     // 删除元素
  4.     func delete(data: Element) {
  6.         // 寻找待删除元素
  7.         let node = search(data: data);
  9.         // 未找到
  10.         if(node == nil) {
  11.             // 直接返回
  12.             return;
  13.         }
  15.         // 删除结点
  16.         var delNode: RBNode?;
  17.         // DB结点
  18.         var dbNode: RBNode?;
  20.         // 如果待删除结点的左、右孩子都是NIL结点，或者其中一边为NIL结点
  21.         if(node!.leftChild!.isNilLeaf || node!.rightChild!.isNilLeaf) {
  23.             // 当前为根结点，并且左、右孩子都是NIL结点
  24.             if(node!.isRoot && node!.leftChild!.isNilLeaf && node!.rightChild!.isNilLeaf) {
  25.                 // 直接将根结点设置为空
  26.                 _root = nil;
  27.                 // 直接返回
  28.                 return;
  29.             }
  31.             // 寻找目标结点，如果左孩子是NIL结点，目标结点选择右孩子，否则选择左孩子
  32.             let target = node!.leftChild!.isNilLeaf ? node!.rightChild! : node!.leftChild!;
  34.             // 如果当前结点为根结点
  35.             if(node!.isRoot) {
  36.                 // 将根结点赋值为目标结点
  37.                 _root = target;
  38.                 // 将目标结点的父节点，设置为空
  39.                 target.parent = nil;
  40.             }
  41.             else {
  43.                 // 获取待删除结点的父节点
  44.                 let parent = node!.parent!;
  46.                 // 判断当前结点为左孩子
  47.                 if(node!.isLeftChild) {
  48.                     // 将父节点的左孩子，赋值为目标结点
  49.                     parent.leftChild = target;
  50.                 }
  51.                 else {
  52.                     // 将父节点的右孩子，赋值为目标结点
  53.                     parent.rightChild = target;
  54.                 }
  56.                 // 将目标结点的父节点，设置为待删除结点的父节点
  57.                 target.parent = parent;
  58.             }
  60.             // 删除结点为传入结点
  61.             delNode = node!;
  62.             // DB结点为目标结点
  63.             dbNode = target;
  64.         }
  65.         // 否则，左、右孩子都非NIL结点
  66.         else {
  68.             // 获取待删除结点的左子树
  69.             var target = node!.leftChild!;
  71.             // 找到直接前驱结点
  72.             while(!target.rightChild!.isNilLeaf) {
  73.                 target = target.rightChild!;
  74.             }
  76.             // 将待删除结点与直接前驱结点的值进行替换
  77.             node!.data = target.data;
  79.             // 获取直接前驱结点的左孩子
  80.             let targetLeft = target.leftChild!;
  82.             // 如果直接前驱结点的父节点就是待删除结点
  83.             if(target.parent == node) {
  84.                 // 将待删除结点的左孩子，赋值为直接前驱结点的左孩子
  85.                 node!.leftChild = targetLeft;
  86.                 // 将直接前驱结点左孩子的父节点，赋值为待删除结点
  87.                 targetLeft.parent = node;
  88.             }
  89.             else {
  90.                 // 获取直接前驱结点的父节点
  91.                 let targetParent = target.parent!;
  92.                 // 将父节点的右孩子，赋值为直接前驱结点的左孩子
  93.                 targetParent.rightChild = targetLeft;
  94.                 // 将直接前驱结点左孩子的父节点，赋值为父节点
  95.                 targetLeft.parent = targetParent;
  96.             }
  98.             // 删除结点为直接前驱结点
  99.             delNode = target;
  100.             // DB结点为直接前驱结点的左孩子
  101.             dbNode = targetLeft;
  102.         }
  104.         // 删除结点为红⾊，正常删除，执行BST的删除逻辑即可
  105.         if(delNode!.color == RBColor.Red) {
  106.             return;
  107.         }
  109.         // 删除结点为⿊⾊，⼦结点为红⾊，正常删除，执行BST的删除逻辑即可
  110.         if(delNode!.leftChild!.color == RBColor.Red && delNode!.rightChild!.color == RBColor.Red) {
  111.             return;
  112.         }
  114.         // 删除结点为⿊⾊，⼦结点也为⿊⾊，先执行BST的删除逻辑，再将当前位置的结点变为double black，缩写DB
  115.         deleteFixup(dbNode: dbNode!);
  116.     }
  117. }

5.2.4 结点修复

  1. class RBTree<Element: Comparable> {
  3.     // 修复
  4.     fileprivate func deleteFixup(dbNode: RBNode) {
  6.         // 情况一：如果DB结点为根结点，或者DB结点的颜色为红色
  7.         if(dbNode.isRoot || dbNode.color == RBColor.Red) {
  8.             // 将DB节点变为正常节点，把颜⾊变为⿊⾊
  9.             dbNode.color = RBColor.Black;
  10.             return;
  11.         }
  13.         if(!dbNode.isExistParent || !dbNode.isExistSibling){
  14.             return;
  15.         }
  17.         // 情况三：如果DB兄弟是红⾊节点
  18.         if(dbNode.sibling!.color == RBColor.Red) {
  20.             // 交换DB⽗节点与DB兄弟节点颜⾊
  21.             let tempColor = dbNode.parent!.color;
  22.             dbNode.parent!.color = dbNode.sibling!.color;
  23.             dbNode.sibling!.color = tempColor;
  25.             // 获取父节点
  26.             let parent = dbNode.parent!;
  27.             // DB⽗节点向DB⽅向旋转
  28.             if(dbNode.isLeftChild) {
  29.                 rotating(node: parent, rbRotating: RBRotating.Left);
  30.             }
  31.             else {
  32.                 rotating(node: parent, rbRotating: RBRotating.Right);
  33.             }
  35.             // 观察此时满⾜哪种情况，进行相应的后续处理
  36.             deleteFixup(dbNode: dbNode);
  37.             return;
  38.         }
  40.         if(dbNode.sibling!.isNilLeaf) {
  41.             return;
  42.         }
  44.         // 情况二（A）：如果DB兄弟是⿊⾊的，并且DB兄弟孩⼦中的最远⼀个为红⾊
  45.         if(dbNode.siblingChildFar!.color == RBColor.Red) {
  47.             // 交换DB⽗节点的颜⾊与DB兄弟的颜⾊
  48.             let tempColor = dbNode.parent!.color;
  49.             dbNode.parent!.color = dbNode.sibling!.color;
  50.             dbNode.sibling!.color = tempColor;
  52.             // 将DB节点变为正常节点，把颜⾊变为⿊⾊
  53.             dbNode.color = RBColor.Black;
  54.             // 将DB兄弟离DB最远的红⾊孩⼦节点变为⿊⾊
  55.             dbNode.siblingChildFar!.color = RBColor.Black;
  57.             // 获取父节点
  58.             let parent = dbNode.parent!;
  59.             // DB⽗节点向DB⽅向进⾏旋转
  60.             if(dbNode.isLeftChild) {
  61.                 rotating(node: parent, rbRotating: RBRotating.Left);
  62.             }
  63.             else {
  64.                 rotating(node: parent, rbRotating: RBRotating.Right);
  65.             }
  67.             return;
  68.         }
  70.         // 情况二（B）：如果兄弟是⿊⾊的，并且兄弟孩⼦中的最远⼀个为⿊⾊，最近的为红⾊
  71.         if(dbNode.siblingChildNear!.color == RBColor.Red) {
  73.             // 交换DB兄弟节点和DB兄弟节点中红⾊孩⼦节点的颜⾊
  74.             let tempColor = dbNode.sibling!.color;
  75.             dbNode.sibling!.color = dbNode.siblingChildNear!.color;
  76.             dbNode.siblingChildNear!.color = tempColor;
  78.             // 获取兄弟结点
  79.             let sibling = dbNode.sibling!;
  80.             // DB兄弟节点向DB反⽅向进⾏旋转
  81.             if(dbNode.isLeftChild) {
  82.                 rotating(node: sibling, rbRotating: RBRotating.Right);
  83.             }
  84.             else {
  85.                 rotating(node: sibling, rbRotating: RBRotating.Left);
  86.             }
  88.             // 此时DB兄弟孩⼦中的最远⼀个为红⾊，按情况一（A）进行处理
  89.             deleteFixup(dbNode: dbNode);
  91.             return;
  92.         }
  94.         // 情况二（C）：如果兄弟是⿊⾊的，并且兄弟孩⼦节点颜⾊为⿊⾊，DB⽗节点是红⾊
  95.         if(dbNode.parent!.color == RBColor.Red) {
  97.             // 将DB节点变为正常节点，把颜⾊变为⿊⾊
  98.             dbNode.color = RBColor.Black;
  99.             // 将DB的兄弟节点变为红⾊
  100.             dbNode.sibling!.color = RBColor.Red;
  101.             // DB⽗节点是红⾊，将其变为⿊⾊
  102.             dbNode.parent!.color = RBColor.Black;
  103.             return;
  104.         }
  106.         // 情况二（D）：如果兄弟是⿊⾊的，并且兄弟孩⼦节点颜⾊为⿊⾊，DB⽗节点是⿊⾊
  108.         // 将DB节点变为正常节点，把颜⾊变为⿊⾊
  109.         dbNode.color = RBColor.Black;
  110.         // 将DB的兄弟节点变为红⾊
  111.         dbNode.sibling!.color = RBColor.Red;
  112.         // 如果DB的⽗节点是⿊⾊，将其变为DB节点，继续进行祖⽗节点、兄弟结点、兄弟孩子结点的综合判断。满⾜哪种情况，进行相应的后续处理
  113.         deleteFixup(dbNode: dbNode.parent!);
  114.     }
  115. }

总结

概述：

  • 红⿊树（R-B Tree）是由Rudolf Bayer在1972发明。是⼀种⾃平衡⼆叉搜索树，其中每个结点都有⼀个额外的位，存储该结点的颜⾊（红⾊或⿊⾊）

  • 是2-3-4树的变种，2-3-4树的每一个结点都对应红黑树的一种结构，所以每一棵2-3-4树也都对应一棵红黑树

结点插入：

  • 标准⼆叉搜索树，搜索找到要添加的位置

  • 执⾏替换，颜⾊设置为红⾊

  • 新结点添加叶⼦结点（NIL结点），颜⾊设置为⿊⾊

  • 如果该⽗结点也为红⾊，需要修复

  • 如何修复取决于⽗结点的sibling（兄弟结点）

结点删除：

  • 删除结点为红⾊，正常删除，执行BST的删除逻辑即可

  • 删除结点为⿊⾊，⼦结点为红⾊，正常删除，执行BST的删除逻辑即可

  • 删除结点为⿊⾊，⼦结点也为⿊⾊，先执行BST的删除逻辑，再将当前位置的结点变为double black，缩写DB

  • DB结点可以理解为一个占位结点，针对DB结点进行不同情况的后续处理。它的主要工作，就是将这个double black转换为single black

学习资料：

数据结构可视化：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

Swift算法俱乐部：https://aquarchitect.github.io/swift-algorithm-club/