手写红黑树笔记

CBeann

发布于 2023-12-25 18:46:40

1040

发布于 2023-12-25 18:46:40

文章被收录于专栏：CBeann的博客CBeann的博客

写这篇文章的目的

红黑树很重要，所以学一下，整理一下笔记

代码下载

Demooo/java-demoo/src/main/java/myredblacktree at master · cbeann/Demooo · GitHub

红黑树难点

红黑树性质

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

插入节点必为红色

假设插入的节点为红色，那么在不考虑空树的情况下，该插入节点的父节点可能为红色，也可能为黑色。如果父节点为黑色，插入后没有破坏红黑树的性质；如果父节点为红色，则破坏了红黑树性质（不能有两个红色节点相连）。

假设插入的节点为黑色，则插入后必破坏红黑树的性质（任意一个节点到每一个叶子节点的路径都包含相同的黑节点）

综上：插入节点必为红色

插入变色规则

插入后修复红黑树平衡的方法情景1：红黑树为空树，插入节点将作为根，将根节点染色为黑色。情景2：插入节点的key已经存在，则只需要替换value值即可。情景3：插入节点的父节点为黑色，插入后不需要其他操作。（因为插入的的为红色，黑色节点没有变化，所以红黑树依然平衡，所以不需要处理）情景4：插入节点的父节点为红色（非常复杂）情景4-1：叔叔节点存在。并且叔叔为红色(父-叔双红)。将爸爸和叔叔染色为黑色，将爷爷染色为红色，并且在以爷爷节点为当前节点，进行下一轮处理。情景4-2：叔叔节点不存在或者为黑色。父节点为爷爷节点的左子树。情景4-2-1：插入节点为其父节点的左子节点（LL情景）。将爸爸染色为黑色，将爷爷染色为红色，然后以爷爷节点右旋，就结束了。情景4-2-2：插入节点为其父节点的右子节点（LR情景）。以爸爸节点进行一次左旋，得到LL双红的情景（4.2.1），然后指定爸爸节点为当前节点进行下一轮处理。情景4-3：叔叔节点不存在，或者为黑色。父节点为爷爷节点的右子树情景4-3-1：插入节点为其父节点的右子节点（RR情景）。将爸爸染色为黑色，将爷爷染色为红色，然后以爷爷节点左旋，就结束了。情景4-3-2：插入节点为其父节点的左子节点（RL情景）。以爸爸节点进行一次右旋，得到RR双红的情景（4.3.1），然后指定爸爸节点为当前节点进行下一轮处理。

左旋右旋编码实现

以左旋为例，如下图和代码所示，虽然我的写的左旋代码很乱，但是只要知道修改了下图中红色标记的点的某几个指针（左子树、右子树、父节点），而且你也知道修改后的应该指向哪，那这个左旋就应该差不多了，编码的时候注意null，然后就实现了左旋代码。

 /**
   * 左旋
   *
   * @param x <br>
   *     图片：https://www.processon.com/view/link/5ff15f05e0b34d19e4f880f1
   */
  private void leftRotate(Node x) {

    if (x == null) {
      return;
    }

    // 记录父节点
    Node parent = x.getParent();
    // 记录X节点的左子树和右子树
    Node xl = x.getLeft();
    Node xr = x.getRight();

    // ---> 修改父节点的指针
    if (null != parent) {
      if (x == parent.left) {
        parent.left = xr;
      } else {
        parent.right = xr;
      }

    } else {
      // parent=null表示为根
      this.root = xr;
      xr.parent = null;
    }

    // ---> 修改x节点的指针
    // 修改左子树(不需要修改)
    // 修改右子树
    if (xr != null) {
      x.right = xr.left;
    }
    // 修改父节点
    x.parent = xr;

    // ---> 修改xl节点的指针（不需要修改）

    // ---> 修改xr节点的指针
    if (xr != null) {
      // 修改左子树
      xr.left = x;
      // 修改右子树(不需要修改)
      // 修改父节点
      if (null != parent) {
        xr.parent = parent;
      }
    }

    // ---> 修改xrl节点的指针
    // 修改左子树(不需要修改)
    // 修改右子树(不需要修改)
    // 修改父节点
    if (xr.left != null) {
      xr.left.parent = x;
    }
  }

代码

Node节点

package myredblacktree;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

/**
 * @author chaird
 * @create 2021-01-03 13:46 <br>
 *     红黑树节点
 */
@Data
@AllArgsConstructor
@NoArgsConstructor
public class Node<K extends Comparable<K>, V> {

