数据结构算法 - 红黑树

Dear 丶 2023-02-21 06:09 86阅读 0赞

红黑树是一棵自平衡的二叉搜索树，因此在学习红黑树之前，我们需要回顾一下之前所学的知识
二叉搜索树和平衡二叉树。

1、二叉搜索树

二叉搜索树又叫二叉查找树或者二叉排序树，它首先是一个二叉树，而且必须满足下面的条件：

  1. 1）若左子树不空，则左子树上所有结点的值均小于它的根节点的值；
  3. 2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值
  5. 3）左、右子树也分别为二叉搜索树

二叉搜索树示例
在这里插入图片描述

2、平衡二叉树

二叉搜索树解决了许多问题，比如可以快速的查找最大值和最小值，可以快速找到排名第几位的值，快速搜索和排序等等。但普通的二叉搜索树有可能出现极不平衡的情况（斜树），这样我们的时间复杂度就有可能退化成 O(N) 的情况。比如我们现在插入的数据是 [1,2,3,4,5,6,7] 转换为二叉树如下：

斜树
在这里插入图片描述
由于普通的二叉搜索树会出现极不平衡的情况，那么我们就必须得想想办法了，这个时候平衡二叉树就能帮到我们了。什么是平衡二叉树？平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

平衡二叉树有一个很重要的性质：左右两个子树的高度差的绝对值不超过1。那么解决方案就是如果二叉树的左右高度超过 1 ，我们就把当前树调整为一棵平衡二叉树。这就涉及到左旋、右旋、先右旋再左旋、先左旋再右旋。

2.1 右旋：
在这里插入图片描述

  1. TreeNode<K, V> *R_Rotation(TreeNode<K, V> *pNode) { 
  2.         TreeNode<K, V> *left = pNode->left;
  3.         TreeNode<K, V> *right = left->right;
  4.         left->right = pNode;
  5.         pNode->left = right;
  6.         // 重新调整高度
  7.         pNode->height = max(getHeight(pNode->left), getHeight(pNode->right)) + 1;
  8.         left->height = max(getHeight(left->left), getHeight(left->right)) + 1;
  9.         return left;
  10.     }

2.2 左旋：
在这里插入图片描述

  1. TreeNode<K, V> *L_Rotation(TreeNode<K, V> *pNode) { 
  2.         TreeNode<K, V> *right = pNode->right;
  3.         TreeNode<K, V> *left = right->left;
  4.         right->left = pNode;
  5.         pNode->right = left;
  6.         // 重新调整高度
  7.         pNode->height = max(getHeight(pNode->left), getHeight(pNode->right)) + 1;
  8.         right->height = max(getHeight(right->left), getHeight(right->right)) + 1;
  9.         return right;
  10.     }

2.3 先右旋再左旋：
先右旋再左旋

  1. TreeNode<K, V> *R_L_Rotation(TreeNode<K, V> *pNode) { 
  2.     pNode->right = R_Rotation(pNode->right);
  3.     return L_Rotation(pNode);
  4.   }

2.4 先左旋再右旋：
先左旋再右旋

  1. TreeNode<K, V> *L_R_Rotation(TreeNode<K, V> *pNode) { 
  2.     pNode->left = L_Rotation(pNode->left);
  3.     return R_Rotation(pNode);
  4.   }

3、红黑树

红黑树用法就比较广了，比如 JDK 1.8 的 HashMap，TreeMap，C++ 中的 map 和 multimap 等等。红黑树学习起来还是有一点难度的，这时如果我们心中有 B 树就有助于理解它，如果没有 B 树也没有关系。

红黑树的特性:
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
在这里插入图片描述

