CcbeanBlog
ccbean
2022-01-05
目录

数据结构与算法-红黑树（一）

# 数据结构与算法 - 红黑树

红黑树保证了最坏情形下在 O(logN) 时间复杂度内完成查找、插入及删除操作。

# 红黑树的五条规则

红黑树本质上是一个二叉搜索树树，它是在二叉搜索树的基础上给节点增加红黑颜色属性以及五条规则：

  • 规则1：节点是红色或黑色的；
  • 规则2：根节点是黑色的；
  • 规则3：每个叶子节点都是黑色的空节点（NIL节点）；
  • 规则4：每个红色节点的两个子节点都是黑色的（从每个叶子到根的所有路径上不可能有两个连续的红色节点）；
  • 规则5：从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点；

红黑树01

# 红黑树的相对平衡

前面5条规则的约束确保了以下红黑树的关键特性：

  • 从根到叶子节点的最长路径，不会超过最短路径的两倍；
  • 结果就是这棵树基本是平衡的；
  • 虽然没有做到绝对的平衡，但是可以保证在最坏的情况下，该树依然是高效的；

为什么可以做到最长路径不超过最短路径的两倍呢？

  • 性质4决定了路径上不能有两个相连的红色节点，所以，最长路径一定是红色节点和黑色节点交替而成的；
  • 由于根节点和叶子节点都是黑色的，最短路径可能都是黑色节点，并且最长路径中一定是黑色节点多于红色节点；
  • 性质5决定了所有路径上都有相同数目的黑色节点；而黑色节点一定比红色节点多，这就表明了没有路径能多于其他任何路径两倍长。

总结：红黑树的五个性质避免了二叉查找树退化成单链表的情况，并且性质 4 和性质 5 确保了任意节点到其每个叶子节点路径中最长路径不会超过最短路径的 2 倍，即一颗树是黑红节点相间的树，另一颗全是黑节点的树；也就是红黑树是相对黑色节点的平衡二叉树。

# 变色和旋转

红黑树节点的插入和删除可能会破坏上述红黑树的性质并打破它的平衡，因此需要进行调整从而让红黑树重新恢复平衡；

调整分两种方式：

  • 变色

  • 旋转，旋转又分为左旋转和又旋转。

这里我们先抛开红黑树，单独来理解变色和旋转。

# 变色

为了重新符合红黑树的规则，需要把红色节点变为黑色，或者把黑色节点变为红色；

插入的新节点通常都是红色节点：

  • 当插入的节点为红色的时候，有可能插入一次是不违反红黑树的任何规则的；
  • 而插入黑色节点，必然会导致一条路径上多了一个黑色节点，这是很难调整的；
  • 红色节点虽然可能导致红红相连的情况，但是这种情况可以通过颜色调换和旋转来调整；

假如上图要插入一个节点14：

  • 红色14情况下，直接将节点插入到黑色节点15的左子树，然后补充节点14的两个叶子节点Nil即可。
  • 黑色14情况下，插入到同样位置，则不满足规则5，那么需要变色，将黑色14变为红色，那么不如直接插入红色节点14。

假如上图要插入一个节点21：

  • 当插入是红色21，节点会插入到22的左子树，此时出现了红红相连的情况，那么通过变色和旋转可解决，对应下面插入的情况4
  • 但如果插入的是黑色21，不满足规则5，还是要将黑色21先变成红色，再做红色情况的处理，那么不如直接插入红色。

# 左旋转

以节点X为根逆时针旋转二叉搜索树，使得父节点原来的位置被自己的右子节点替代，左子节点的位置被父节点替代；

红黑树02

如上图所示，左旋转之后：

  • 节点X取代了节点a原来的位置；
  • 节点Y取代了节点X原来的位置；
  • 节点X的左子树 a 仍然是节点X的左子树（这里X的左子树只有一个节点，有多个节点时同样适用，以下同理）；
  • 节点Y的右子树 c 仍然是节点Y的右子树；
  • 节点Y的左子树 b 向左平移成为了节点X的右子树；

左旋转后仍满足二叉搜索树，如下图：