  public Node(K key, V value) {
    this.key = key;
    this.value = value;
  }

  // 父节点
  Node parent;
  // 左子树
  Node left;
  // 右子树
  Node right;
  // 颜色，红色为true,黑色为false
  Boolean color;
  // key
  K key;
  // vale
  V value;

  @Override
  public String toString() {
    return "Node{" + ", color=" + color + ", key=" + key + ", value=" + value + '}';
  }
}

红黑树实体类

package myredblacktree;

import lombok.Data;

/**
 * @author chaird
 * @create 2021-01-03 13:52<br>
 *     红黑树
 */
@Data
public class RBTree<K extends Comparable<K>, V> {

  // 根节点
  private Node root;

  // 定义红黑树常量
  private static final boolean RED = true;
  private static final boolean BLACK = false;

  /**
   * 当前节点是否是红色
   *
   * @param node
   * @return
   */
  private Boolean isRed(Node node) {
    if (null != node) {

      return node.getColor() == RED;
    }
    return false;
  }

  /**
   * 当前节点是否是黑色
   *
   * @param node
   * @return
   */
  private Boolean isBlack(Node node) {
    if (null != node) {

      return node.getColor() == BLACK;
    }
    return false;
  }

  /**
   * 设置节点为红色
   *
   * @param node
   */
  private void setRed(Node node) {
    if (null != node) {
      node.setColor(RBTree.RED);
    }
  }

  /**
   * 设置节点为黑色
   *
   * @param node
   */
  private void setBlack(Node node) {
    if (null != node) {
      node.setColor(RBTree.BLACK);
    }
  }

  /**
   * 左旋
   *
   * @param x <br>
   *     图片：https://www.processon.com/view/link/5ff15f05e0b34d19e4f880f1
   */
  private void leftRotate(Node x) {

    if (x == null) {
      return;
    }

    // 记录父节点
    Node parent = x.getParent();
    // 记录X节点的左子树和右子树
    Node xl = x.getLeft();
    Node xr = x.getRight();

    // ---> 修改父节点的指针
    if (null != parent) {
      if (x == parent.left) {
        parent.left = xr;
      } else {
        parent.right = xr;
      }

    } else {
      // parent=null表示为根
      this.root = xr;
      xr.parent = null;
    }

    // ---> 修改x节点的指针
    // 修改左子树(不需要修改)
    // 修改右子树
    if (xr != null) {
      x.right = xr.left;
    }
    // 修改父节点
    x.parent = xr;

    // ---> 修改xl节点的指针（不需要修改）

    // ---> 修改xr节点的指针
    if (xr != null) {
      // 修改左子树
      xr.left = x;
      // 修改右子树(不需要修改)
      // 修改父节点
      if (null != parent) {
        xr.parent = parent;
      }
    }

    // ---> 修改xrl节点的指针
    // 修改左子树(不需要修改)
    // 修改右子树(不需要修改)
    // 修改父节点
    if (xr.left != null) {
      xr.left.parent = x;
    }
  }

  /**
   * 右旋
   *
   * @param x <br>
   *     图片：https://www.processon.com/view/link/5ff1660807912977bede44d5
   */
  private void rightRotate(Node x) {

    if (null == x) {
      return;
    }

    // 记录父节点
    Node parent = x.getParent();
    // 记录X节点的左子树和右子树
    Node xl = x.getLeft();
    Node xr = x.getRight();

    // ---> 修改父节点的指针
    if (null != parent) {
      if (x == parent.left) {
        parent.left = xl;
      } else {
        parent.right = xl;
      }

    } else {
      // parent=null表示为根
      this.root = xl;
      xl.parent = null;
    }

    // ---> 修改X节点的指针
    // 修改左子树
    if (xl != null) {
      x.left = xl.right;
    }
    // 修改右子树(不需要修改)
    // 修改父节点
    x.parent = xl;

    // ---> 修改xl节点的指针
    // 修改左子树(不需要修改)
    // 修改右子树
    xl.right = x;
    // 修改父节点
    xl.parent = parent;

    // ---> 修改XR节点的指针(不需要修改)

    // ---> 修改XLR节点的指针
    // 修改左子树(不需要修改)
    // 修改右子树(不需要修改)
    // 修改父节点
    if (xl.right != null) {
      xl.parent = x;
    }
  }

  public void insert(K key, V value) {

    Node node = new Node(key, value);
    // 新阶段一定是红色
    node.setColor(RED);
    insert(node);
  }

