红黑树(更高级的二叉查找树)

目录

介绍及性质

红黑树的基本定义

黑高度

时间复杂度

接近于“平衡”操作

红黑树的旋转

红黑树中插入新结点

红黑树中删除结点

红黑树与AVL树的区别

• 介绍及性质

• 红黑树（R-B TREE，全称：Red-Black Tree），本身是一棵二叉查找树，在其基础上附加了两个要求：
  • 1. 树中的每个结点增加了一个用于存储颜色的标志域；
  • 2. 树中没有一条路径比其他任何路径长出两倍，整棵树要接近于“平衡”的状态
• 这里所指的路径，指的是从任何一个结点开始，一直到其子孙的叶子结点的长度；
• 接近于平衡：红黑树并不是平衡二叉树，只是由于对各路径的长度之差有限制，所以近似于平衡的状态
• 红黑树对于结点的颜色设置不是任意的，需满足以下性质的二叉查找树才是红黑树：
  • 树中的每个结点颜色不是红的，就是黑的；
  • 根结点的颜色是黑的；
  • 所有为 nil 的叶子结点的颜色是黑的；（注意：叶子结点说的只是为空（nil 或 NULL）的叶子结点！）
  • 如果此结点是红的，那么它的两个孩子结点全部都是黑的；
  • 对于每个结点，从该结点到到该结点的所有子孙结点的所有路径上包含有相同数目的黑结点；

    

• 哪些性质反映了红黑树结构的平衡？
• 性质5 反映了红黑树结构的平衡
• 它确保从任意一个节点出发到其叶子节点的所有路径中，最长路径长度也不会超过最短路径长度的两倍；因而，红黑树是相对接近平衡的二叉树
• 而且性质5 明显指出每个节点的左右子树中黑节点的层数是相等的，因此红黑树的黑节点是完美平衡的

• 红黑树的基本定义

  

• 

• 黑高度

• 注意：图中每个结点附带一个整形数值，表示的是此结点的黑高度（从该结点到其子孙结点中包含的黑结点数，用 bh(x) 表示（x 表示此结点））
• nil 的黑高度为 0，颜色为黑色（在编程时为节省空间，所有的 nil 共用一个存储空间）
• 在计算黑高度时，也看做是一个黑结点
• 红黑树中每个结点都有各自的黑高度，整棵树也有自己的黑高度，即为根结点的黑高度，例如图中的红黑树的黑高度为 3

• 时间复杂度

• 对于一棵具有 n 个结点的红黑树，树的高度至多为：2lg(n+1)
• 由此可推出红黑树进行查找操作时的时间复杂度为 O(lgn)，因为对于高度为 h 的二叉查找树的运行时间为 O(h)，而包含有 n 个结点的红黑树本身就是最高为 lgn（简化之后）的查找树（h=lgn），所以红黑树的时间复杂度为 O(lgn)

• 接近于“平衡”操作

• 红黑树本身作为一棵二叉查找树，所以其任务就是用于动态表中数据的插入和删除的操作
• 在进行该操作时，避免不了会破坏红黑树的结构，此时就需要进行适当的调整，使其重新成为一棵红黑树，可以从两个方面着手对树进行调整：
  • 调整树中某些结点的指针结构；
  • 调整树中某些结点的颜色；

• 红黑树的旋转

• 当使用红黑树进行插入或者删除结点的操作时，可能会破坏红黑树的 5 条性质，从而变成了一棵普通树
• 此时就可以通过对树中的某些子树进行旋转，从而使整棵树重新变为一棵红黑树
• 旋转操作分为左旋和右旋

  

• 左旋：如图所示，左旋时 y 结点变为该部分子树的根结点，同时 x 结点（连同其左子树 a）移动至 y 结点的左孩子
• 若 y 结点有左孩子 b，由于 x 结点需占用其位置，所以调整至 x 结点的右孩子处

  

• 
• 右旋：如图所示，同左旋是同样的道理，x 结点变为根结点，同时 y 结点连同其右子树 c 作为 x 结点的右子树，原 x 结点的右子树 b 变为 y 结点的左子树

  

• 

