平衡查找树
定义
父节点的左子树和右子树的高度之差不能大于1
2-3查找树
定义
2-3树运行每个节点保存1个或者两个的值。对于普通的2节点(2-node)，他保存1个key和左右两个自己点。对应3节点(3-node)，保存两个Key，2-3查找树的定义如下：
- 要么为空，要么：
- 对于2节点，该节点保存一个key及对应value，以及两个指向左右节点的节点，左节点也是一个2-3节点，所有的值都比key要小，右节点也是一个2-3节点，所有的值比key要大。
- 对于3节点，该节点保存两个key及对应value，以及三个指向左中右的节点。左节点也是一个2-3节点，所有的值均比两个key中的最小的key还要小；中间节点也是一个2-3节点，中间节点的key值在两个跟节点key值之间；右节点也是一个2-3节点，节点的所有key值比两个key中的最大的key还要大。
如果中序遍历2-3查找树，就可以得到排好序的序列。在一个完全平衡的2-3查找树中，根节点到每一个为空节点的距离都相同。
变换方法
- 向2-结点插入新键，将2-结点变成3-结点
- 向3-结点插入新键，将3-结点变成4-结点，然后转换成3个2-结点组成的2-3树，树的高度增加1
- 从下往上，依次变换，可以有中间状态，但是最后必须都为2-结点和3-结点
结点变换示意图
红黑树
思想
用标准的二叉查找树和一些额外的信息来表示2-3树。红链接将两个2-结点连接起来构成一个3-结点，黑链接则是2-3树中的普通链接。
定义
红黑树是含有红黑链接并且满足下列条件的二叉查找树：
- 红链接均为左链接
- 没有任何一个结点同时和两个红链接相连
- 该树是完美红黑平衡的，即任意空链接到根节点路径上的黑链接数量相同
相关操作
颜色表示
结点的数据结构：键+值+左右子树+结点总数+颜色
结点的颜色是指指向该节点链接的颜色
旋转
旋转原因：当出现红色右链接或者两条连续的红色链接时
旋转操作：左旋是将两个键中较小者作为根节点变为较大者作为根节点；右旋是将两个键中较大者作为根节点变为较小者作为根节点。旋转后返回一条链接重置父节点中相应的链接。
颜色变化
如果一个结点的两条链接都是红色的，使用flipColors将子结点的颜色由红变黑，同时父结点的颜色由黑变红
根节点的颜色总是黑色
在每次插入后，都需要将根结点的颜色设为黑色。
2-节点插入新键
左边：直接新增红色结点
右边：增加红色结点后，左旋并修正根节点的链接root = rotateLeft(root)
2-结点插入示意图
3-节点插入新键
右边：增加红色结点以后，进行颜色转换
左边：增加红色结点后，右旋，再进行颜色转换
中间：增加红色结点后，先左旋下层链接，在右旋上层链接，在进行颜色转换
3-结点插入示意图
红色链接在树中向上传递
插入点到根节点的路径上的每个结点必须完成以下操作：
- 如果右子结点是红色，而左子结点是黑色==> 左旋
- 如果左子结点是红色而它的左子节点是红色==> 右旋
- 如果左右子结点都是红色==>颜色转换
红色链接传递示例
代码实现
package edu.princeton.cs.algs4.chapter3;
/**
* 使用红黑树实现的符号表
* Created by tianxianhu on 2017/3/7.
*/
public class RedBlackBST<Key extends Comparable<Key>, Value> {
private static final boolean RED = true;
private static final boolean BLACK = false;
private Node root;
private class Node{
Key key;
Value val;
Node left, right;
int N;
boolean color; // 其父节点指向它的链接的颜色
Node (Key key, Value val, int N, boolean color) {
this.key = key;
this.val = val;
this.N = N;
this.color = color;
}
}
private boolean isRed (Node x) {
if (x == null)
return false;
return RED == x.color;
}
public int size() {
return size(root);
}
private int size(Node x) {
if (x == null)
return 0;
return x.N;
}
/**
* 寻找key，找到则更新它的值，否则为它创建一个新节点，同时更新节点数量
* 创建的节点默认为红色，可能会影响红黑树的平衡，需要进行调整
* 1.如果左：黑 右：红 ==> 左旋 ==> 2
* 2.如果左：红 左左：红 ==> 右旋 ==> 3
* 3.如果左：红 右：红 ==> flip
* @param key
* @param val
*/
public void put(Key key, Value val) {
if (key == null) throw new IllegalArgumentException("first argument to put() is null");
if (val == null) {
delete(key);
return;
}
root = put(root, key, val);
root.color = BLACK; // 根节点的颜色始终是黑色的
}
private Node put(Node x, Key key, Value val) {
if (x == null)
return new Node(key, val, 1, RED);
int cmp = key.compareTo(x.key);
if (cmp < 0) {
x.left = put(x.left, key, val);
} else if (cmp > 0) {
x.right = put(x.right, key, val);
} else {
x.val = val;
}
// 调整链接，保证红黑树的平衡
if (isRed(x.right) && !isRed(x.left))
x = rotateLeft(x);
if (isRed(x.left) && isRed(x.left.left))
x = rotateRight(x);
if (isRed(x.left) && isRed(x.right))
flipColors(x);
x.N = size(x.left) + size(x.right) + 1;
return x;
}
/**
* 左旋改变h的右子节点
* 1. 改变链接
* 2. 改变颜色
* 3. 更新计数
* @param h
* @return
*/
private Node rotateLeft(Node h) {
Node x = h.right;
h.right = x.left;
x.left = h;
x.color = h.color;
h.color = RED;
x.N = h.N;
h.N = 1 + size(h.left) + size(h.right);
return x;
}
/**
* 右旋转h的左链接
* 1. 改变链接
* 2. 改变颜色
* 3. 更新计数
*/
private Node rotateRight(Node h) {
Node x = h.left;
h.left = x.right;
x.right = h;
x.color = h.color;
h.color = RED;
x.N = h.N;
h.N = 1 + size(h.left) + size(h.right);
return x;
}
/**
* 左子节点和右子节点都为红色的时候，将左右子节点变成黑色，根节点变成红色
* @param x
*/
private void flipColors(Node x) {
if (x == null)
return;
x.left.color = BLACK;
x.right.color = BLACK;
x.color = RED;
}
//TODO: 待实现
public void delete(Key key) {
}
}