  private void insert(Node node) {

    // 第一步：查找当前的node的父节点
    Node parent = null;
    Node x = this.root;

    while (x != null) {
      parent = x;
      int cmp = node.getKey().compareTo(x.getKey());
      if (cmp > 0) {
        x = x.getRight();
      } else if (cmp < 0) {
        x = x.getLeft();
      } else if (cmp == 0) {
        x.setValue(node.getValue());
        return;
      }
    }

    node.setParent(parent);
    // 判断node是parent的左子树还是右子树
    if (parent != null) {
      int cmp = node.getKey().compareTo(parent.getKey());

      if (cmp > 0) {
        parent.setRight(node);
      } else {
        parent.setLeft(node);
      }
    } else {
      this.root = node;
    }

    // 需要调用红黑树平衡的方法
    insertFixUp(node);
  }

  // 修复红黑树(复杂)

  /**
   * 插入后修复红黑树平衡的方法<br>
   * 情景1：红黑树为空树，将根节点染色为黑色。 <br>
   * 情景2：插入节点的key已经存在（不需要处理） <br>
   * 情景3：插入节点的父节点为黑色（因为插入的的为红色，黑色节点没有变化，所以红黑树依然平衡，所以不需要处理） <br>
   * 情景4：插入节点的父节点为红色（复杂） 情景4-1：叔叔节点存在。并且为红色(父-叔 双红)。将爸爸和叔叔染色为黑色，将爷爷染色为红色，并且在以爷爷节点为当前节点，进行下一轮处理
   * 情景4-2：叔叔节点不存在，或者为黑色。父节点为爷爷节点的左子树 <br>
   * 情景4-2-1：插入节点为其父节点的左子节点（LL情景）。将爸爸染色为黑色，将爷爷染色为红色，然后以爷爷节点右旋，就结束了
   * 情景4-2-2：插入节点为其父节点的右子节点（LR情景）。以爸爸节点进行一次左旋，得到LL双红的情景（4.2.1），然后指定爸爸节点为当前节点进行下一轮处理
   * 情景4-3：叔叔节点不存在，或者为黑色。父节点为爷爷节点的右子树 <br>
   * 情景4-3-1：插入节点为其父节点的右子节点（RR情景）。将爸爸染色为黑色，将爷爷染色为红色，然后以爷爷节点左旋，就结束了
   * 情景4-3-2：插入节点为其父节点的左子节点（RR情景）。以爸爸节点进行一次右旋，得到RR双红的情景（4.3.1），然后指定爸爸节点为当前节点进行下一轮处理
   *
   * @param node
   */
  private void insertFixUp(Node node) {
    // 情景1：红黑树为空树，将根节点染色为黑色。
    if (this.root == node) {
      setBlack(node);
    }

    // 情景2：插入节点的key已经存在（不需要处理） (走不到这里)

    // 情景3：插入节点的父节点为黑色（因为插入的的为红色，黑色节点没有变化，所以红黑树依然平衡，所以不需要处理） <br>
    if (node.getParent() != null && isBlack(node.getParent())) {
      return;
    }

    // 情景4：插入节点的父节点为红色（复杂）
    if (node.getParent() != null && isRed(node.getParent())) {

      Node parent = node.getParent();
      Node gParent = parent.getParent();

      Node uncle = null;
      if (parent == gParent.left) {
        // 爸爸是爷爷的左子树
        uncle = gParent.right;
      } else {
        // 爸爸是爷爷的右子树
        uncle = gParent.left;
      }

      // 情景4-1：叔叔节点存在。并且为红色(父-叔 双红)。将爸爸和叔叔染色为黑色，将爷爷染色为红色，并且在以爷爷节点为当前节点，进行下一轮处理
      if (null != uncle && isRed(uncle)) {
        setBlack(parent);
        setBlack(uncle);
        setRed(gParent);
        insertFixUp(gParent);
        return;
      }

      // 情景4-2：叔叔节点不存在，或者为黑色。父节点为爷爷节点的左子树
      if (null == uncle || isBlack(uncle)) {
        if (parent == gParent.left) {
          // 情景4-2-1：插入节点为其父节点的左子节点（LL情景）。将爸爸染色为黑色，将爷爷染色为红色，然后以爷爷节点右旋，就结束了
          if (node == parent.left) {
            setBlack(parent);
            setRed(gParent);
            rightRotate(gParent);
            return;
          } else {
            leftRotate(parent);
            insertFixUp(parent);
            return;
          }
        }
      }

      // 情景4-3：叔叔节点不存在，或者为黑色。父节点为爷爷节点的右子树
      if (null == uncle || isBlack(uncle)) {
        if (parent == gParent.right) {
          if (node == parent.right) {
            setBlack(parent);
            setRed(gParent);
            leftRotate(gParent);
            return;

          } else {

            rightRotate(parent);
            insertFixUp(parent);
            return;
          }
        }
      }
    }
  }
}