• 红黑树中插入新结点

• 为什么新插入的节点颜色是红的？
• 将新插入的节点着色为红色，不会违背特性5
• 少违背一条特性，就意味着我们需要处理的情况越少
• 当创建一个红黑树或者向已有红黑树中插入新的数据时，只需要按部就班地执行以下 3 步：
  • 由于红黑树本身是一棵二叉查找树，所以在插入新的结点时，完全按照二叉查找树插入结点的方法，找到新结点插入的位置；
  • 将新插入的结点结点初始化，颜色设置为红色后插入到指定位置；（将新结点初始化为红色插入后，不会破坏红黑树第 5 条的性质）
  • 由于插入新的结点，可能会破坏红黑树第 4 条的性质（若其父结点颜色为红色，就破坏了红黑树的性质），此时需要调整二叉查找树，想办法通过旋转以及修改树中结点的颜色，使其重新成为红黑树！
• 插入结点的第 1 步和第 2 步都非常简单，关键在于最后一步对树的调整！
• 在红黑树中插入结点时，根据插入位置的不同可分为以下 3 种情况：
• 1. 插入位置为整棵树的树根；处理办法：只需要将插入结点的颜色改为黑色即可
• 2. 插入位置的双亲结点的颜色为黑色；处理方法：此种情况不需要做任何工作，新插入的颜色为红色的结点不会破坏红黑树的性质
• 3. 插入位置的双亲结点的颜色为红色；处理方法：由于插入结点颜色为红色，其双亲结点也为红色，破坏了红黑树第 4 条性质，此时需要结合其祖父结点和祖父结点的另一个孩子结点（父结点的兄弟结点，此处称为“叔叔结点”）的状态，分为 3 种情况讨论:
  • 当前结点的父节点是红色，且“叔叔结点”也是红色：破坏了红黑树的第 4 条性质，解决方案为：将父结点颜色改为黑色；将叔叔结点颜色改为黑色；将祖父结点颜色改为红色；下一步将祖父结点认做当前结点，继续判断，处理结果如下图所示

    

    • 分析：此种情况下，由于父结点和当前结点颜色都是红色，所以为了不产生冲突，将父结点的颜色改为黑色
    • 但是虽避免了破坏第 4 条，但是却导致该条路径上的黑高度增加了 1 ，破坏了第 5 条性质
    • 但是在将祖父结点颜色改为红色、叔叔结点颜色改为黑色后，该部分子树没有破坏第 5 条性质
    • 但是由于将祖父结点的颜色改变，还需判断是否破坏了上层树的结构，所以需要将祖父结点看做当前结点，继续判断
  • 当前结点的父结点颜色为红色，叔叔结点颜色为黑色，且当前结点是父结点的右孩子；解决方案：将父结点作为当前结点做左旋操作

    

    • 提示：在进行以父结点为当前结点的左旋操作后，此种情况就转变成了第 3 种情况，处理过程跟第 3 种情况同步进行
  • 当前结点的父结点颜色为红色，叔叔结点颜色为黑色，且当前结点是父结点的左孩子；解决方案：将父结点颜色改为黑色，祖父结点颜色改为红色，从祖父结点处进行右旋处理；如下图所示：

    

    • 分析：在此种情况下，由于当前结点 F 和父结点 S 颜色都为红色，违背了红黑树的性质 4，此时可以将 S 颜色改为黑色，有违反了性质 5，因为所有通过 S 的路径其黑高度都增加了 1 ，所以需要将其祖父结点颜色设为红色后紧接一个右旋，这样这部分子树有成为了红黑树（上图中的有图虽看似不是红黑树，但是只是整棵树的一部分，以 S 为根结点的子树一定是一棵红黑树）
• 内部接口 -- insert(node)的作用是将"node"节点插入到红黑树中
• 外部接口 -- insert(key)的作用是将"key"添加到红黑树中

  

• 

•  

• 

• 

• 

• 

• 

• 红黑树中删除结点

• 在红黑树中删除结点，思路更简单，只需要完成 2 步操作：
  • 1. 将红黑树按照二叉查找树删除结点的方法删除指定结点；
  • 2. 重新调整删除结点后的树，使之重新成为红黑树；（还是通过旋转和重新着色的方式进行调整）
