1 2-3树
添加新元素
- 第一种:添加进 2 节点,形成一个3节点;
- 第二种: 添加进 3 节点,暂时形成一个 4 节点;
2 红黑树添加节点
2.1 保持根节点是黑色,左旋转
node.right = x.left
x.left = node
x.color = node
node.color = RED
private Node leftRoatate(Node node){
Node x = node.right;
node.right = x.left;
x.left = node;
x.color = node.color;
node.color = RED;
return x;
}
3 红黑树添加新的元素
- 维护的时间: 与 AVL 树类似,添加节点后回溯向上维护
RBTree.java
package tree;
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;
}
}
private Node root;
private int size;
public RBTree() {
root = null;
size = 0;
}
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
private boolean isRed(Node node) {
if (node == null) {
return BLACK;
}
return node.color;
}
private Node leftRoatate(Node node){
Node x = node.right;
node.right = x.left;
x.left = node;
x.color = node.color;
node.color = RED;
return x;
}
public void add(K key, V value) {
root = add(root, key, value);
root.color = BLACK;
}
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;
}
if(isRed(node.right) && !isRed(node.left)){
leftRoatate(node);
}
if(isRed(node.left) && isRed(node.left.left)){
rightRotate(node);
}
if(isRed(node.left) && isRed(node.right)){
flipColors(node);
}
return node;
}
private void flipColors(Node node) {
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
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;
}
}
4 红黑树的性能总结
- 对于完全随机的数据,普通的二分搜索树有优势;但是缺点是:极端情况退化为链表;
- 对于查询较多的情况,AVL 树有优势;
- 红黑树牺牲了平衡性(2logn 的高度),统计性能更优(综合增删改查所有的操作)