实现
红黑查找树是2-3树的具体实现
1. 替换3-结点
- 红黑树的基本思想:用标准的二叉查找树(全是2-结点)和一些额外信息(替换3-结点)来表示2-3查找树
- 结点类型:(结点的颜色指的是指向该结点的链接颜色)
- 红链接:将两个2-结点连成3-结点
- 黑链接:2-3树中的普通链接
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;
}
}
2. 等价定义
- 红链接均为左链接
- 没有一个结点同时和两条红链接相连(4-结点)
- 该树是黑色平衡,即任意空链接到根结点的路径上黑链接数量相同
3. 一一对应
将红黑树中所有红链接画水平,那所有空链接到根结点的距离都将相同.再将红链接相连的结点合并,即可得到2-3树.红黑树结合了二叉树的高效查找和2-3树的平衡插入
4. 主要操作
4.1 旋转
某些操作下,可能出现红色右链接或两个连续红链接,需要旋转改变红链接指向,旋转操作保证了有序性和完美平衡性
- 左旋:避免产生右红链接
- 右旋:处理左侧两个连续红链接
Node rotateLeft(Node h){
Node x = h.right;
h.right = x.left;
x.left = h;
x.color = h.color;//初始h的颜色不确定
h.color = RED;//旋转后左链接置红色
x.N = h.N;
h.N = 1+size(h.left)+size(h.right);
return x;
}
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;
}
4.2 插入
4.2.1 向2-结点插入新键
当只有一个2-结点时,插入一个新键后立刻旋转
- 新键<老键:增加红色结点,新树等价于3-结点
- 新键>老键:增加红色结点,但产生红右链,
root=rotateLeft(root)
,旋转修正
4.2.2 向双键树(3-结点)插入新键
- 新键>原数中两个键:最简单的情况,直接连接到3-结点右链接.此时树是平衡的,将两个链接的颜色由黑变红,即得到一棵由三个结点组成的,高为2的平衡树,真好对于2-3树
- 新键<原数中两个键:连接到最左边的空链接,形成了连续两条红链接(4-结点),只需把上层红链接右旋转即可回到情况一
- 新键介于二者之间:连接到左结点的右链(红色),有形成两条连续红链接,将右链左旋,回到情况二
4.2.3 颜色转换
在上述向双键树插入新键操作后,子结点都由红变黑,父结点变红,这是局部变换,不会影响整棵树的黑色平衡性
private void flipColors(Node h){
h.color = RED;
h.left.color = BLACK;
h.right.color = BLACK;
}
4.2.4 根结点总为黑色
红色结点说明结点是3-结点的一部分,但根结点并不满足,则每次插入后根结点都设为黑,且每当根结点由红变黑,树高加1
4.2.5 红链接向上传递
在2-3树中,在一个3-结点下插入新键->临时创建4-结点->分解,传递中间值到父结点->父结点是一个2-结点或为根结点->若为后者,则分解根结点.
对应到红黑树中就是红链接向上传递,插入->旋转->颜色转换->红链接转移至中结点->重复(和新插入结点效果一样)->直到非红右链接/非连续红链接/非根结点
4.2.6 插入算法
- 插入操作只有以下三种:
- 左子结点黑色,右子结点红色->左旋
- 左子结点和左子结点的左子结点都为红色->右旋
- 左右子结点都为红色->颜色转换
红黑树平衡性的调整是自下而上的,所以在put()递归插入语句后,再用if判断以上三种情况,并且,三条语句有顺序(根据4.2.2分析)
public class RedBlackBST<Key extends Comparable<Key>, Value > {
private Node root;
private static final boolean RED = true;
private static final boolean BLACK = false;
private class Node{}
private boolean isRed(Node x){
if (x == null) return false;
return x.color == RED;
}
private Node rotateLeft(Node h){}
private Node rotateRight(Node h){}
private void flipColors(Node h){}
public int size(){ return size(root);}
private int size(Node h){
if (h == null) return 0;
else return h.N;
}
public void put(Key key, Value val){
root = put(root,key,val);
root.color = BLACK;
}
private Node put(Node h, Key key, Value val){
if (h == null){
//新建结点都用红链接
return new Node(key, val, 1, RED);
}
int cmp = key.compareTo(h.key);
if (cmp < 0) h.left = put(h.left, key, val);//小于key,进入左子树
else if(cmp > 0) h.right = put(h.right, key, val);//大于key,进入右子树
else h.val = val;//已存在,则更新val
//处理右侧红链接
if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
//处理连续红链接
if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
//颜色转换
if (isRed(h.left) && isRed(h.right)) flipColors(h);
h.N = size(h.right)+size(h.left)+1;
return h;
}
}
4.3 删除
4.3.1 自顶向下的2-3-4树
2-3-4树中允许存在4-结点,它的插入算法和2-3数的删除算法类似,因此作为引导
- 插入: 沿着路径向下进行变换,始终保持当前结点非4-结点(这样树底才有空间插入新键),沿查找路径向上进行变换是为了将之前创建的4-结点配平
- 向下变换:
- 根结点是4-结点,分解为三个2-结点,树高加一
- 父结点为2-结点的4-结点,将中间结点上移构成3-结点,剩下拆分为两个2-结点
- 父结点为3-结点的4-结点,将中间结点上移构成4-结点,剩下拆分为两个2-结点
- 不会构建出出现父结点和子结点同时为4-结点的情况
- 树底部只可能为2-/3-结点,插入扩大一个即可
- 向上变换:即put()中的递归后rotate()处理
- 红黑树实现2-3-4插入:
- 4-结点由三个2-结点表示
- 向下时分解4-结点,进行颜色转换
- 向上时旋转配平4-结点
- 只需要将colorFlip()语句及其if语句放在null测试和比较操作之间,就可以实现上述算法
- 允许4-结点存在,即允许连续两个左红链接存在,所以语句提前在比较执行put()前,再下次put()时前在调整颜色(分解4-结点)—向下
- 两个方向rotate()依旧在put()后,则在向上过程中配平4-结点—向上
- 向下变换:
4.3.2 删除最小键
- 考虑:在树底部删除3-结点删除最小键容易实现,但若从2-结点删除一个结点,会留下一个空链接,破坏平衡性
- 因此:删除最小键时,沿着左链接向下变换,确保当前结点非2-结点(可能是3-结点或者临时4-结点)
- 根结点的两种可能:
- 根结点是2-结点且两个子结点也是2-结点:将三个结点合并为一个4-结点
- 否则需要保证根结点的左子结点非2-结点,必要时从其右兄弟结点取一个键
- 沿着左链接向下时:
if(!isRed(h.left) && !isRed(h.left.left))
- 若当前结点左子结点非2-结点(h.left或h.left.left中一个为红色,则h.left就在一个3-结点中),完成,继续左下深入
- 若当前结点左子结点是2-结点而亲兄弟非2-结点,将右子结点的兄弟结点中一个键移动到左子结点中
- 若当前结点左子结点和兄弟结点都是2-结点,将左子结点,父结点中的最小键,左子结点最近兄弟结点合并为一个4-结点,则父结点从3-变为2-或4-变为3-
- 最终:得到一个含有最小键的3-结点或者4-结点,将其删除,在回头向上分解4-结点(递归)
- 根结点的两种可能:
//配平4-结点函数,只有第一句话不同,其余和put最后五句一致
private Node balance(Node h){
if (isRed(h.right)) h = rotateLeft(h);
if(!isRed(h.left) && isRed(h.right)) rotateLeft(h);
if(isRed(h.left) && isRed(h.left.left)) rotateRight(h);
if(isRed(h.left) && isRed(h.right)) flipColors(h);
h.N = size(h.right) + size(h.left)+1;
return h;
}
//删除时的颜色转换与插入时刚好相反
private void delFlipColors(Node h){
h.color = BLACK;
h.left.color = RED;
h.right.color = RED;
}
public void deleteMin(){
if(!isRed(root.left) && !isRed(root.right))//根结点三个2-结点
root.color = RED;//为后续颜色变换准备
deleteMin(root.left);
if(!isEmpty()) root.color = BLACK;//根结点始终为黑色
}
private Node deleteMin(Node h){
if (h.left == null) return null;//找到左链最底,返回null
if(!isRed(h.left) && !isRed(h.left.left))//h.left是2-结点
h = moveRedLeft(h);//借助兄弟结点
h.left = deleteMin(h.left);
return balance(h);
}
private Node moveRedLeft(Node h){
delFlipColors(h);//Min:默认形成4-结点
if (isRed(h.right.left)){//Min:当右兄弟非2-结点,借出一个键给左兄弟
h.right = rotateRight(h.right);
h = rotateLeft(h);
}
return h;
}
示例
4.3.3 删除最大键
- 删除最大键的思想和删除最小键一样
- 对根结点的处理:同上
- 沿着右链接向下时:
- 若当前结点的左子结点非2-结点,则左旋转左子结点,成为父结点,新的右子结点一定非2-结点,为后续删除创造条件
if(!isRed(h.left) && !isRed(h.left.left))
- 若当前结点右子结点非2-结点(h.right或h.right.left中一个为红色,则h.left就在一个3-结点中),完成,继续右下深入
- 若当前结点右子结点是2-结点而左兄弟非2-结点,将右子结点,父结点中的最大键,最近左兄弟结点合并为一个4-结点
- 若当前结点右子结点和兄弟结点都是2-结点,则将左子结点旋转,即移动一个键到右子结点
- 最终:得到一个含有最大键的3-结点或者4-结点,将其删除,在回头向上分解4-结点(递归)
//删除最大键
public void deleteMax(){
if(!isRed(root.left) && !isRed(root.right))//根结点三个2-结点
root.color = RED;//为后续颜色变换准备
root = deleteMax(root);
if (!isEmpty()) root.color = BLACK;
}
private Node deleteMax(Node h){
if (isRed(h.left)) h = rotateRight(h);//左侧非2-结点右旋转
if(h.right == null) return null;//找到右链底部,返回null
if (!isRed(h.right) && !isRed(h.right.left))
h = moveRedRight(h);//从左链借来键
h.right = deleteMax(h.right);
return balance(h);
}
private Node moveRedRight(Node h){
//delMin与delMax这两步含义不同
delFlipColors(h);//Max:默认右子结点变为非2-结点
if (!isRed(h.left.left))//Max:当左兄弟是2-结点,则形成4-结点
h = rotateRight(h);
return h;
}
示例
4.3.4 删除操作
- 删除和delMin/delMax都要保证当前结点非2-结点,若最终找到结点在底部(左链接/右链接),则直接删除,否则就用右子树最小结点键值与其他交换,再删除右子树最小键
public void delete(Key key){
if(!isRed(root.left) && !isRed(root.right))//根结点三个2-结点
root.color = RED;//为后续颜色变换准备
root = delete(root, key);
if (!isEmpty()) root.color = BLACK;
}
private Node delete(Node h, Key key){
if(key.compareTo(h.key) < 0){//cmp < 0,类比delMin
if(!isRed(h.left) && !isRed(h.left.left))
h = moveRedLeft(h);
h.left = delete(h.left, key);
}
else{//cmp >= 0,类比delMax
if(isRed(h.left)) h = rotateRight(h);
if(key.compareTo(h.key) == 0 && (h.right == null)) return null;//找到结点,且无右子树,直接删除
if(!isRed(h.right) && !isRed(h.right.left)) h = moveRedRight(h);
if(key.compareTo(h.key) == 0){//找到结点,且有后续结点,则用右子树最小结点键值替换父结点,再删去右子树最小结点
h.val = get(h.right, min(h.right).key);
h.key = min(h.right).key;
h.right = deleteMin(h.right);
}
else h.right = delete(h.right, key);
}
return balance(h);
}
示例
5. 红黑树性质
5.1 性能分析
- 大小为N的红黑树高度不超过2lgN
最坏情况是对应2-3树最左边路径全是3-结点而其余都为2-结点 - 大小为N的红黑树,根结点到任意结点的平均路径长度为~1.00lgN
- 红黑树中,以下操作在最坏情况下是对数级别的:
get(),put(),min(),max(),floor(),ceiling(),rank(),select(),deleteMin(),deleteMax(),delete(),range()
红黑树是第一个可以保证**对数级别插入和查找的符号表实现**
5.2 各种符号表实现性能总结
算法 | 最坏查找 | 最坏插入 | 最优查找 | 最坏插入 | 支持有序操作 |
---|---|---|---|---|---|
顺序查询(无序链表) | N | N | N/2 | N | 否 |
二分查找(有序数组) | lgN | N | lgN | N/2 | 是 |
BST | N | N | 1.39lgN | 1.39lgN | 是 |
红黑树 | 2lgN | 2lgN | 1.00lgN | 1.00lgN | 是 |