锐客网

  1. 首页 > it技术 > >

【数据结构与算法】手撕红黑树

红黑树 定义 动机：

  • 二叉查找树查找、插入、删除最坏情况时间复杂度可能退化为 O(n)。
  • AVL 树很好的限制了数的高度为 O(logn)，插入、删除、查找的最坏时间复杂度均为 O(logn)；但删除操作最多需要做 O(logn) 次旋转。
  • 红黑树是具有如下特点的二叉查找树：
    • 每个结点是红色或黑色的
    • 根结点为黑色
    • 外结点为黑色（外界点即为 null）
    • 如果一个结点时红色，那么它的孩子必须是黑色
    • 任一结点到外结点的路径上，包含相同数目的黑结点
【数据结构与算法】手撕红黑树
文章图片
结点的黑高度：该结点到外结点的路径上包含的黑结点数目
红黑树的黑高度：根结点的黑高度
性质
  • 若忽略红结点而只考虑黑结点，则这棵树是平衡的
  • 任何一条路径上不能有两个连续的红结点。从任意结点触发最长的路径（红黑结点间隔组成）是最短路径（仅由黑结点组成）的 2 倍
  • 任何一个结点的左右子树的高度最多相差 2 倍
  • 红黑树的平衡性比 AVL 树更弱
  • 平均和最坏高度：O(logn)
  • 查找、插入、删除操作的平均和最坏时间复杂度是 O(logn)，且仅涉及 O(1) 次旋转
  • 红黑树的高度：h = O(logn) 且 logn <= h <= 2logn
    【数据结构与算法】手撕红黑树
    文章图片

结点定义 【数据结构与算法】手撕红黑树
文章图片
1?? key：关键字的值
2?? value：关键字的存储信息
3?? parent：父亲结点的引用
4?? left：左子树根结点的引用
5?? right：右子树根结点引用
6?? color：结点颜色
class RBNode, V> { public RBNode parent; public RBNode left; public RBNode right; public boolean color; public K key; public V value; public RBNode(RBNode parent, K key, V value) { this.parent = parent; this.key = key; this.value = https://www.it610.com/article/value; } }

插入算法
  • 查找，若查找成功则不插入并更新结点值；若查找失败，再查找失败的位置插入新结点
  • 新结点总是作为叶结点插入的
  • 新结点必须为红色
  • 若新结点的父结点是黑色，则插入过程结束
  • 若新结点的父结点是红色，则需要处理双红缺陷
这里定义 x 为新插入的结点，p 为 x 的父结点，g 为 x 的爷爷结点，u 为 x 的叔叔
【数据结构与算法】手撕红黑树
文章图片
双红修正
1?? x 的叔叔是黑色
  • g 到 x 的路径为 LL 型
    【数据结构与算法】手撕红黑树
    文章图片

  • g 到 x 的路径为 RR 型
    【数据结构与算法】手撕红黑树
    文章图片

  • g 到 x 的路径为 LR 型
    【数据结构与算法】手撕红黑树
    文章图片

