数据机构基础之红黑树实现
介绍
二叉搜索树
二叉树：树的每个节点最多只能有两个子节点
二叉搜索树：
- 左子树不为空，左子树上所有节点的值均小于它的根节点的值
- 右子树不为空，右子树上所有节点的值均大于它的根节点的值
参考图片
查找：搜索值小于当前节点搜左子树，大于当前节点搜右子树，等于表示搜到
插入：类似查找，直到左子树或右子树为空时认为找到了插入位置
遍历：
- 中序遍历：左-根-右（使用较多）
- 前序遍历：根-左-右
- 后序遍历：左-右-根
参考图片
最值：
- 最小值：最左边的节点
- 最大值：最右边的节点
删除：
- 叶节点：直接删（父节点指向空）
- 有一个子节点：由于二叉搜索树的特性，可以直接子承父位
- 有两个子节点：找到后继节点替换（大于该节点的最小节点）
二分查找
二分查找：数组有序情况下，对半查，参考下图
缺点：必须是有序的，而且是数组，不可以是链表
可以看出，二叉搜索树和二分查找有一定的相似度
AVL树
二叉搜索树存在一种极端情况，这种情况下会退化为一个有序链表
由于退化成链表后搜索效率过低，需要设计一种树，在插入元素的时候自动调整两边平衡，保持高查询性能。这里暂不分析AVL树，本节重点是红黑树
AVL树特点：
- 具有二叉树全部特性
- 左子树和右子树高度差最多是1
- 插入或删除时，会涉及到左旋和右旋操作
虽然AVL树解决了二叉搜索树的极端情况，但是由于高度差限制过于严格，导致效率过低
于是引出了红黑树的概念
基础
性质
红黑树具有以下的性质，如果满足那么这棵树就是趋于平衡状态的：
- 每个节点是黑色或红色
- 根节点是黑色
- 叶节点是黑色
- 每个红色节点的两个子节点是黑色，红色节点不能相连
- 任意节点到每个叶节点的路径都包含相同的黑节点，又称黑高
- 如果一个节点存在黑子节点，那么该节点一定有两个子节点
自平衡
- 变色：节点颜色红黑变化
- 左旋：某节点右子节点变成父节点，右子节点的左节点变为它的右节点，左子节点保持不变
- 右旋：某节点左子节点变成父节点，左子节点的右节点变为它的左节点，右子节点保持不变
实现
红黑树的插入等操作会涉及到多种情况，暂不分析，直接上代码，在代码中分析
树节点
// 树节点
static class RBNode<K extends Comparable<K>, V> {
private RBNode parent;
private RBNode left;
private RBNode right;
private boolean color;
private K key;
private V value;
// 构造 get set
// ......
}
左旋实现
/**
* 左旋
* p p
* | |
* x y
* / \ ---> / \
* lx y x ry
* / \ / \
* ly ry lx ly
*
* (1) x.right=y.left
* (2) y.left.parent=x
* (3) y.parent=x.parent
* (4) x.parent=y
*
* @param x 左旋节点
*/
private void leftRotate(RBNode x) {
RBNode y = x.right;
// (1)
x.right = y.left;
// (2)
if (y.left != null) {
y.left.parent = x;
}
// (3)
if (x.parent != null) {
y.parent = x.parent;
if (x == x.parent.left) {
x.parent.left = y;
} else {
x.parent.right = y;
}
} else {
// root
this.root = y;
}
// (4)
x.parent = y;
y.left = x;
}
右旋实现
/**
* 右旋
* p p
* | |
* y x
* / \ ---> / \
* x ry lx y
* / \ / \
* lx ly ly ry
*
* (1) y.left=x.right
* (2) x.right.parent=y
* (3) x.parent=y.parent
* (4) y.parent=x
*
* @param y 右旋节点
*/
private void rightRotate(RBNode y) {
RBNode x = y.left;
// (1)
y.left = x.right;
// (2)
if (x.right != null) {
x.right.parent = y;
}
// (3)
if (y.parent != null) {
x.parent = y.parent;
if (y == y.parent.left) {
y.parent.left = x;
} else {
y.parent.right = x;
}
} else {
// root
this.root = x;
this.root.parent = null;
}
// (4)
y.parent = x;
x.right = y;
}
插入
/**
* 对外的插入
* @param key key
* @param value value
*/
public void insert(K key, V value) {
RBNode node = new RBNode();
node.setKey(key);
node.setValue(value);
// 新节点一定是红色
node.setColor(RED);
insert(node);
}
/**
* 插入实现
* @param node 插入节点
*/
private void insert(RBNode node) {
RBNode parent = null;
RBNode x = this.root;
while (x != null) {
parent = x;
// cmp>0:node.key>x.key->遍历右子树
// cmp=0:node.key=x.key->replace
// cmp<0:node.key<x.key->遍历左子树
int cmp = node.key.compareTo(x.key);
if (cmp > 0) {
x = x.right;
} else if (cmp == 0) {
x.setValue(node.getValue());
return;
} else {
x = x.left;
}
}
node.parent = parent;
if (parent != null) {
// cmp>0:node.key>parent.key->node在parent右子节点
// cmp<0:node.key<parent.key->node在parent左子节点
int cmp = node.key.compareTo(parent.key);
if (cmp > 0) {
parent.right = node;
} else {
parent.left = node;
}
} else {
this.root = node;
}
// 恢复平衡
insertFixup(node);
}
恢复平衡
private void insertFixup(RBNode node) {
this.root.setColor(BLACK);
// 父节点
RBNode parent = parentOf(node);
// 父节点的父节点
RBNode gparent = parentOf(parent);
// 父节点为黑色直接平衡
// 父节点为红色应分多种情况
if (parent != null && isRed(parent)) {
// 父节点的父节点的另一个子节点（叔叔）
RBNode uncle = null;
// 父节点是爷节点左节点
if (parent == gparent.left) {
uncle = gparent.right;
/**
* | |
* gp(B) gp(R)
* / \ ---> / \
* p(R) u(R) p(B) u(B)
* / /
* n(R) n(R)
*/
if (uncle != null && isRed(uncle)) {
// 重新染色后下一轮处理
setBlack(parent);
setBlack(uncle);
setRed(gparent);
insertFixup(gparent);
return;
}
if (uncle == null || isBlack(uncle)) {
/**
* | |
* gp(B) p(B)
* / \ ---> / \
* p(R) u(B) n(R) gp(R)
* / \
* n(R) u(B)
*/
if (node == parent.left) {
setBlack(parent);
setRed(gparent);
// 右旋
rightRotate(gparent);
return;
}
/**
* | |
* gp(B) gp(B)
* / \ ---> / \ ---> 上一步
* p(R) u(B) n(R) u(B)
* \ /
* n(R) p(R)
*/
if (node == parent.right) {
leftRotate(parent);
insertFixup(parent);
// 右旋
return;
}
}
} else {
// 父节点是右节点
uncle = gparent.left;
/**
* | |
* gp(B) gp(R)
* / \ ---> / \
* u(R) p(R) u(B) p(B)
* / /
* n(R) n(R)
*/
if (uncle != null && isRed(uncle)) {
// 重新染色后下一轮处理
setBlack(parent);
setBlack(uncle);
setRed(gparent);
insertFixup(gparent);
return;
}
// 不存在叔节点
if (uncle == null || isBlack(uncle)) {
/**
* | |
* gp(B) p(B)
* / \ ---> / \
* u(B) p(R) gp(R) n(R)
* \ /
* n(R) u(R)
*/
if (node == parent.right) {
setBlack(parent);
setRed(gparent);
leftRotate(gparent);
return;
}
/**
* | |
* gp(B) gp(B)
* / \ ---> / \ ---> 上一步
* u(B) p(R) u(B) n(R)
* / \
* n(R) p(R)
*/
if (node == parent.left) {
rightRotate(parent);
insertFixup(parent);
return;
}
}
}
}
}
代码
最终代码参考链接：https://github.com/EmYiQing/RBTree