• 在二叉查找树删除结点时，分为 3 种情况：
  • 若该删除结点本身是叶子结点，则可以直接删除；
  • 若只有一个孩子结点（左孩子或者右孩子），则直接让其孩子结点顶替该删除结点；
  • 若有两个孩子结点，则找到该结点的右子树中值最小的叶子结点来顶替该结点，然后删除这个值最小的叶子结点
• 以上三种情况最终都需要删除某个结点，此时需要判断删除该结点是否会破坏红黑树的性质，判断的依据是：
  • 1. 如果删除结点的颜色为红色，则不会破坏；
  • 2. 如果删除结点的颜色为黑色，则肯定会破坏红黑树的第 5 条性质，此时就需要对树进行调整，调整方案分 4 种情况讨论：
    • 删除结点的兄弟结点颜色是红色，调整措施为：将兄弟结点颜色改为黑色，父亲结点改为红色，以父亲结点来进行左旋操作，同时更新删除结点的兄弟结点（左旋后兄弟结点发生了变化），如下图所示：

      

    • 删除结点的兄弟结点及其孩子全部都是黑色的，调整措施为：将删除结点的兄弟结点设为红色，同时设置删除结点的父结点标记为新的结点，继续判断；
    • 删除结点的兄弟结点是黑色，其左孩子是红色，右孩子是黑色。调整措施为：将兄弟结点设为红色，兄弟结点的左孩子结点设为黑色，以兄弟结点为准进行右旋操作，最终更新删除结点的兄弟结点；
    • 删除结点的兄弟结点是黑色，其右孩子是红色（左孩子不管是什么颜色），调整措施为：将删除结点的父结点的颜色赋值给其兄弟结点，然后再设置父结点颜色为黑色，兄弟结点的右孩子结点为黑色，根据其父结点做左旋操作，最后设置替换删除结点的结点为根结点；
• 红黑树，虽隶属于二叉查找树，但是二叉查找树的时间复杂度会受到其树深度的影响，而红黑树可以保证在最坏情况下的时间复杂度仍为 O(lgn)
• 当数据量多到一定程度时，使用红黑树比二叉查找树的效率要高
• 内部接口 -- remove(node)的作用是将"node"节点插入到红黑树中
• 外部接口 -- remove(key)删除红黑树中键值为key的节点

  

• 

• 

• 

•  

• 

• 

•  

• 

• 

• 

• 

• 红黑树与AVL树的区别

• 1---为什么红黑树比 AVL 树更受欢迎？
• 红黑树的平衡条件相对宽松，因此在红黑树中插入与删除结点所需的旋转操作相对更少，结点增删操作相比 AVL 树的效率更高
• 2---和红黑树相比，AVL树是严格的平衡二叉树，平衡条件必须满足（所有节点的左右子树高度差不超过1）；不管是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保持平衡，而旋转是非常耗时的，由此可以知道AVL树适合用于插入与删除次数比较少，但查找多的情况
• 3---AVL树追求绝对平衡，条件比较苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知
• 4---由于维护这种高度平衡所付出的代价比从中获得的效率收益还大，故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树；当然，如果应用场景中对插入、删除不频繁，只是对查找要求较高，那么AVL还是较优于红黑树
• 5---相较红黑树AVL树查找性能更快
• 6---红黑树放弃了追求完全平衡，而是追求大致平衡，在与AVL树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，维持平衡的时间消耗较少，实现起来也更为简单
• 7---相对于要求严格平衡的AVL树来说，它的旋转次数少，对于插入、删除操作较多的情况下，选择红黑树
• 8---红黑树的查询性能略微逊色于AVL树，因为其比AVL树会稍微不平衡最多一层，也就是说红黑树的查询性能只比相同内容的AVL树最多多一次比较，但是，红黑树在插入和删除上优于AVL树，AVL树每次插入删除会进行大量的平衡度计算，而红黑树为了维持红黑性质所做的红黑变换和旋转的开销，相较于AVL树为了维持平衡的开销要小得多