  • g 到 x 的路径为 RL 型
    【数据结构与算法】手撕红黑树
    文章图片

2?? x 的叔叔是红色
【数据结构与算法】手撕红黑树
文章图片
实例
【数据结构与算法】手撕红黑树
文章图片
此时结点 50 的父亲结点 60 也为红色，需要进行双红修正。注意到，其叔叔结点 20 也是红色，只需要将父亲结点 60 和叔叔结点 20 变为黑色，再把爷爷结点 30 变为红色，结果如下图。
【数据结构与算法】手撕红黑树
文章图片
之后会发现，结点 30 和其父结点 70 都为红色，需要进行双红修正。而结点 30 的叔叔结点 85 为黑色，结点 30 的爷爷结点 15 到达结点 30 的路径是 RL 型，故需要先右旋，再左旋。结果如下图。
【数据结构与算法】手撕红黑树
文章图片
旋转操作
由于红黑树结点还拥有 parent 属性，故不能像平衡二叉树一样进行旋转（【数据结构与算法】手撕平衡二叉树），需要特殊考虑 parent的赋值。
1?? RR 型
左旋
【数据结构与算法】手撕红黑树
文章图片
需要特别注意的是爷爷结点 g 的 parent 的设置，需要先判断 g 是左子结点还是右子结点。
private void leftRotate(RBNode g) { if (g != null) { RBNode p = g.right; g.right = p.left; if (p.left != null) { p.left.parent = g; } p.parent = g.parent; if (g.parent == null) { this.root = p; } else if (g.parent.left == g) { g.parent.left = p; } else { g.parent.right = p; } p.left = g; g.parent = p; }

2?? LL 型
右旋
【数据结构与算法】手撕红黑树
文章图片
需要特别注意的是爷爷结点 g 的 parent 的设置，需要先判断 g 是左子结点还是右子结点。
private void rightRotate(RBNode g) { if(g != null) { RBNode p = g.left; g.left = p.right; if(p.right != null) { p.right.parent = g; } p.parent = g.parent; if(g.parent == null) { this.root = p; } else if(g.parent.left == g) { g.parent.left = p; } else { g.parent.right = p; } p.right = g; g.parent = p; } }

3?? LR 型
先对 g 的左子结点左旋，再对 g 右旋
【数据结构与算法】手撕红黑树
文章图片
private void leftRightRotate(RBNode g) { if(g != null) { leftRotate(g.left); rightRotate(g); } }

4?? RL 型
先对 g 的右子结点右旋，再对 g 左旋
【数据结构与算法】手撕红黑树
文章图片
private void rightLeftRotate(RBNode g) { if(g != null) { rightRotate(g.right); leftRotate(g); } }

代码
1?? 插入操作
代码描述
  • 如果根结点为空，则创建根结点，返回
  • 否则，根据 key 与结点关键值的比较找到插入位置
  • 创建结点并插入
  • 平衡处理
public void insert(K key, V value) { RBNode t = this.root; if (t == null) { this.root = new RBNode(null, key, value); setColor(root, BLACK); return; } int cmp = 0; RBNode parent = null; while (t != null) { parent = t; cmp = key.compareTo(t.key); if (cmp < 0) { t = t.left; } else if (cmp > 0) { t = t.right; } else { t.value = https://www.it610.com/article/value; return; } } RBNode e = new RBNode(parent, key, value); if (cmp < 0) { parent.left = e; } else { parent.right = e; } // 平衡处理，旋转+变色 fixAfterPut(e); }

2?? 平衡处理
代码描述
  • 新插入的结点都设置为红色
  • 进入循环，条件是 x 不为空且 x 不为根结点且 x 的父亲为红色（进行双红处理）
  • 若父结点是爷爷结点的左子结点，即为 L 类型
    • 令 uncle 为叔叔结点
    • 若叔叔结点为红色：令爷爷结点为红色，父亲结点为黑色，叔叔结点为黑色，x 赋为爷爷结点，进入下一次循环处理。
    • 若叔叔结点为黑色：
      • 若 x 是父结点的右子结点，则为 LR 型，先左旋，再右旋，染色
      • 若 x 是父结点的左子结点，则为 LL 型，左旋，染色
  • 若父结点是爷爷结点的右子结点，即为 R 类型
    • 令 uncle 为叔叔结点
    • 若叔叔结点为红色：令爷爷结点为红色，父亲结点为黑色，叔叔结点为黑色，x 赋为爷爷结点，进入下一次循环处理。
    • 若叔叔结点为黑色：
      • 若 x 是父结点的左子结点，则为 RL 型，先右旋，再左旋，染色
      • 若 x 是父结点的右子结点，则为 RR 型，右旋，染色
  • 设置根结点为黑色（始终如此）
private void fixAfterInsert(RBNode x) { setColor(x, RED); while (x != null && x != root && colorOf(x.parent) == RED) { if (x.parent == x.parent.parent.left) { RBNode uncle = x.parent.parent.right; if (colorOf(uncle) == RED) { setColor(x.parent, BLACK); setColor(uncle, BLACK); setColor(x.parent.parent, RED); x = x.parent.parent; } else { if (x == x.parent.right) { leftRightRotate(x.parent.parent); setColor(x, BLACK); setColor(x.right, RED); } else { setColor(x.parent, BLACK); setColor(x.parent.parent, RED); rightRotate(x.parent.parent); } } } else { RBNode uncle = x.parent.parent.left; if (colorOf(uncle) == RED) { setColor(x.parent, BLACK); setColor(uncle, BLACK); setColor(x.parent.parent, RED); x = x.parent.parent; } else { if (x == x.parent.left) { rightLeftRotate(x.parent.parent); setColor(x, BLACK); setColor(x.left, RED); } else { setColor(x.parent, BLACK); setColor(x.parent.parent, RED); leftRotate(x.parent.parent); } } } } setColor(root, BLACK); }

查找前驱和后继结点 1?? 查找前驱结点
  • 若当前结点为空，则返回
  • 若当前结点存在左子树，则前驱结点是左子树的最右结点
  • 若当前结点不存在左子树：注意这种情况在删除时是不用考虑的，要么为叶子结点，可以直接删除；要么可以用右子树代替，不用考虑前驱。这里是求的是严格意义上的前驱结点。
    【数据结构与算法】手撕红黑树
    文章图片

private RBNode predecessor(RBNode node) { if (node == null) { return null; } else if (node.left != null) { RBNode p = node.left; while (p.right != null) { p = p.right; } return p; } else { RBNode p = node.parent; RBNode ch = node; while (p != null && ch == p.left) { ch = p; p = p.parent; } return p; } }

2?? 查找后继结点
  • 若当前结点为空，则返回
  • 若当前结点存在右子树，则前驱结点是右子树的最左结点
  • 若当前结点不存在右子树：注意这种情况在删除时是不用考虑的，要么为叶子结点，可以直接删除；要么可以用左子树代替，不用考虑后继。这里是求的是严格意义上的后继结点。
    【数据结构与算法】手撕红黑树
    文章图片

private RBNode successor(RBNode node) { if (node == null) { return null; } else if (node.right != null) { RBNode p = node.right; while (p.left != null) { p = p.left; } return p; } else { RBNode p = node.parent; RBNode ch = node; while (p != null && ch == p.right) { ch = p; p = p.parent; } return p; } }

删除算法 【数据结构与算法】手撕红黑树
文章图片
  • 【【数据结构与算法】手撕红黑树】定义 x 为实际删除结点，r 为替换 X 的结点，p 为 x 的父亲，s 为 x 的兄弟
  • 查找，若查找失败则直接返回，若查找成功则删除对应的结点 x
  • 删除操作最终可归结为两种情况：删除叶结点和删除只有一个孩子的结点
    • 若 x 为红，则必为红叶子，直接删除
    • 若 x 为黑 r 为红，r 替换 x，并将 r 染黑
    • 若 x 为黑 r 为黑：需要处理双黑缺陷
双黑缺陷
【数据结构与算法】手撕红黑树
文章图片
  • 若 x 为黑 r 为黑（r 可能为外结点）：双黑缺陷
  • x 为实际删除结点，r 为替换 x 的结点，p 为 x 的父亲，s 为 x 的兄弟，n 为 s 的孩子
1?? 兄弟 s 为黑，且有红孩子
  • p 到 n 的路径为 LL 型
    【数据结构与算法】手撕红黑树
    文章图片

  • p 到 n 的路径为 LR 型
    【数据结构与算法】手撕红黑树
    文章图片

  • p 到 n 的路径为 RR 型。
    【数据结构与算法】手撕红黑树
    文章图片

  • p 到 n 的路径为 RL 型。
    【数据结构与算法】手撕红黑树
    文章图片

2?? 兄弟 s 为黑，无红孩子
  • 父亲 p 为红
    【数据结构与算法】手撕红黑树
    文章图片

  • 父亲 p 为黑
    【数据结构与算法】手撕红黑树
    文章图片

3?? 兄弟 s 为红
  • s 为 p 的左孩子
    【数据结构与算法】手撕红黑树
    文章图片
经过变换后，问题没有解决，但 r 的兄弟变为黑色，可能转为黑兄弟有红孩子情况（最多需两次旋转），或黑兄弟无红孩子有红父亲情况，需染色。
  • s 为 p 的右孩子
    【数据结构与算法】手撕红黑树
    文章图片
经过变换后，问题没有解决，但 r 的兄弟变为黑色，可能转为黑兄弟有红孩子情况（最多需两次旋转），或黑兄弟无红孩子有红父亲情况，需染色。
代码
1?? 删除时先找到要删除的结点
private RBNode getNode(K key) { RBNode node = this.root; while (node != null) { int cmp = key.compareTo(node.key); if (cmp < 0) { node = node.left; } else if (cmp > 0) { node = node.right; } else { return node; } } return null; }

2?? 删除结点
代码描述
  • 若要被删除的结点的左右子结点都存在，则找到其中序后继（前驱）结点，将中序结点的值赋给该结点，然后令该结点的引用指向中序结点，用来删除该中序结点
  • 令 relpacement 指向结点的非空子结点
  • 若 replacemnet 不为空，即找到了该结点的非空子结点，则用该子结点结点替换该结点。特别注意 parent 属性的赋值。若该结点是黑色，处理双黑缺陷。
  • 若该结点没有子结点，且父结点为空，说明该结点就是根节点，直接删除
  • 若该结点没有子结点，且父结点不是空
    • 若为黑色结点，处理双黑缺陷
    • 删除该结点
private void deleteNode(RBNode node) { if (node.left != null && node.right != null) { //RBNode predecessor = predecessor(node); //node.value = https://www.it610.com/article/predecessor.value; //node = predecessor; RBNode successor = successor(node); node.key = successor.key; node.value = https://www.it610.com/article/successor.value; node = successor; } RBNode replacement = node.left != null ? node.left : node.right; if (replacement != null) { replacement.parent = node.parent; if (node.parent == null) { root = replacement; } else if (node == node.parent.left) { node.parent.left = replacement; } else { node.parent.right = replacement; } node.left = node.right = node.parent = null; if (colorOf(node) == BLACK) { fixAfterRemove(replacement); } } else if (node.parent == null) { root = null; } else { if (colorOf(node) == BLACK) { fixAfterRemove(node); } if (node.parent != null) { if (node == node.parent.left) { node.parent.left = null; } else { node.parent.right = null; } } } }

3?? 处理双黑缺陷
代码描述
  • 只要当前结点不是根节点，且颜色为黑色，循环
    • 如果当前结点是左节点，即为 L 型
      • 令 s 为该结点的右兄弟结点
      • 若 s 为红色，说明该结点的兄弟结点为红色，属于情况三（2），将其转化为情况一或二（兄弟结点 s 变为黑）
      • 若 s 为黑色，且无红孩子，属于情况二（将兄弟结点 s 染红），将 x 赋予 x.parent 向上继续双黑修正
      • 否则，若有红孩子
        • 若为 LL 型，右旋 + 染色，属于情况一（1）
        • 若为 LR 型，左右旋 + 染色，属于情况一（2）
    • 如果当前结点是右节点，即为 R 型
      • 令 s 为该结点的左兄弟结点
      • 若 s 为红色，说明该结点的兄弟结点为红色，属于情况三（1），将其转化为情况一或二（兄弟结点 s 变为黑）
      • 若 s 为黑色，且无红孩子，属于情况二（将兄弟结点 s 染红），将 x 赋予 x.parent 向上继续双黑修正
      • 否则，若有红孩子
        • 若为 RR 型，左旋 + 染色，属于情况一（3）
        • 若为 RL 型，右左旋 + 染色，属于情况一（4）
  • x 有可能最后指向根结点，必须保证为黑色
private void fixAfterRemove(RBNode x) { while (x != root && colorOf(x) == BLACK) { if (x == x.parent.left) { RBNode s = x.parent.right; if (colorOf(s) == RED) { leftRotate(x.parent); setColor(s, BLACK); setColor(x.parent, RED); s = x.parent.right; } if (colorOf(s.left) == BLACK && colorOf(s.right) == BLACK) { setColor(s, RED); x = x.parent; } else { if (colorOf(s.right) == BLACK) { RBNode p = s.parent; rightLeftRotate(p); setColor(s, BLACK); setColor(s.parent, p.color); setColor(p, BLACK); x = root; } else { RBNode p = s.parent; leftRotate(p); setColor(s, colorOf(p)); setColor(p, BLACK); setColor(s.right, BLACK); x = root; // 终止循环 } } } else { RBNode s = x.parent.left; if (colorOf(s) == RED) { setColor(s, BLACK); setColor(x.parent, RED); rightRotate(x.parent); s = x.parent.left; } if (colorOf(s.left) == BLACK && colorOf(s.right) == BLACK) { setColor(s, RED); x = x.parent; } else { if (colorOf(s.left) == BLACK) { RBNode p = s.parent; leftRightRotate(p); setColor(s, BLACK); setColor(s.parent, p.color); setColor(p, BLACK); x = root; } else { RBNode p = s.parent; rightRotate(p); setColor(s, colorOf(p)); setColor(p, BLACK); setColor(s.left, BLACK); x = root; } } } } setColor(x, BLACK); }

总结
【数据结构与算法】手撕红黑树
文章图片

最多涉及 3 次旋转，O(logn) 次染色
AVL 树 vs 红黑树
  • 查找、插入、删除最坏时间复杂度均为 O(logn)。
  • 红黑树平衡性弱于 AVL 树，故查找性能低于 AVL 树。
  • 红黑树插入删除所需的旋转次数较少，插入、删除效率高于 AVL 树。
完整代码
class RBTree, V> { private static final boolean RED = false; private static final boolean BLACK = true; private RBNode root; private void inorder(RBNode root) { if (root != null) { inorder(root.left); System.out.print(root.key + " " + (root.color ? "B" : "R") + " "); inorder(root.right); } }private void preorder(RBNode root) { if (root != null) { System.out.print(root.key + " " + (root.color ? "B" : "R") + " "); preorder(root.left); preorder(root.right); } }public void preorderTraverse() { preorder(this.root); System.out.println(); }public void inorderTraverse() { inorder(this.root); System.out.println(); }public boolean colorOf(RBNode node) { return node != null ? node.color : BLACK; }public void insert(K key, V value) { RBNode t = this.root; if (t == null) { this.root = new RBNode(null, key, value); setColor(root, BLACK); return; } int cmp = 0; RBNode parent = null; while (t != null) { parent = t; cmp = key.compareTo(t.key); if (cmp < 0) { t = t.left; } else if (cmp > 0) { t = t.right; } else { t.value = https://www.it610.com/article/value; return; } } RBNode e = new RBNode(parent, key, value); if (cmp < 0) { parent.left = e; } else { parent.right = e; } // 平衡处理，旋转+变色 fixAfterInsert(e); }private void fixAfterInsert(RBNode x) { setColor(x, RED); while (x != null && x != root && colorOf(x.parent) == RED) { if (x.parent == x.parent.parent.left) { RBNode uncle = x.parent.parent.right; if (colorOf(uncle) == RED) { setColor(x.parent, BLACK); setColor(uncle, BLACK); setColor(x.parent.parent, RED); x = x.parent.parent; } else { if (x == x.parent.right) { leftRightRotate(x.parent.parent); setColor(x, BLACK); setColor(x.right, RED); } else { setColor(x.parent, BLACK); setColor(x.parent.parent, RED); rightRotate(x.parent.parent); } } } else { RBNode uncle = x.parent.parent.left; if (colorOf(uncle) == RED) { setColor(x.parent, BLACK); setColor(uncle, BLACK); setColor(x.parent.parent, RED); x = x.parent.parent; } else { if (x == x.parent.left) { rightLeftRotate(x.parent.parent); setColor(x, BLACK); setColor(x.left, RED); } else { setColor(x.parent, BLACK); setColor(x.parent.parent, RED); leftRotate(x.parent.parent); } } } } setColor(root, BLACK); }private RBNode predecessor(RBNode node) { if (node == null) { return null; } else if (node.left != null) { RBNode p = node.left; while (p.right != null) { p = p.right; } return p; } else { RBNode p = node.parent; RBNode ch = node; while (p != null && ch == p.left) { ch = p; p = p.parent; } return p; } }private RBNode successor(RBNode node) { if (node == null) { return null; } else if (node.right != null) { RBNode p = node.right; while (p.left != null) { p = p.left; } return p; } else { RBNode p = node.parent; RBNode ch = node; while (p != null && ch == p.right) { ch = p; p = p.parent; } return p; } }public void remove(K key) { RBNode node = getNode(key); if (node == null) return; deleteNode(node); return; }private void deleteNode(RBNode node) { if (node.left != null && node.right != null) { //RBNode predecessor = predecessor(node); //node.value = https://www.it610.com/article/predecessor.value; //node = predecessor; RBNode successor = successor(node); node.key = successor.key; node.value = https://www.it610.com/article/successor.value; node = successor; } RBNode replacement = node.left != null ? node.left : node.right; if (replacement != null) { replacement.parent = node.parent; if (node.parent == null) { root = replacement; } else if (node == node.parent.left) { node.parent.left = replacement; } else { node.parent.right = replacement; } node.left = node.right = node.parent = null; if (colorOf(node) == BLACK) { fixAfterRemove(replacement); } } else if (node.parent == null) { root = null; } else { if (colorOf(node) == BLACK) { fixAfterRemove(node); } if (node.parent != null) { if (node == node.parent.left) { node.parent.left = null; } else { node.parent.right = null; } } } }private void fixAfterRemove(RBNode x) { while (x != root && colorOf(x) == BLACK) { if (x == x.parent.left) { RBNode s = x.parent.right; if (colorOf(s) == RED) { leftRotate(x.parent); setColor(s, BLACK); setColor(x.parent, RED); s = x.parent.right; } if (colorOf(s.left) == BLACK && colorOf(s.right) == BLACK) { setColor(s, RED); x = x.parent; } else { if (colorOf(s.right) == BLACK) { RBNode p = s.parent; rightLeftRotate(p); setColor(s, BLACK); setColor(s.parent, p.color); setColor(p, BLACK); x = root; } else { RBNode p = s.parent; leftRotate(p); setColor(s, colorOf(p)); setColor(p, BLACK); setColor(s.right, BLACK); x = root; // 终止循环 } } } else { RBNode s = x.parent.left; if (colorOf(s) == RED) { setColor(s, BLACK); setColor(x.parent, RED); rightRotate(x.parent); s = x.parent.left; } if (colorOf(s.left) == BLACK && colorOf(s.right) == BLACK) { setColor(s, RED); x = x.parent; } else { if (colorOf(s.left) == BLACK) { RBNode p = s.parent; leftRightRotate(p); setColor(s, BLACK); setColor(s.parent, p.color); setColor(p, BLACK); x = root; } else { RBNode p = s.parent; rightRotate(p); setColor(s, colorOf(p)); setColor(p, BLACK); setColor(s.left, BLACK); x = root; } } } } setColor(x, BLACK); }private RBNode getNode(K key) { RBNode node = this.root; while (node != null) { int cmp = key.compareTo(node.key); if (cmp < 0) { node = node.left; } else if (cmp > 0) { node = node.right; } else { return node; } } return null; }private void setColor(RBNode node, boolean color) { if (node != null) { node.color = color; } }private void leftRotate(RBNode g) { if (g != null) { RBNode p = g.right; g.right = p.left; if (p.left != null) { p.left.parent = g; } p.parent = g.parent; if (g.parent == null) { this.root = p; } else if (g.parent.left == g) { g.parent.left = p; } else { g.parent.right = p; } p.left = g; g.parent = p; } }private void rightRotate(RBNode g) { if (g != null) { RBNode p = g.left; g.left = p.right; if (p.right != null) { p.right.parent = g; } p.parent = g.parent; if (g.parent == null) { this.root = p; } else if (g.parent.left == g) { g.parent.left = p; } else { g.parent.right = p; } p.right = g; g.parent = p; } }private void leftRightRotate(RBNode g) { leftRotate(g.left); rightRotate(g); }private void rightLeftRotate(RBNode g) { rightRotate(g.right); leftRotate(g); } }class RBNode, V> { public RBNode parent; public RBNode left; public RBNode right; public boolean color; public K key; public V value; public RBNode(RBNode parent, K key, V value) { this.parent = parent; this.key = key; this.value = https://www.it610.com/article/value; } }

方法测试
public static void main(String[] args) { RBTree tree = new RBTree<>(); Scanner scanner = new Scanner(System.in); int n; n = scanner.nextInt(); while (n-- > 0) { String operation = scanner.next(); String value = https://www.it610.com/article/scanner.next(); if (operation.equals("Insert")) { tree.insert(Integer.parseInt(value), 1); } else { tree.remove(Integer.parseInt(value)); } } tree.inorderTraverse(); System.out.println(); tree.preorderTraverse(); }

输入：
32 Insert 10 Insert 40 Insert 30 Insert 60 Insert 90 Insert 70 Insert 20 Insert 50 Insert 80 Insert 10 Insert 66 Insert 85 Insert 60 Insert 12 Insert 32 Insert 74 Insert 7 Insert 52 Insert -5 Insert 13 Insert 23 Insert 13 Insert 103 Insert 306 Insert 2 Insert -97 Insert 752 Remove 90 Remove 60 Remove 70 Remove 50 Remove 80

输出：
-97 R -5 B 2 R 7 R 10 B 12 B 13 R 20 B 23 R 30 R 32 B 40 B 52 B 66 B 74 B 85 B 103 B 306 R 752 B 66 B 30 R 12 B 7 R -5 B -97 R 2 R 10 B 20 B 13 R 23 R 40 B 32 B 52 B 85 B 74 B 306 R 103 B 752 B

    推荐阅读


    上一篇：如何保证同事的代码不会腐烂（一文带你了解 Alibaba COLA 架构）

    下一篇：[computer|[computer vision] Bag of Visual Word (BOW)