红黑树03

# 右旋转

以节点X为根顺时针旋转二叉搜索树，使得父节点原来的位置被自己的左子节点替代，右子节点的位置被父节点替代；

红黑树04

如上图所示，右旋转之后：

  • 节点X取代了节点a原来的位置；
  • 节点Y取代了节点X原来的位置；
  • 节点X的右子树 a 仍然是节点X的右子树（这里X的右子树虽然只有一个节点，但是多个节点时同样适用，以下同理）；
  • 节点Y的左子树 b 仍然是节点Y的左子树；
  • 节点Y的右子树 c 向右平移成为了节点X的左子树；

右旋转后仍满足二叉搜索树，如下图：

红黑树05

# 红黑树的插入操作

首先需要明确，在保证满足红黑树5条规则的情况下，新插入的节点必然是红色节点。

为了方便说明，规定以下四个节点：新插入节点为N（Node），N的父节点为P（Parent），P的兄弟节点为U（Uncle），P和U的父节点为G（Grandpa），如下图所示：

红黑树06

红黑树的节点插入有7种情况：

# 情况1

插入的新节点N位于树的根上时，没有父节点。即插入的节点是根节点。

这种情况下，只需要将红色节点变为黑色节点即可满足规则2 。

红黑树07

# 情况2

插入的新节点N的父节点P为黑色节点，此时不需要任何变化。

此时既满足规则4也满足规则5。尽管新节点是红色的，但是新节点N有两个黑色节点NIL，所以通向它的路径上黑色节点的个数依然相等，因此满足规则5 。

红黑树08

# 情况3

插入新节点N，节点P为红色，节点U也为红色，此时节点G必为黑色，即父红叔红祖黑。

在这种情况下需要：

  • 先将父节点P变为黑色；
  • 再将叔叔节点U变为黑色；
  • 最后将祖父节点G变为红色；

即变为父黑叔黑祖红，如下图所示：

红黑树09

可能出现的问题：

  • N的祖父节点G的父节点也可能是红色，这就违反了规则4，此时可以通过递归调整节点颜色；
  • 处理：将祖父节点G当作新插入的红色节点，从祖父节点G的父节点开始由底向上进行处理，直至插入节点的父节点为黑色节点或者插入节点为根节点。
  • 整个处理过程中可能还需要旋转，下面情况分析旋转。

红黑树10

# 情况4

节点P是节点G的左子节点，节点P是红色节点，节点U是黑色节点，并且节点N为节点P的左子节点，此时节点G一定是黑色节点，即父红叔黑祖黑。

在这种情况下需要：

  • 先变色：将父节点P变为黑色，将祖父节点G变为红色；
  • 后旋转：以祖父节点G为根进行右旋转；

红黑树11

# 情况5

节点P是节点G的左子节点，节点P是红色节点，节点U是黑色节点，并且节点N为节点P的右子节点，此时节点G一定是黑色节点，即父红叔黑祖黑。

在这种情况下需要：

  • 先以节点P为根进行左旋转，旋转后如图b所示；
  • 随后将红色节点P和黑色节点B看成一个整体的红色节点N1，将新插入的红色节点N看成红色节点P1 如图c所示。此时整体就转换为了情况4。

红黑树12

接着可以按照情况4进行处理：

  • 先变色：将N1节点的父节点P1变为黑色，将祖父节点G变为红色；
  • 后旋转：以祖父节点G为根进行右旋转，旋转后如图 e 所示；
  • 最后将节点N1和P1变换回来，完成节点N的插入，如图 f 所示；

红黑树13

# 情况6 （情况4镜像）

节点P是节点G的右子节点，节点P是红色节点，节点U是黑色节点，并且节点N为节点P的右子节点，此时节点G一定是黑色节点，即父红叔黑祖黑。

在这种情况下，与情况4处理只是旋转变成左旋转，需要：

  • 先变色：将父节点P变为黑色，将祖父节点G变为红色；
  • 后旋转：以祖父节点G为根进行左旋转；

红黑树14

# 情况7 （情况5镜像）

