??B-tree/2-3 tree/2-3-4 tree：在BST的基础上对它的worst case进行了优化，B-tree更加平衡。
满足条件
??所有叶子节点到root节点的距离都相同；
??一个具有k个item的非叶子节点，它一定有k+1个child。
??（2-3 tree：最多可以有3个child，2-3-4 tree：最多可以有4个child）
??以2-3 tree为例展示insert操作的过程，2-3-4 tree类似。
??红黑树（Red Black Tree ）：对BST进行旋转可以平衡它，进而获得更好的效果。（B-tree算法很好，但实现起来很复杂）；
??下面以左倾红黑二叉树LLRB（和一个2-3 tree 对应）为例进行实现。
满足条件
??所有leaf节点到root节点之间都具有相同数量的黑色edge；
??同一个节点不可能同时具有两条红色edge；
??LLRB的红色edge只能在左边（左倾）；
??如果它所对应2-3 tree 的高度为H，则LLRB的高度最高为2H + 1，所以worst case的时间复杂度仍为O(logN)。
红黑
??为了和2-3 tree的结构对应，使用红色和黑色的边来连接各个节点：
????黑色edge是正常BST的edge；
????红色edge连接的两个节点相当于2-3 tree中一个节点的两个item。
??这样就可以使用BST来实现2-3 tree的结构了。
旋转
??在维护一个LLRB的过程中涉及到一定的旋转操作，以左旋为例，介绍旋转的基本思路（右旋是对称操作）。
??rotateLeft(A)：
????将A和其right child B合并；
??????如果B没有left child C，continue；
??????如果B有left child C，将C变为A的right child；
????A变为B的left child。
insert实现
??在向LLRB插入新节点的过程中，为了维护其特性，需要遵守以下规则：
????1.每一个新插入的节点都使用红色edge连接；
????2.如果节点（root节点特殊）有两个红色edge，进行flip操作，见图例；
??????flip操作也有可能违反rule 3，需要check一下
????3.如果节点有右倾的红色edge，rotateLeft；
????4.如果节点有连续两个红色edge，rotateRight，进入rule 2；
java代码
??以如下LLRBBST为例测试上述insert操作的正确性
??LLRBBST.java
public class LLRBBST {
/* 左倾红黑二叉树的部分实现
*/
private Node root;
private class Node {
/* node设计
* 除了常规的左右child外，还应该有parent，以及标识此节点和parent连接的edge是红边/黑边
* root默认为黑边
*/
private int value;
private Node leftNode;
private Node rightNode;
private Node parentNode;
private boolean edgeColor; // true:红边 false:黑边
Node(int v, Node parent, boolean color) {
this.value = v;
this.leftNode = null;
this.rightNode = null;
this.parentNode = parent;
this.edgeColor = color;
}
}
LLRBBST(int v) {
this.root = new Node(v, null, false);
}
/**
* 1.每一个新插入的节点都使用红色edge连接；
* 2.如果节点（root节点特殊）有两个红色edge，进行flip操作，见图例；
* flip操作也有可能违反rule 3，需要check一下
* 3.如果节点有右倾的红色edge，rotateLeft；
* 4.如果节点有连续两个红色edge，rotateRight，进入rule 2；
*/
public void insert(int v) {
Node parent = findParentNode(root, v);
Node curNode = new Node(v, parent, true);
if (parent.value < v) {
parent.rightNode = curNode;
} else {
parent.leftNode = curNode;
}
checkTwoRedEdge(parent);
Node grandParent = parent.parentNode;
grandParent = checkRightEdge(grandParent);
checkConseEdge(grandParent);
}
/**
* 3.如果节点有右倾的红色edge，rotateLeft
*/
private Node checkRightEdge(Node curNode) {
if (curNode == null) {
return curNode;
} else if (!checkRight(curNode)) {
if (curNode.rightNode.edgeColor) {
curNode = rotateLeft(curNode);
if (checkRoot(curNode)) {
root = curNode;
}
}
}
return curNode;
}
/**
* 对当前节点进行左旋操作
* 当前节点的right child为当前节点right child的left child
* 当前节点的right child的left child变为为当前节点
* 两个节点的edgecolor互换
*/
private Node rotateLeft(Node curNode) {
Node parent = curNode.parentNode;
if (!checkRight(curNode)) {
Node right = curNode.rightNode;
curNode.rightNode = right.leftNode;
if (right.leftNode != null) {
right.leftNode.parentNode = curNode;
}
right.leftNode = curNode;
curNode.parentNode = right;
curNode = right;
boolean temp = curNode.edgeColor;
curNode.edgeColor = curNode.leftNode.edgeColor;
curNode.leftNode.edgeColor = temp;
}
curNode.parentNode = parent;
return curNode;
}
/**
* 对当前节点进行右旋操作
* 当前节点的left child的right child变为当前节点的left child
*
*/
private Node rotateRight(Node curNode) {
Node parent = curNode.parentNode;
if (!checkLeaf(curNode)) {
Node left = curNode.leftNode;
curNode.leftNode = left.rightNode;
if (left.rightNode != null) {
left.rightNode.parentNode = curNode;
}
left.rightNode = curNode;
curNode.parentNode = left;
curNode = left;
boolean temp = curNode.edgeColor;
curNode.edgeColor = curNode.rightNode.edgeColor;
curNode.rightNode.edgeColor = temp;
}
curNode.parentNode = parent;
return curNode;
}
/**
* 2.如果节点（root节点特殊）有两个红色edge，进行flip操作，见图例；
* flip操作也有可能违反rule 3，需要check一下
*/
private void checkTwoRedEdge(Node curNode) {
if (curNode == null) {
return;
}
if (!checkLeft(curNode) && !checkRight(curNode)) {
if (curNode.leftNode.edgeColor && curNode.rightNode.edgeColor) {
flip(curNode);
if (curNode.parentNode != null) {
Node grandNode = curNode.parentNode.parentNode;
checkConseEdge(grandNode);
}
}
}
}
/**
* 对当前节点进行flip操作；
* 将两个child节点的edge改为黑色；
* 将当前节点的edge改为红色；
*/
private void flip(Node curNode) {
curNode.leftNode.edgeColor = false;
curNode.rightNode.edgeColor = false;
if (checkRoot(curNode)) {
curNode.edgeColor = false;
} else {
curNode.edgeColor = true;
}
}
/**
* 4.如果节点有连续两个红色edge，rotateRight，进入rule 2；
*/
private void checkConseEdge(Node curNode) {
if (curNode == null) {
return;
}
if (!checkLeaf(curNode)) {
Node leftChild = curNode.leftNode;
if (leftChild.edgeColor) {
if (!checkLeaf(leftChild)) {
if (leftChild.leftNode.edgeColor) {
curNode = rotateRight(curNode);
checkTwoRedEdge(curNode);
if (checkRoot(curNode)) {
root = curNode;
}
}
}
}
}
}
/**
* 找到当前插入节点的parent节点并return
*/
private Node findParentNode(Node curNode, int v) {
if (checkLeaf(curNode)) {
return curNode;
} else if (curNode.value < v) {
if (checkRight(curNode)) {
return curNode;
} else {
return findParentNode(curNode.rightNode, v);
}
} else {
if (checkLeft(curNode)) {
return curNode;
} else {
return findParentNode(curNode.leftNode, v);
}
}
}
/**
* check当前节点是否为叶子节点
*/
private boolean checkLeaf(Node curNode) {
return curNode.leftNode == null &&
curNode.rightNode == null;
}
/**
* check当前节点的左子树是否为空
*/
private boolean checkLeft(Node curNode) {
return curNode.leftNode == null;
}
/**
* check当前节点的右子树是否为空
*/
private boolean checkRight(Node curNode) {
return curNode.rightNode == null;
}
/**
* check当前节点是否为root节点
*/
private boolean checkRoot(Node curNode) {
return curNode.parentNode == null;
}
}
??Test.java
public class Test {
/**
* 对LLRBBST进行测试
*/
public static void main(String[] args) {
LLRBBST t = new LLRBBST(6);
t.insert(8);
t.insert(10);
t.insert(9);
t.insert(15);
t.insert(3);
t.insert(7);
}
}
