2-3树
- 2-3树是一种绝对平衡的二分搜索树；
- 2-3树中存在2种节点：2节点和3节点；
- 2节点：每个节点存1个元素，有2个孩子；
- 3节点：每个节点存2个元素，有3个孩子；
- 新添加的元素都要融合进叶子节点，或者融合成3节点，或者融合成临时的4节点；
- 融合成临时的4节点后，就要将4节点拆成3个2节点，然后将中间的节点向上融合到其父节点，融合后的结构如果任然是4节点，则继续拆；
红黑树
- 红黑树和2-3树是等价的；
- 红黑树中的每个节点只存一个元素，因而实现上更简单；
- 红黑树中的节点要么是红色，要么是黑色；
- 红黑树中红节点表示其和其父节点一起表示2-3树中的一个3节点；
- 红黑树中红节点都是向左倾斜的，定义出来的；
- 红黑树中的节点有一个表示其颜色的属性；
- 红黑树中的红节点对应2-3树中3节点中存储的左边的元素；
- 红黑树中根节点是黑色的；
-
红黑树中从任意节点到叶子节点（最后的空节点），经过的黑色节点是一样的； *
- 红黑树中一个节点是红色的，那么他的孩子节点都是黑色的；
- 红黑树中一个节点是黑色的，那么他的右孩子是黑色的；
- 红黑树中每个叶子节点（最后的空节点）是黑色的；
- 红黑树是保持“黑平衡”的二叉树，严格意义上，不是平衡二叉树；
红黑树时间复杂度分析
- 红黑树的最大高度：2logn；
- 红黑树的时间复杂度为O(logn)；
- 红黑树添加删除更快，AVL树查询更快；
- 树结构不怎么变用AVL树，经常添加删除操作用红黑树；
红黑树基础代码
- 红黑树中每个节点在初始化的时候都是红节点；
- 每个空节点（null）是黑节点；
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;
}
// 判断节点node的颜色
private boolean isRed(Node node){
if(node == null)
return BLACK;
return node.color;
}
}