节点P是节点G的右子节点，节点P是红色节点，节点U是黑色节点，并且节点N为节点P的左子节点，此时节点G一定是黑色节点，即父红叔黑祖黑。

处理与情况5相同，只是旋转方向相反。

需要：

  • 先以节点P为根进行右旋转；
  • 随后将红色节点P和黑色节点B看成一个整体的红色节点N1，将新插入的红色节点N看成红色节点P1。此时整体就转换为了情况4镜像。

红黑树15

# 情况8

插入节点key已存在。

这种情况下，在插入节点之前，红黑树是保持着平衡状态，只需要将插入节点的颜色变为被替换节点的颜色，同时替换掉原节点；或者只需要将新节点种的值赋值给原节点即可。

# 插入案例

在二叉树中依次插入节点：10，9，8，7，6，5，4，3，2，1

如果直接采用普通的二叉搜索树，节点全部插入后是这样的：

红黑树16-0

是一个严重的不平衡树，相当于一个链表，不能体现出二叉搜索树的高效率。而按照红黑树的五条规则插入节点就能最大程度保证搜索二叉树是一棵平衡树。

以下为过程详解：为了方便解释省略了部分红黑树的叶子节点（NIL）

  • 插入10：符合情况1

    1. 插入节点10；
    2. 将节点10的颜色变为黑色；

    红黑树16

  • 插入9：符合情况2

    1. 不需要任何变化

    红黑树17

  • 插入8：符合情况4

    1. 父节点9变成黑，祖父节点10变为红；
    2. 以祖父节点为根进行右旋转；

    红黑树18

  • 插入7：符合情况3

    1. 节点8和叔节点10变为黑，祖父节点9变为红；
    2. 此时会出现问题：不符合规则2，即根节点不为黑，此时可以把以9为根节点的二叉搜索树当作一个整体作为一个新插入的节点N，而此时又符合情况1，只需要把9变回黑色即可。

    红黑树19

  • 插入6：符合情况4

    1. 父节点7变为黑，祖父节点8变为红；
    2. 以祖父节点8为根进行右旋转；

    红黑树20

  • 插入5：符合情况3

    1. 父节点6和叔节点8变为黑
    2. 祖父节点7变为红；

    红黑树21

  • 插入4：符合情况4

    1. 父节点5变为黑，祖父节点6变为红；
    2. 以祖父节点6为根进行右旋转；

    红黑树22

  • 插入3

    • 第一次变换：符合情况3

      1. 父节点4和6变成黑色，祖父节点5变成红色
      2. 变换之后发现5和7为相连的两个红色节点，于是把以5为根的整个子树看成一个新插入的节点N1，再进行第二次变换。

      红黑树23

    • 第二次变换：符合情况4

      1. 父节点7变为黑，祖父节点9变为红；
      2. 以祖父节点9为根进行右旋转；
      3. 最后复原N1得到变换后的红黑树

      红黑树24

      红黑树25

  • 插入2：符合情况4

    1. 父节点3变为黑，祖父节点4变为红；
    2. 以祖父节点4为根进行右旋转；

    红黑树26

  • 插入1

    • 第一次变换：符合情况3：

      1. 父节点2和叔节点4变为黑，祖父节点3变为红；

      变换之后发现3和5为相连的两个红色节点，于是把以3为根的整个子树看成一个新插入的节点N1，再进行第二次变换。

      红黑树27

    • 第二次变换：符合情况3

      1. 父节点5和叔节点9变为黑，祖父节点7变为红；
      2. 变换之后发现根节点7为红色不符合规则2，所以把以7为根节点的红黑树看成一个新插入的节点N2，再进行第三次变换

    • 第三次变换：符合情况1

      1. 直接将根节点7变为黑色即可

      红黑树28

由此，完成了1~10节点的插入，虽然没有遇到情况5，不过情况5经过左旋转的操作便可转换为情况4，原理一样。如下图所示，将这棵红黑树的叶子节点NIL补全之后，经检验满足红黑树的五条规则，并且基本属于平衡树，效率较高。

