在 Lab 06 中，我们实现了一个 BST，虽然在平衡状态下 BST 的平均性能能达到 $O(\log n)$ 但在极端情况下(比如升/降序插入)， BST 的性能会降到 $O(n)$ ，这就和线性表没有区别了。
我们希望防止细长树的情况出现，这就需要树自身能够“自平衡”。自平衡的核心在于通过控制树的最大深度来保证极端情况的搜索性能。在实现上，自平衡有着多种实现策略，包括 AVL 的强制平衡、2 – 3 树的平衡搜索，以及这次 lab 中需要实现的 RBTree 。
2 – 3 Tree
2 – 3 树是一种平衡搜索树，每个节点含 1~2 个键以及 2~3 个节点。 它通过多路节点的分裂机制，保持所有叶子节点在树的同一层，从而保证树的高度平衡和极端性能。
为什么提及 2 – 3 Tree ？ 因为红黑树的实现参考或者说蕴含了一定的 2 – 3 树思想。2 – 3 树的思想在于允许节点储存多个键和子节点，并通过再插入时向上分裂(fixUp) 来保持树的平衡
想到了 B+ 树，但似乎更简单
核心机制 – FixUp
对于新插入的节点，在插入前我们做如下判断：
- 如果叶子节点当前 2 – Node，则直接插入使其成为 3 – Node
- 如果叶子节点已经 3 – Node，则对节点做分裂操作：
- 取中间键为父节点，原节点剩余两个节点分裂为父节点的两个子 2 – Node
- 若提级后父节点为 3 – Node，则重复上述操作
通过分裂操作，2 – 3 树能够很好的保持平衡，而与 AVL 树相比，FixUp 的操作更加简单直观
呃..不过实现更麻烦
Left Leaning Red Black Tree
LLRBT(左倾红黑树) 由Robert Sedgewick 提出，其实是 红黑树 的一个简化(指实现上)实现。标准红黑树的实现复杂、情况繁多。LLRBT 通过类似于 2 – 3 Tree 的 FixUp 的左倾操作，将红黑树的多种操作后的调整情况做出了简化，同时保证了相同的性能开销 $O(\log n)$
操作步骤
LLRBT 的核心方法包括三个，分别是
- 左旋 (Rotate Left):当前节点的右孩子上浮至父节点，原父节点下沉为新的父节点的左孩子；
- 右旋 (Rotate Right)：当前节点的左孩子上浮至父节点，原父节点下沉为新的父节点的右孩子
- 颜色翻转 (Color Filp)：反转当前节点及其首个左右孩子的颜色标记
依赖于上述方法，LLRBT 的详细机制为：
- 修复左倾：
- 右子节点永远为黑，出现红则执行左旋操作
- 不会出现两个连续的红色左子节点，如果出现，执行右旋
- 如果一个节点的两个子节点均为红色，执行颜色翻转
- 按上述操作递归向上修复
实现
Lab 的框架在这给出了基本的方法签名。而且代码 Comment 及其详细
以至于不看讲义对着 Commit 都能实现…
颜色翻转：
void flipColors(RBTreeNode<T> node) {
// TODO: YOUR CODE HERE
RBTreeNode<T> cur = node;
if(cur != null) {
cur.isBlack = false;
// Recursion for child
if(cur.left != null) cur.left.isBlack = true;
if(cur.right != null) cur.right.isBlack = true;
}
}
右旋：
RBTreeNode<T> rotateRight(RBTreeNode<T> node) {
// TODO: YOUR CODE HERE
RBTreeNode<T> temp = node;
node = node.left;
RBTreeNode<T> prev = node.right;
node.right = temp;
temp.left = prev;
node.isBlack = temp.isBlack;
temp.isBlack = false;
return node;
}
左旋：
RBTreeNode<T> rotateLeft(RBTreeNode<T> node) {
// TODO: YOUR CODE HERE
RBTreeNode<T> temp = node;
node = node.right;
RBTreeNode<T> prev = node.left;
node.left = temp;
temp.right = prev;
node.isBlack = temp.isBlack;
temp.isBlack = false;
return node;
}
以及 Insert：
private RBTreeNode<T> insert(RBTreeNode<T> node, T item) {
// TODO: Insert (return) new red leaf node.
if(node == null) {
return new RBTreeNode<>(false, item);
}
// TODO: Handle normal binary search tree insertion.
int cmp = node.item.compareTo(item);
if(cmp < 0) {
node.right = insert(node.right, item);
} else if(cmp > 0) {
node.left = insert(node.left, item);
} else {
return node;
}
// TODO: Rotate left operation
if(isRed(node.right) && !isRed(node.left)) {
node = rotateLeft(node);
}
// TODO: Rotate right operation
if(isRed(node.left) && isRed(node.left.left)) {
node = rotateRight(node);
}
// TODO: Color flip
if(isRed(node.right) && isRed(node.left)) {
flipColors(node);
}
return node;
}
以上
发表回复