假设我们现在要插入一个新的节点，如过插入的这个新的节点为黑色，那么必然会违反性质(5)，所以我们把新插入的点定义为红色的。但是如果插入的新节点为红色，就可能会违反性质(4) ，因此我们需要对其进行调整，使得整棵树依然满足红黑树的性质，也就是双红修正。接下来我们只要分情况分析就可以了：

  1. 1、如果没有出现双红现象，父亲是黑色的不需要修正；
  2. 2、叔叔是红色的 ，将叔叔和父亲染黑，然后爷爷染红；
  3. 3、叔叔是黑色的，父亲是爷爷的左节点，且当前节点是其父节点的右孩子，将“父节点”作为“新的当前节点”，
  4.     以“新的当前节点”为支点进行左旋。然后将“父节点”设为“黑色”，将“祖父节点”设为“红色”，
  5.     以“祖父节点”为支点进行右旋；
  6. 4、叔叔是黑色的，父亲是爷爷的左节点，且当前节点是其父节点的左孩子，将“父节点”设为“黑色”，
  7.     将“祖父节点”设为“红色”，以“祖父节点”为支点进行右旋；
  8. 5、叔叔是黑色的，父亲是爷爷的右节点，且当前节点是其父节点的左孩子，将“父节点”作为“新的当前节点”，
  9.     以“新的当前节点”为支点进行右旋。然后将“父节点”设为“黑色”，将“祖父节点”设为“红色”，
  10.     以“祖父节点”为支点进行左旋；
  11. 6、叔叔是黑色的，父亲是爷爷的右节点，且当前节点是其父节点的右孩子，将“父节点”设为“黑色”，
  12.     将“祖父节点”设为“红色”，以“祖父节点”为支点进行左旋；

上面的双红修正现象看似比较复杂，但实际上只有三种情况，一种是没有双红现象，另一种是父亲和叔叔都是红色的，最后一种是叔叔是黑色的。我们来画个实例看下：

在这里插入图片描述

  1. void solveDoubleRed(TreeNode *pNode) { 
  2.         while (pNode->parent && pNode->parent->color == red) { // 情况 1
  3.             TreeNode *uncle = brother(parent(pNode));
  5.             if (getColor(uncle) == red) { // 情况2
  6.                 // 设置双亲和叔叔为黑色
  7.                 setColor(parent(pNode), black);
  8.                 setColor(uncle, black);
  9.                 // 指针回溯至爷爷
  10.                 pNode = parent(parent(pNode));
  11.             } else { 
  12.                 // 父亲是爷爷的左儿子
  13.                 if (parent(parent(pNode))->left = parent(pNode)) {  // 情况 3 和 4
  14.                     // 自己是父亲的右儿子
  15.                     if (parent(pNode)->right == pNode) { 
  16.                         pNode = parent(pNode);
  17.                         L_Rotation(pNode);
  18.                     }
  19.                     // 把我自己这边的红色节点挪到隔壁树上，但仍然不能违反性质 4 和 5
  20.                     setColor(parent(pNode), black);
  21.                     setColor(parent(parent(pNode)), red);
  22.                     R_Rotation(parent(parent(pNode)));
  23.                 } else {  // 情况 5 和 6
  24.                     // 自己是父亲的左儿子
  25.                     if (parent(pNode)->left == pNode) { 
  26.                         pNode = parent(pNode);
  27.                         R_Rotation(pNode);
  28.                     }
  29.                     // 把我自己这边的红色节点挪到隔壁树上，但仍然不能违反性质 4 和 5
  30.                     setColor(parent(pNode), black);
  31.                     setColor(parent(parent(pNode)), red);
  32.                     L_Rotation(parent(parent(pNode)));
  33.                 }
  34.             }
  35.         }
  37.         // 根结点为黑色
  38.         root->color = black;
  39.     }

哎～好复杂这怎么记得住。如果要记住肯定不太可能而且费劲，接下来我们来分析下为什么要这么操作，还有没有更好的调整方法。我们所有的调整都是为了不违反性质4和性质5，假设我在左边的这个支树上新增了一个红色的节点，违反了性质4 。想法就是我把左支树上的一个红色节点，挪动右支树上去，这样就解决了我有两个连续红色节点的问题。但挪给右支树的过程中不能违反性质4和性质5，所以必须得考虑叔叔节点的颜色。
在这里插入图片描述

最后我们来看下红黑树的删除操作，红黑树的删除操作要比新增操作要复杂些，但总体来说都是出现问题就去解决问题。当我们移除的是一个红色节点，那么根本就不会影响我们的性质4和性质5，我们不需要调整，但倘若我们移除的是一个黑色的节点，这时肯定会违反我们的性质5，所以我们只需要调整移除黑色节点的情况。分情况讨论下：

  1. 1、如果兄弟节点是红色的，把兄弟节点染黑，父节点染红，左/右旋父节点；
  2. 2、如果兄弟节点是黑色的，并且两个侄子节点都是黑色的，将兄弟节点染红，指针回溯至父亲节点；
  3. 3、如果兄弟节点是黑色，的并且远侄子是黑色的，近侄子是红色的，将进侄子染黑，兄弟染红，
  4.     左/右旋兄弟节点，进入下面情况 4 ；
  5. 4、如果兄弟节点是黑色的，并且远侄子是红色的，近侄子随意，将兄弟节点染成父亲节点的颜色，
  6.     父亲节点染黑，远侄子染黑，左/右旋父亲节点。