打印红黑树工具类（针对本文）

参考于：按照树形结构直观地打印出一棵二叉树(Java) - 点点爱梦 - 博客园

package myredblacktree;

/**
 * @author chaird
 * @create 2021-01-03 10:21
 */
public class TreeOperation {
  /*
  树的结构示例：
            1
          /   \
        2       3
       / \     / \
      4   5   6   7
  */

  // 用于获得树的层数
  public static int getTreeDepth(Node root) {
    return root == null ? 0 : (1 + Math.max(getTreeDepth(root.left), getTreeDepth(root.right)));
  }

  private static void writeArray(
      Node currNode, int rowIndex, int columnIndex, String[][] res, int treeDepth) {
    // 保证输入的树不为空
    if (currNode == null) return;
    // 先将当前节点保存到二维数组中
    // res[rowIndex][columnIndex] = String.valueOf(currNode.value);
    //加颜色
    res[rowIndex][columnIndex] =
        String.valueOf(currNode.value + "-" + (currNode.color ? "红" : "黑") + "");

    // 计算当前位于树的第几层
    int currLevel = ((rowIndex + 1) / 2);
    // 若到了最后一层，则返回
    if (currLevel == treeDepth) return;
    // 计算当前行到下一行，每个元素之间的间隔（下一行的列索引与当前元素的列索引之间的间隔）
    int gap = treeDepth - currLevel - 1;

    // 对左儿子进行判断，若有左儿子，则记录相应的"/"与左儿子的值
    if (currNode.left != null) {
      res[rowIndex + 1][columnIndex - gap] = "/";
      writeArray(currNode.left, rowIndex + 2, columnIndex - gap * 2, res, treeDepth);
    }

    // 对右儿子进行判断，若有右儿子，则记录相应的"\"与右儿子的值
    if (currNode.right != null) {
      res[rowIndex + 1][columnIndex + gap] = "\\";
      writeArray(currNode.right, rowIndex + 2, columnIndex + gap * 2, res, treeDepth);
    }
  }



  public static void show(Node root) {
    if (root == null) System.out.println("EMPTY!");
    // 得到树的深度
    int treeDepth = getTreeDepth(root);

    // 最后一行的宽度为2的（n - 1）次方乘3，再加1
    // 作为整个二维数组的宽度
    int arrayHeight = treeDepth * 2 - 1;
    int arrayWidth = (2 << (treeDepth - 2)) * 3 + 1;
    // 用一个字符串数组来存储每个位置应显示的元素
    String[][] res = new String[arrayHeight][arrayWidth];
    // 对数组进行初始化，默认为一个空格
    for (int i = 0; i < arrayHeight; i++) {
      for (int j = 0; j < arrayWidth; j++) {
        res[i][j] = " ";
      }
    }

    // 从根节点开始，递归处理整个树
    // res[0][(arrayWidth + 1)/ 2] = (char)(root.val + '0');
    writeArray(root, 0, arrayWidth / 2, res, treeDepth);

    // 此时，已经将所有需要显示的元素储存到了二维数组中，将其拼接并打印即可
    for (String[] line : res) {
      StringBuilder sb = new StringBuilder();
      for (int i = 0; i < line.length; i++) {
        sb.append(line[i]);
        if (line[i].length() > 1 && i <= line.length - 1) {
          i += line[i].length() > 4 ? 2 : line[i].length() - 1;
        }
      }
      System.out.println(sb.toString());
    }
  }
}

测试类

package myredblacktree;

/**
 * @author chaird
 * @create 2021-01-03 13:50
 */
public class Main {
  public static void main(String[] args) {

    RBTree<Integer, Object> tree = new RBTree();

    tree.insert(1, 1);
    tree.insert(2, 2);
    tree.insert(3, 3);
    tree.insert(4, 4);
    tree.insert(5, 5);
    tree.insert(6, 6);
    tree.insert(7, 7);
    tree.insert(8, 8);

    TreeOperation.show(tree.getRoot());
  }
}