一、红黑树定义
- 二分搜索树
- 平衡二叉树
- 每个节点是红色或者黑色
- 根节点是黑色
- 每一个叶子节点(最后空节点)是黑色的
- 如果一个节点是红色,那么孩子节点都是黑色
- 从任意一节点到叶子节点经过的黑色节点是一样的
1. 太过生硬
2. 和2-3树的等价性,理解2-3树和红黑树直接的关系
二、 2-3树介绍
- 满足二分搜索树
- 节点可以存放一个元素或者两个元素
- 每一个节点或者有2个孩子或者有3个孩子(2节点、3节点)
- 2-3 树是一只绝对的平衡的树(任意一节点左右子树高度相等))
三、2-3树通过什么机制维持它的绝对平衡
插入不是根节点 插入3节点 父亲为2节点, 直接让父亲节点变成3节点 插入3节点 父亲为3节点,向上融合父节点变成临时4节点,然后4节点拆成两个2节点
四、红黑树和2-3树的等价性
Red 等价于 3节点
五、红黑树的实现
public static final boolean RED = true;
public 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;
}
}
红黑树更多考察你的原理,旋转之类的不会白板编程红黑树的实现操作
五、维持根节点是黑色
// 向红黑树中添加新的元素(key, value)
public void add(K key, V value){
root = add(root, key, value);
root.color = BLACK; // 最终根节点为黑色节点
}
六、左旋转
// node x
// / \ 左旋转 / \
// T1 x ---------> node T3
// / \ / \
// T2 T3 T1 T2
private Node leftRotate(Node node){
Node x = node.right;
// 左旋转
node.right = x.left;
x.left = node;
x.color = node.color;
node.color = RED;
return x;
}
// 颜色翻转
private void flipColors(Node node){
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
七、右旋转
// node x
// / \ 右旋转 / \
// x T2 -------> y node
// / \ / \
// y T1 T1 T2
private Node rightRotate(Node node){
Node x = node.left;
// 右旋转
node.left = x.right;
x.right = node;
x.color = node.color;
node.color = RED;
return x;
}
八、红黑树添加新节点
// 向以node为根的红黑树中插入元素(key, value),递归算法
// 返回插入新节点后红黑树的根
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 // key.compareTo(node.key) == 0
node.value = value;
if (isRed(node.right) && !isRed(node.left))
node = leftRotate(node);
if (isRed(node.left) && isRed(node.left.left))
node = rightRotate(node);
if (isRed(node.left) && isRed(node.right))
flipColors(node);
return node;
return node;
}
九、红黑树的性能总结
- 对于完全随机的数据,普通的二分搜索树很好用。缺点:极端情况下会退化成链表
- 对于查询较多的,AVL树很好用
- 红黑树牺牲了平衡性,最高的高度达到2logn 比AVL 树高
- 红黑树统计性能更优(综合增删改查操作)