在这里插入图片描述

  1. void solveLostBlack(TreeNode *pNode) { 
  2.         while (pNode != root && getColor(pNode) == black) { 
  3.             if (left(parent(pNode)) == pNode) { 
  4.                 TreeNode *sib = brother(pNode);
  5.                 if (getColor(sib) == red) { 
  6.                     setColor(sib, black);
  7.                     setColor(parent(pNode), red);
  8.                     L_Rotation(parent(pNode));
  9.                     sib = brother(pNode);
  10.                 }
  12.                 if (getColor(left(sib)) == black && getColor(right(sib)) == black) { 
  13.                     setColor(sib, red);
  14.                     pNode = parent(pNode);
  15.                 } else { 
  16.                     if (getColor(right(sib)) == black) { 
  17.                         setColor(left(sib), black);
  18.                         setColor(sib, red);
  19.                         R_Rotation(sib);
  20.                         sib = brother(pNode);
  21.                     }
  23.                     setColor(sib, getColor(parent(pNode)));
  24.                     setColor(parent(pNode), black);
  25.                     setColor(right(sib), black);
  26.                     L_Rotation(parent(pNode));
  27.                     pNode = root;
  28.                 }
  29.             } else { 
  30.                 TreeNode *sib = brother(pNode);
  31.                 if (getColor(sib) == red) { 
  32.                     setColor(sib, black);
  33.                     setColor(parent(pNode), red);
  34.                     R_Rotation(parent(pNode));
  35.                     sib = brother(pNode);
  36.                 }
  38.                 if (getColor(left(sib)) == black && getColor(right(sib)) == black) { 
  39.                     setColor(sib, red);
  40.                     pNode = parent(pNode);
  41.                 } else { 
  42.                     if (getColor(left(sib)) == black) { 
  43.                         setColor(right(sib), black);
  44.                         setColor(sib, red);
  45.                         L_Rotation(sib);
  46.                         sib = brother(pNode);
  47.                     }
  49.                     setColor(sib, getColor(parent(pNode)));
  50.                     setColor(parent(pNode), black);
  51.                     setColor(left(sib), black);
  52.                     R_Rotation(parent(pNode));
  53.                     pNode = root;
  54.                 }
  55.             }
  56.         }
  57.         pNode->color = black;
  58.     }

发表评论

表情：
评论列表 （有 0 条评论，86人围观）

还没有评论，来说两句吧...

相关阅读

    相关 数据结构算法 - 红黑树

    红黑树是一棵自平衡的二叉搜索树，因此在学习红黑树之前，我们需要回顾一下之前所学的知识 二叉搜索树和平衡二叉树。 1、二叉搜索树 二叉搜索树又叫二叉查找树或者二叉排序

    Dear 丶Dear 丶/ 0 赞/ 87 阅读

    相关 【数据结构】红黑树

    一. 红黑树的概念 红黑树是一颗二叉搜索树，它的每个结点增加一个存储单位来表示结点的颜色，这个颜色是red或者black，通过对任何一条从根结点到叶子结点上的颜色来约束，

    喜欢ヅ旅行喜欢ヅ旅行/ 0 赞/ 322 阅读

    相关 数据结构 - 红黑树

    数据结构 - 红黑树 - 面试常问知识点 数据结构是面试中必定考查的知识点，面试者需要掌握几种经典的数据结构：线性表（数组、链表）、栈与队列、树（二叉树、二叉查找树、平衡

    我会带着你远行我会带着你远行/ 0 赞/ 300 阅读

    相关 数据结构_红黑树

    红黑树 红黑树也是属于一种BBST。在之前介绍的[伸展树][Link 1]中，虽然实现简单，分摊复杂度低，但是最坏情况下的操作需要O(n)时间，无法适用于对单次效率敏感的

    ╰半夏微凉°╰半夏微凉°/ 0 赞/ 303 阅读

    相关 数据结构--红黑树

    为什么要平衡 在上一节中，我们了解了 `二叉搜索树` 具有较稳定和较高的插入搜索效率。但是在某些极端情况下， 它的效率也会退化到 `链表` 的地步。 ![2018122

    水深无声水深无声/ 0 赞/ 288 阅读