红黑树29

# 封装

红黑树本质上是一颗二叉查找树，只有增加和删除节点是不一样的，这里只分析插入代码。

const COLOR = {
  RED: 'red',
  BALCK: 'black'
}

class Node {
  constructor (key, value, color) {
    this.key = key // 节点对应的key
    this.value = value
    this.color = color

    this.left = null // 指向的左子树
    this.right = null // 指向的右子树
    this.parent = null // 指向的父节点
  }
}


/**
 * 红黑树
 */
 module.exports = class RedBlackTree {
  constructor () {
    this.root = null
  }

  // 先序遍历
  preOrderTraversal (handler) {
    this._preOrderTraversalNode(this.root, handler)
  }
  _preOrderTraversalNode (node, handler) {
    if (node !== null) {
      // 首先回调 handler
      handler(node.key)
      // 然后遍历所有的左子树
      this._preOrderTraversalNode(node.left, handler)
      // 最后遍历所有的右子树
      this._preOrderTraversalNode(node.right, handler)
    }
  }

  // 中序遍历
  inOrderTraversal (handler) {
    this._inOrderTraversalNode(this.root, handler)
  }
  _inOrderTraversalNode (node, handler) {
    if (node !== null) {
      // 首先遍历所有的左子树
      this._inOrderTraversalNode(node.left, handler)
      // 然后回调 handler
      handler(node.key)
      // 最后遍历所有的右子树
      this._inOrderTraversalNode(node.right, handler)
    }
  }

  // 后序遍历
  postOrderTraversal (handler) {
    this._postOrderTraversalNode(this.root, handler)
  }
  _postOrderTraversalNode (node, handler) {
    if (node !== null) {
      // 首先遍历所有的左子树
      this._postOrderTraversalNode(node.left, handler)
      // 然后遍历所有的右子树
      this._postOrderTraversalNode(node.right, handler)
      // 最后回调 handler
      handler(node.key)
    }
  }

  /**
   * 左旋
   *      G             P
   *     / \           / \
   *    U   P   ===>  G   N
   *       / \       / \
   *      L   N     U   L
   * @param {*} node 旋转支点G
   */
  rotateLeft (gnode) {
    const pnode = gnode.right

    // G.right = L
    gnode.right = pnode.left
    if (pnode.left) {
      // L节点存在，将L.parent指向G
      pnode.left.parent = gnode
    }

    // P.parent = G.parent
    pnode.parent = gnode.parent

    if (gnode.parent === null) { // G是根节点
      // this.root = P
      this.root = pnode
    } else {
      if (gnode.parent.right === gnode) {
        // G是父节点的右子节点
        gnode.parent.right = pnode
      } else {
        // G是父节点的左子节点
        gnode.parent.left = pnode
      }
    }

    // P.left = G
    pnode.left = gnode
    // G.parent = P
    gnode.parent = pnode
  }

  /**
   * 右旋
   *      G             P
   *     / \           / \
   *    P   U   ===>  N   G
   *   / \               / \
   *  N   R             R   U
   * @param {*} node 旋转支点G
   */
  rotateRight (gnode) {
    const pnode = gnode.left

    // G.left = R
    gnode.left = pnode.right
    if (pnode.right) {
      pnode.right.parent = gnode
    }

    pnode.parent = gnode.parent

    if (gnode.parent === null) { // G是根节点
      this.root = pnode
    } else {
      if (gnode.parent.right === gnode) {
        // G是父节点的右子节点
        gnode.parent.right = pnode
      } else {
        // G是父节点的左子节点
        gnode.parent.left = pnode
      }
    }

    // P.right = G
    pnode.right = gnode
    // G.parent = P
    gnode.parent = pnode
  }

  /**
   * 向树中插入一个节点 循环
   */
  insert (key, value) {
    const newNode = new Node(key, value, COLOR.RED)
    if (this.root === null) {
      this.root = newNode
    } else {
      let parent
      let node = this.root
      while(node !== null) {
        parent = node
        if (node.key === newNode.key) {
          // 情况8 插入节点key已存在 更新节点value即可
          // newNode.color = node.color
          node.value = newNode.value
          return
        } else if (node.key > newNode.key) {
          // 向左子树查找
          node = node.left
        } else {
          // 向右子树查找
          node = node.right
        }
      }

      newNode.parent = parent
      if (parent.key > newNode.key) {
        parent.left = newNode
      } else {
        parent.right = newNode
      }
    }

    // 插入节点平衡修正
    this.balanceInsertion(newNode)
  }

  /**
   * 插入节点平衡修正
   */
  balanceInsertion (node) {
    // 情况2：插入的新节点N的父节点P为黑色节点，此时不需要任何变化 无需修正

    // 插入节点非根节点 且 插入节点的父级是红色节点
    while (node.parent !== null && node.parent.color === COLOR.RED) {
      let uncle = null
      let grandpa = node.parent.parent
      if (node.parent === grandpa.left) { // 父节点是祖父节点的左子节点
        uncle = grandpa.right
        // 情况3 父红叔红祖黑 叔叔节点是红色
        if (uncle !== null && uncle.color === COLOR.RED) {
          // 父节点、叔叔节点变成黑色，祖父节点变成红色
          node.parent.color = COLOR.BALCK
          uncle.color = COLOR.BLACK
          grandpa.color = COLOR.RED
          // 以祖父节点当作新节点继续调用修正方法
          node = grandpa
          continue
        }

        // 情况5 父节点是祖父节点的左子节点 插入节点是父节点的右子节点 且 父红叔黑祖黑
        if (node === node.parent.right) {
          // 左旋之后，原插入节点的父节点变成新插入节点 回归情况4
          node = node.parent // 将原插入节点的父节点看作是新插入节点
          grandpa = node.parent.parent // 重新赋值新节点的grandpa
          this.rotateLeft(node) // 以父节点为支点进行左旋转
        }

        // 情况4 父节点是祖父节点的左子节点 插入节点是父节点的左子节点 且 父红叔黑祖黑
        // 以及情况5左旋转之后
        node.parent.color = COLOR.BALCK // 父节点变成黑色
        grandpa.color = COLOR.RED // 祖父节点变成红色
        this.rotateRight(grandpa) // 以祖父节点进行右旋转
      } else { // 父节点是祖父节点的右节点
        uncle = grandpa.left
        // 情况3 父红叔红祖黑 叔叔节点是红色
        if (uncle !== null && uncle.color === COLOR.RED) {
          node.parent.color = COLOR.BLACK
          uncle.color = COLOR.BLACK
          grandpa.color = COLOR.RED
          // 以祖父节点当作新节点继续调用修正方法
          node = grandpa
          continue
        }

        // 情况5镜像 父节点是祖父节点的右子节点 插入节点是父节点的左子节点 且 父红叔黑祖黑
        if (node === node.parent.left) {
          // 右旋之后，原插入节点的父节点变成新插入节点 回归情况4镜像
          node = node.parent // 将原插入节点的父节点看作是新插入节点
          grandpa = node.parent.parent // 重新赋值新节点的grandpa
          this.rotateRight(node) // 以父节点为支点进行右旋转
        }

        // 情况4镜像 父节点是祖父节点的右子节点 插入节点是父节点的右子节点 且 父红叔黑祖黑
        if (node === node.parent.right) {
          node.parent.color = COLOR.BALCK
          grandpa.color = COLOR.RED
          this.rotateLeft(grandpa) // 以祖父节点进行左旋转
        }
      }
    }

    // 情况1：插入节点是根节点
    // 情况3：最后回归情况1
    this.root.color = COLOR.BALCK
  }
}
编辑 (opens new window)
上次更新: 2022/01/12, 11:17:42
数据结构与算法-二叉搜索树
数据结构与算法-红黑树（二）

← 数据结构与算法-红黑树（二）→

最近更新
01
阅读精通正则表达式总结
09-29
02
项目搭建规范的配置
07-15
03
Vite的使用
07-03
更多文章>
Theme by Vdoing | Copyright © 2018-2023 Ccbeango