文章看起来很长是因为图片多, 且后面的代码注释较多
本文介绍的是左倾红黑树, 用于初步了解红黑树 学红黑树可以先从2-3树开始, 因为红黑树和2-3树是等价的, 我们可以先理解简单的2-3树, 然后再把它转为红黑树 红黑树是一种二分搜索树, 所有要符合二分搜索树存储的性质
2-3树也是满足二分搜索树的基本性质, 但是它的一个节点可以存放一个或两个元素 可以存放两个孩子的节点称为2节点, 存放三个的称为3节点 2-3树的结构如下: 如果是2节点, 那么左孩子都比自己小, 右孩子都比自己大 如果是3节点, 那么左孩子都比自己大, 中间孩子都在自己的两个值之间, 比如22在17和34之间, 右孩子都比自己大 2-3树是一棵绝对平衡的树: 从根节点到任意一个叶子节点经过的节点数量相同, 所以在添加的时候需要遵循一些规则
如果用文字描述理解不了, 就看看下面一个例子吧, 比如依次添加 42, 37, 12, 18 第3步融合之后变成了4节点, 于是拆成一棵二叉树 再添加 6 第6步先是形成一个 4节点, 然后拆成一个二叉树, 因为要维持绝对平衡, 所以要向上融合, 找到37 第7步12和37融合之后刚好是 3节点, 结束 最后添加 11, 5, 添加11比较简单 第10步添加5形成了一个 4节点, 拆成一棵二叉树, 得到第11步 第12步是向上融合, 又形成了一个4节点, 继续拆, 结束 如果你能理解上面的步骤, 那就可以转到红黑树了
只需将2-3树中的 2节点, 3节点 用下面另外两种节点代替, 就可以得到红黑树 (红色节点在左边, 所以这里介绍的是 左倾红黑树, 当然也有 右倾 的) 有的树枝是水平的是为了更直观地体现2-3树和红黑树的关系
算法导论 中的红黑树: 红黑树是一棵具有下列5个特性的二分搜索树: 1. 每个节点或者是红色, 或者是黑色 2. 根节点是黑色的 3. 每一个叶子节点 (这里的叶子节点指最后的空节点, 图中没有画出来) 是黑色的 空树也是红黑树 4. 如果一个节点是红色的, 那么他的孩子节点都是黑色的 5. 从任意一个节点到叶子节点, 经过的黑色节点是一样的 理解了2-3树, 这个也就能理解 因为这个性质, 我们也说红黑树是保持"黑平衡"的二叉树
先像二叉搜索树一样添加元素, 然后向上回溯维护红黑颜色
按照上面的规则, 新添的节点都是要融合的, 或者与 2节点 融合, 形成 3节点; 或者与 3节点 融合, 暂时形成 4节点 因为第一步都是要融合, 所以默认添加的是红色的节点
有两种情况 情况1: 如果添加到左侧, 那最简单, 直接加上即可 情况2: 如果添加到右侧 就要进行一次旋转, 想想2-3树, 也可以看看我之前写的AVL树 Again, 在红黑树中, 空节点当作是黑色的 旋转的代码如下
* 添加元素x到2节点node, 因为在2-3树中, 新添节点要融合, 所以要旋转, 一红一黑表示一个3节点 * 如果添加的节点x在节点node的右侧, 就需要左旋转(node绕x逆时针旋转) * node的左孩子是黑色, 因为是2节点, 右孩子是红色, 因为是新添的, 默认红色 * 添加T1, T2, T3是为了保证普适性 * node x * / \ 左旋转 / \ * T1:B x:R ---------> node:R T3 * / \ / \ * T2 T3 T1 T2 * 这里不严格维护x的颜色, 递归返回后, 上一层递归自会处理 private Node leftRotate(Node node){ Node x = node.right; // 左旋转 node.right = x.left; x.left = node; x.color = node.color; // x代替node的位置, 包括颜色 node.color = RED; // 形成了一个3节点, 所以要变红 return x; }有三种情况 情况1: 新插入的元素比红黑两个元素都大 加完节点6, 得到一个暂时的4节点(第一步), 4节点要拆成二叉树, 所以3, 5, 6这3个元素都是独立的节点, 都应该是黑色的, 但是! 为了维持平衡, 拆出来的二叉树的父节点是要向上融合的 (不懂的看上面的2-3树的添加过程), 所以要变成红色的, 这里节点5要和上面的一个节点融合
可以看到处理完所有节点的颜色都翻转
代码如下
// 添加元素到3节点右侧, 形成一棵二叉树 private void filpColors(Node node){ node.color = RED; node.left.color = BLACK; node.right.color = BLACK; }情况2: 新插入的元素比红黑两个元素都小 第2步得到的是一个4节点, 最后需要做一次颜色翻转 (如情况1, 就不画出来了)
代码如下:
* 添加y到3节点(x, node), 形成了4节点(y, x, node) * 所以需要右旋转将4节点变成二叉树 * node x * / \ 右旋转 / \ * x:R T2:B -------> y:R node:R * / \ / \ * y:R T1 T1 T2 * 你可能注意到如果是二叉树的话, 颜色不太对, 别担心, 后面有颜色翻转 private Node rightRotate(Node node){ Node x = node.left; // 右旋转 node.left = x.right; x.right = node; x.color = node.color; // x代替node的位置, 包括颜色 node.color = RED; return x; }情况3: 新插入的元素在红黑两个元素之间 从第1步到第2步用的是 添加元素到2节点情况2 的方法, 也就是左旋转 从第2步到第3步用的是上一种情况的方法, 也就是右旋转 最后还需要颜色翻转一下 (就没有画出来了)
其实上面的几种添加就是按照下面这条链条在执行: 第0步 对应 添加元素到2节点的情况2 第1步 对应 添加元素到3节点的情况3, 左旋转得到第2步 第2步 对应 添加元素到3节点的情况2, 右旋转得到第3步 第3步 对应 添加元素到3节点的情况1, 颜色翻转, 结束 代码如下:
递归算法 Node add(Node node, K key, V value) { if(node == null){ size++; return new Node(key, value); // 默认插入的是红色节点 } 先像普通二分搜索树一样找到位置, 添加元素 然后再按照上面的流程维护红黑树性质, // 左旋转 if(isRed(node.right) && !isRed(node.left)) node = leftRotate(node); // 右旋转 if(isRed(node.left) && !isRed(node.right)) node = rightRotate(node); // 颜色翻转 if(isRed(node.left) && isRed(node.right)) filpColors(node); return node; }先像二叉搜索树一样添加元素, 然后向上回溯维护红黑颜色 要注意, 根节点一定是黑色的
红黑树并不是严格意义上的平衡二叉树, 它的最大高度是 2logn, 复杂度O(log n), 它牺牲了一定的平衡性, 来换取更优的统计性能(综合增删改查所有的操作) (统计性能很好的还有伸展树Splay Tree, 它是根据局部性原理设计的, 用的越多越容易查到)
如果是建完树后只是查找元素, 不做修改, AVL树比红黑树好 如果是要频繁地添加删除元素, 红黑树更好
红黑树在数据规模大的时候更有优势, 如果数据规模小的话, 用比较简单的算法, 如AVL, 会更有优势 (就像快排用于小规模数据反而会不如插入排序), 如果是随机数的话, 用普通的二分搜索树也是很可的, 如果是比较有序的话就要小心, 普通二分搜索树会退化成链表, 或者很偏斜, 会很慢!
Java标准库中的有序映射TreeMap和有序集合TreeSet都是用红黑树实现的
RBTree.java
public class RBTree<K extends Comparable<K>, V>{ private static final boolean RED = true; // 静态不可修改变量 private static final boolean BLACK = false; private class Node{ public K key; public V value; public Node left, right; public boolean color; public Node(K key, V value){ this.key = key; this.value = value; left = null; right = null; color = RED; // 先融合, 形成3节点或4节点, 再做其他处理 } } private Node root; private int size; public RBTree(){ root = null; size = 0; } public int getSize() { return size; } public boolean isEmpty() { return size == 0; } // 判断节点node的颜色 private boolean isRed(Node node){ if(node == null) return BLACK; return node.color; } /** * 添加元素到2节点node, 因为在2-3树中, 新添节点要融合, 所以要旋转 * 如果添加的节点x在节点node的右侧, 就需要左旋转 * node的左孩子是黑色, 因为是2节点, 右孩子是红色, 因为是新添的, 默认红色 * node x * / \ 左旋转 / \ * T1:B x:R ---------> node:R T3 * / \ / \ * T2 T3 T1 T2 * 这里不严格维护x的颜色, 递归返回后, 上一层递归自会处理 */ private Node leftRotate(Node node){ Node x = node.right; // 左旋转 node.right = x.left; x.left = node; x.color = node.color; // x代替node的位置, 包括颜色 node.color = RED; // 形成了一个3节点, 所以要变红 return x; } /** * 添加y到3节点(x, node), 形成了4节点(y, x, node) * x, y是红色因为和node形成4节点, 也因此T2是黑色的 * 所以需要右旋转将4节点变成二叉树 * node x * / \ 右旋转 / \ * x:R T2:B -------> y:R node:R * / \ / \ * y:R T1 T1 T2 * 你可能注意到如果是二叉树的话, 颜色不太对, 别担心, 后面有颜色翻转 * 如果新添的节点在node和x之间??? */ private Node rightRotate(Node node){ Node x = node.left; // 右旋转 node.left = x.right; x.right = node; x.color = node.color; // x代替node的位置, 包括颜色 node.color = RED; // return x; } // 添加元素到3节点右侧, 形成一棵二叉树 private void filpColors(Node node){ node.color = RED; node.left.color = BLACK; node.right.color = BLACK; } /** * 向红黑树中添加新的元素(key, value) * @param key * @param value */ public void add(K key, V value) { root = add(root, key, value); root.color = BLACK; } /** * 向以node为根的红黑树中插入元素(key, value)，递归算法 * 如果key已存在, 则更新value * @param node * @param key * @param value * @return 插入新节点后红黑树的根 */ private Node add(Node node, K key, V value) { if(node == null){ size++; return new Node(key, value); // 默认插入的是红色节点 } if(key.compareTo(node.key) < 0) node.left = add(node.left, key, value); else if(key.compareTo(node.key) > 0) node.right = add(node.right, key, value); else node.value = value; // 维护红黑树性质 // 左旋转, 2节点, 所以左边非红, 右边红是因为新添默认红 if(isRed(node.right) && !isRed(node.left)) node = leftRotate(node); // 右旋转, 3节点, 所以左边红, 右边黑 if(isRed(node.left) && !isRed(node.right)) node = rightRotate(node); if(isRed(node.left) && isRed(node.right)) filpColors(node); return node; } /** * @return 以node为根节点的红黑树中，key所在的节点 */ private Node getNode(Node node, K key){ if(node == null){ return null; } if(key.equals(node.key)) return node; else if(key.compareTo(node.key) < 0) return getNode(node.left, key); else // key.compareTo(node.key) > 0 return getNode(node.right, key); } public boolean contains(K key) { return getNode(root, key) != null; } public V get(K key) { Node node = getNode(root, key); return node == null ? null : node.value; } public void set(K key, V newValue) { Node node = getNode(root, key); if(node == null) throw new IllegalArgumentException(key + " doesn't exist!"); node.value = newValue; } }感谢bobobo老师!
