Stephan Xu
文章 标签 归类 主页
Stephan Xu

红黑树基础操作

 
       

性质

  • 每个节点要么是黑色，要么是红色
  • 根节点是黑色
  • 每个叶子结点（NIL）是黑色
  • 每个红色节点的两个子节点一定都是黑色，即不能有两个红色节点相连
  • 任意一节点到每个叶子结点的路径都包含数量相同的黑节点（俗称“黑高”）
    • 推论：如果一个节点存在黑子节点，那么该节点肯定有两个子节点。

/posts/%E7%BA%A2%E9%BB%91%E6%A0%91%E5%9F%BA%E7%A1%80%E6%93%8D%E4%BD%9C/images/Untitled.png

自平衡操作

  • 变色：结点的颜色由红变黑或由黑变红。

  • 左旋：以某个节点作为支点（旋转节点），其右子节点变为旋转节点的父节点，右子节点的左子节点变为旋转节点的右子节点，左子节点保持不变。

/posts/%E7%BA%A2%E9%BB%91%E6%A0%91%E5%9F%BA%E7%A1%80%E6%93%8D%E4%BD%9C/images/Untitled%201.png

/posts/%E7%BA%A2%E9%BB%91%E6%A0%91%E5%9F%BA%E7%A1%80%E6%93%8D%E4%BD%9C/images/%E5%B7%A6%E6%97%8B.gif

  • 右旋：以某个节点作为支点（旋转节点），其左子节点变为旋转节点的父节点，左子节点的右子节点变为旋转节点的左子节点，右节点保持不变。

/posts/%E7%BA%A2%E9%BB%91%E6%A0%91%E5%9F%BA%E7%A1%80%E6%93%8D%E4%BD%9C/images/Untitled%202.png

/posts/%E7%BA%A2%E9%BB%91%E6%A0%91%E5%9F%BA%E7%A1%80%E6%93%8D%E4%BD%9C/images/%E5%8F%B3%E6%97%8B.gif

插入操作

插入节点时，节点必须为红色。

原因：红色在父节点为黑色节点时，红黑树的黑色平衡没有被破坏，不需要做自平衡操作。但如果插入节点为黑色，那么插入位置所在的子树黑色节点总是多1，必须做自平衡。

术语

/posts/%E7%BA%A2%E9%BB%91%E6%A0%91%E5%9F%BA%E7%A1%80%E6%93%8D%E4%BD%9C/images/Untitled%203.png

插入情景

  • 红黑树为空树：直接把插入节点作为根节点，并把插入节点设置为黑色。
  • 插入节点的Key已经存在：更新当前节点的值为插入节点的值。
  • 插入节点的父节点为黑色：由于插入的节点是红色的，当父节点是黑色时，并不会影响红黑树的平衡，直接插入即可，无需做自平衡。

/posts/%E7%BA%A2%E9%BB%91%E6%A0%91%E5%9F%BA%E7%A1%80%E6%93%8D%E4%BD%9C/images/Untitled%204.png

  • 插入节点的父节点为红色：如果插入节点的父节点为红节点，那么该父节点不可能为根节点，所以插入节点总是存在祖父节点。

    • 叔叔节点存在并且为红节点
      • 将P和U节点改为黑色
      • 将PP改为红色
      • 将PP设置为当前节点，进行后续处理（即如果PP的父节点也是红色，则继续以PP为当前节点进行插入操作自平衡处理，直到平衡为止）

    /posts/%E7%BA%A2%E9%BB%91%E6%A0%91%E5%9F%BA%E7%A1%80%E6%93%8D%E4%BD%9C/images/Untitled%205.png

    • 叔叔节点不存在或为黑节点，并且插入节点的父亲节点是祖父节点的左子节点

      • 新插入的节点是其父节点的左子节点（LL双红）

        • 变色：将P设置为黑色，将PP设置为红色
        • 对PP节点进行右旋

        /posts/%E7%BA%A2%E9%BB%91%E6%A0%91%E5%9F%BA%E7%A1%80%E6%93%8D%E4%BD%9C/images/Untitled%206.png

      • 新插入的节点是其父节点的右子节点（LR双红）

        • 对P进行左旋
        • 将P设置为当前节点，得到“LL双红”的情况
        • 按照“LL双红”的情况处理（变颜色、右旋PP）

        /posts/%E7%BA%A2%E9%BB%91%E6%A0%91%E5%9F%BA%E7%A1%80%E6%93%8D%E4%BD%9C/images/Untitled%207.png

    • 叔叔节点不存在或为黑节点，并且插入节点的父亲节点是祖父节点的右子节点

      • 新插入的节点是其父节点的右子节点（RR双红）

        • 变色：将P设置为黑色，将PP设置为红色
        • 对PP节点进行左旋

        /posts/%E7%BA%A2%E9%BB%91%E6%A0%91%E5%9F%BA%E7%A1%80%E6%93%8D%E4%BD%9C/images/Untitled%208.png

      • 新插入的节点是其父节点的左子节点（RL双红）

        • 对P进行右旋
        • 将P设置为当前节点，得到“RR红色”的情况
        • 按照“RR红色”情况处理（变颜色、左旋PP）

        /posts/%E7%BA%A2%E9%BB%91%E6%A0%91%E5%9F%BA%E7%A1%80%E6%93%8D%E4%BD%9C/images/Untitled%209.png

 |