B树
B树是一种平衡的多路搜索树, 多用于文件系统, 数据库的实现
特点
- 一个节点可以存储超过2 个元素, 可以拥有超过2 个子节点
- 拥有二叉搜索树的一些性质
- 平衡, 每个节点的所有子树高度一致
- 比较矮
m阶B树的性质(m>2)
假设一个节点存储的元素个数为x
- 根节点1 <= x <= m-1
- 非根节点 ceiling(m/2)-1 <= x <= m-1
- 如果哟子节点, 子节点个数 y = x + 1
- 根节点: 2 <= y <= m
- 非根节点: ceiling(m/2) <= x <= m
- 比如m = 3, 2 <= y <= 3, 因此可以称为(2, 3)树, 2-3树
- 比如m = 4, 2 <= y <= 4, 因此可以称为(2, 4)树, 2-3-4树
- ......
B 树和二叉搜索树
B树和二叉搜索树在逻辑上是等价的
多代合并, 获得一个超级节点
2代合并, 最多4个子节点, 至少是4阶B树
3代合并, 最多8个子节点, 至少是8阶B树
m代合并, 最多2^n个子节点, 至少是2^n阶B树
m 阶B 树, 最多需要log2(m) 代合并
搜索
跟二叉搜索树类似
- 先从节点内部从小到大开始搜索
- 命中, 即结束
- 否则, 再去对应子节点中搜索元素, 重复1 步骤
添加
新添加元素必定添加到子节点, 如果超过元素限制数量, 则需要上溢(overflow)
上溢节点元素个数为m
假定, 上溢节点最中间元素位置为k
将k 位置元素向上与父节点合并
将[0, k-1] 和[k+1, m-1] 位置的元素分裂成2 个子节点
这2 个子节点元素个数, 必然都不会低于最低限制m/2 - 1
第一次分裂完后, 可能造成父节点上溢, 重复步骤, 直到不上溢位置, 最极端情况一直分裂到根节点
删除
叶子节点, 直接删除即可
非叶子节点, 先找到前驱或者后继, 覆盖所需删除元素值, 再把前驱或后继删除
非叶子节点前驱或后继必定在叶子节点中, 所以最终删除掉的也是叶子节点
叶子节点删除掉一个元素后, 个数可能低于最低限制m/2 - 1, 这需要下溢操作
下溢节点元素数量必然等于m/2 - 2
如果下溢节点临近的兄弟节点, 有至少m/2 个元素, 可以向其借一个
将父节点元素b, 插入到下溢节点0 位置
兄弟节点元素a, 代替父节点元素b
这样的操作称为旋转
如果下溢节点临近兄弟节点, 只有m/2-1 个元素
将父节点元素b 挪下来跟左右子节点合并
合并后节点元素个数不超过m-1
这样的操作可能导致父节点下溢, 直到根节点
红黑树
红黑树是一种自平衡的二叉搜索树
满足以下5 个性质
- 节点是RED 或者BLACK
- 跟节点为BLACK
- 叶子节点, 外部节点, 空节点, 都是BLACK
- RED 节点子节点都是BLACK
- RED 的parent 都是BLACK
- 从根节点到叶子结点所有路径上不能有2 个连续的RED 节点
- 从任一节点到叶子节点所有路径都包含相同数量的BLACK 节点
红黑树等价变换
- 红黑树和4 阶B 树具有等价性
- BLACK 节点与他的RED 节点融合在一起, 形成一个B 树节点
- 红黑树的BLACK 节点个数与4 阶B 树节点总个数相等
添加
B 树中, 新元素必定添加到叶子结点中
4 阶B 树所有节点元素个数x 都符合1 <= x <= 3
添加节点时默认为红色节点, 红黑树的性质尽快满足, 1, 2, 3, 5, 只需要调整, 满足性质4 即可
如果添加的是根节点, 直接染成BLACK
添加-1
有4 中情况满足性质4, parent 为BLACK
也满足所有性质, 不用做额外处理
添加-2
有8 中情况不满足红黑树性质4, parent 为RED
前4 种属于B 树上溢情况
添加 - 修复 - LL\RR
uncle 不是RED
- parent 染成BLACK, grand 染成RED
- grand 单旋
添加 - 修复 - LR\RL
uncle 不是RED
- 自己染成BLACK, grand 为RED
- 双旋操作
添加 - 修复 - 上溢LL
uncle 为RED
- parent uncle 染成BLACK
- grand 向上合并
- 上溢节点染成RED, 当做新节点进行处理
添加 - 修复 - 上溢RR
uncle 为RED
- parent uncle 染成BLACK
- grand 向上合并
- 该节点染红, 当做新添加节点处理
添加 - 修复 - 上溢LR
uncle 为RED
- parent uncle 染成BLACK
- grand 向上合并
- 该节点染红, 当做新节点处理
添加 - 修复 - 上溢RL
删除
最后真正被删除的元素都在叶子节点中
删除 RED节点
直接删除, 也满足红黑树性质
删除 - BLACK节点
三种情况
- 拥有2 个RED 子节点的BLACK 节点
- 会找到替代子节点删除
- 拥有1 个RED 子节点的BLACK 节点
- BLACK 叶子节点
删除 - 拥有1个RED 子节点的BLACK节点
用以替代的子节点是RED
将替代子节点染成BLACK 可以保持红黑树性质
删除 - BLACK叶子节点 - sibling为BLACK
- BLACK 叶子节点被删除后, 会导致B 树节点下溢, 比如删除88
- 如果sibling 至少有一个RED 子节点
- 进行旋转操作
- 旋转后, 中心节点继承parent 颜色
- 左右节点染成BLACK
删除 - BLACK叶子节点 - sibling为BLACK
sibling 没有1 个RED 子节点
将sibling 染成RED, parent 染成BLACK, 满足红黑树性质
删除 - BLACK叶子节点 - sibling为RED
sibling 为RED
- sibling 染成BLACK, parent 染成RED, 进行旋转
- 变成sibling 为BLACK 情况
红黑树的平衡
满足5 条性质, 保证可以红黑树等价于4 阶B 树
相比AVL 树, 红黑树的平衡标准比较宽松, 没有一条路径会大于其他路径的2 倍
是一种弱平衡, 黑高度平衡
最大高度为2*log2(n+1), 依然是O(logn)
搜索, O(logn)
添加, O(logn), O(1) 次旋转操作
删除, O(logn), O(1) 次旋转操作
红黑树和AVL 树对比
AVL
- 平衡标准严格, 每个左右子树高度差不超过1
- 最大高度, 1.44 * log2(n+2) -1.328, 100w 节点, AVL 树最高为28
- 搜索, 添加, 删除都是O(logn), 添加O(1)旋转调整, 删除最多O(logn) 旋转调整
红黑树
- 平衡标准宽松, 没有一条路径大于其他两倍
- 最大高度2 * log2(n+1), 100w 节点, 红黑树最高40
- 搜索, 添加, 删除都是O(logn), 添加和删除仅需O(1) 旋转
搜索次数远远大于插入和删除, 选择AVL, 次数差不多选择红黑树
相对于AVL, 红黑树牺牲部分平衡性换取插入和删除操作时的少量选择操作, 整体上优于AVL
红黑树平均统计性能优于AVL, 实际应用中更多选择红黑树
public class RBTree<E> extends BBST<E> {
private static final boolean RED = false;
private static final boolean BLACK = true;
public RBTree() {
this(null);
}
public RBTree(Comparator<E> comparator) {
super(comparator);
}
@Override
protected void afterAdd(Node<E> node) {
Node<E> parent = node.parent;
// 如果是根节点
if (parent == null) {
black(node);
return;
}
// 如果父节点是黑色, 直接返回
if (isBlack(parent)) return;
// 叔父节点
Node<E> uncle = parent.sibling();
// 祖父节点
Node<E> grand = red(parent.parent);
if (isRed(uncle)) { // 叔父节点是红色
black(parent);
black(uncle);
// 把祖父节点当做是新添加的节点
afterAdd(red(grand));
return;
}
// 叔父节点不是红色
if (parent.isLeftChild()) {// L
if (node.isLeftChild()) { // LL
black(parent);
} else { // LR
black(node);
rotateLeft(parent);
}
rotateRight(grand);
} else { // R
if (node.isLeftChild()) {// RL
black(node);
rotateRight(parent);
} else { // RR
black(parent);
}
rotateLeft(grand);
}
}
@Override
protected void afterRomove(Node<E> node) {
// 如果删除的节点是红色
// if (isRed(node)) return;
// 用以取代node 的子节点是红色
if (isRed(node)) {
black(node);
return;
}
Node<E> parent = node.parent;
// 删除的是根节点
if (parent == null) return;
// 删除的时黑色叶子节点
// 判断被删除的node 是左还是右边
boolean left = parent.left == null || node.isLeftChild();
Node<E> sibling = left ? parent.right : parent.left;
if (left) {// 被删除的节点在左边, 兄弟节点在右边
if (isRed(sibling)) { // 兄弟节点是红色
black(sibling);
red(parent);
rotateLeft(parent);
sibling = parent.right;
}
// 兄弟节点必然是黑色
if (isBlack(sibling.left) && isBlack(sibling.right)) {
// 兄弟节点没有一个是红色子节点, 父节点要向下合并
boolean parentBlack = isBlack(parent);
black(parent);
red(sibling);
if (parentBlack) {
afterRomove(parent);
}
} else {// 兄弟节点至少有一个是红色子节点
// 兄弟节点的左边是黑色, 兄弟要旋转
if (isBlack(sibling.right)) {
rotateRight(sibling);
sibling = parent.right;
}
color(sibling, colorOf(parent));
black(sibling.right);
black(parent);
rotateLeft(parent);
}
} else {// 被删除的节点在右边, 兄弟节点在左边
if (isRed(sibling)) { // 兄弟节点是红色
black(sibling);
red(parent);
rotateRight(parent);
sibling = parent.left;
}
// 兄弟节点必然是黑色
if (isBlack(sibling.left) && isBlack(sibling.right)) {
// 兄弟节点没有一个是红色子节点, 父节点要向下合并
boolean parentBlack = isBlack(parent);
black(parent);
red(sibling);
if (parentBlack) {
afterRomove(parent);
}
} else {// 兄弟节点至少有一个是红色子节点
// 兄弟节点的左边是黑色, 兄弟要旋转
if (isBlack(sibling.left)) {
rotateLeft(sibling);
sibling = parent.left;
}
color(sibling, colorOf(parent));
black(sibling.left);
black(parent);
rotateRight(parent);
}
}
}
private Node<E> color(Node<E> node, boolean color) {
if (node == null) return node;
((RBNode<E>)node).color = color;
return node;
}
private Node<E> red(Node<E> node) {
return color(node, RED);
}
private Node<E> black(Node<E> node) {
return color(node, BLACK);
}
private boolean colorOf(Node<E> node) {
return node == null ? BLACK : ((RBNode<E>)node).color;
}
private boolean isRed(Node<E> node) {
return colorOf(node) == RED;
}
private boolean isBlack(Node<E> node) {
return colorOf(node) == BLACK;
}
@Override
protected Node<E> createNode(E element, Node<E> parent) {
return new RBNode<>(element, parent);
}
private static class RBNode<E> extends Node<E> {
boolean color = RED;
public RBNode(E element, Node<E> parent) {
super(element, parent);
}
@Override
public String toString() {
String str = "";
if (color == RED) {
str = "R_";
}
return str + element.toString();
}
}
}
