唉 規整規整 進階目錄
1. 紅黑樹 -- 特性
(1) 每個節點或者是黑色，或者是紅色。
(2) 根節點是黑色。
(3) 每個葉子節點是黑色。 [注意：這裡葉子節點，是指為空的葉子節點！]
(4) 如果一個節點是紅色的，則它的子節點必須是黑色的。
(5) 從一個節點到該節點的子孫節點的所有路徑上包含相同數目的黑節點。
2. Java -- 實作
package lime.xiaoniu;
/**
* @Author : LimeOracle
* @Descri :
* @Remark :
* 紅黑樹的特性:
（1）每個節點或者是黑色，或者是紅色。
（2）根節點是黑色。
（3）每個葉子節點（NIL）是黑色。 [注意：這裡葉子節點，是指為空(NIL或NULL)的葉子節點！]
（4）如果一個節點是紅色的，則它的子節點必須是黑色的。
（5）從一個節點到該節點的子孫節點的所有路徑上包含相同數目的黑節點。
*/
/**
* @Author : LimeOracle
* @Descri :
* @Remark :
* 注意：
(01) 特性(3)中的葉子節點，是隻為空(NIL或null)的節點。
(02) 特性(5)，確定沒有一條路徑會比其他路徑長出倆倍。因而，紅黑樹是相對是接近平衡的二叉樹。
*/
/**
* @Author : LimeOracle
* @Descri :
* @Remark :
* 1.将紅黑樹當作一顆二叉查找樹，将節點插入；
* 2.将節點着色為紅色；
* 3.通過旋轉和重新着色等方法來修正該樹，使之重新成為一顆紅黑樹。
第二步中，将插入節點着色為"紅色"之後，不會違背"特性(5)"。那它到底會違背哪些特性呢？
對于"特性(1)"，顯然不會違背了。因為我們已經将它塗成紅色了。
對于"特性(2)"，顯然也不會違背。在第一步中，我們是将紅黑樹當作二叉查找樹，然後執行的插入操作。而根據二叉查找數的特點，插入操作不會改變根節點。是以，根節點仍然是黑色。
對于"特性(3)"，顯然不會違背了。這裡的葉子節點是指的空葉子節點，插入非空節點并不會對它們造成影響。
對于"特性(4)"，是有可能違背的！
那接下來，想辦法使之"滿足特性(4)"，就可以将樹重新構造成紅黑樹了。
*/
/**
* @Author : LimeOracle
* @Descri :
* @Remark :
* 根據被插入節點的父節點的情況，可以将"當節點z被着色為紅色節點，并插入二叉樹"劃分為三種情況來處理。
① 情況說明：被插入的節點是根節點。
處理方法：直接把此節點塗為黑色。
② 情況說明：被插入的節點的父節點是黑色。
處理方法：什麼也不需要做。節點被插入後，仍然是紅黑樹。
③ 情況說明：被插入的節點的父節點是紅色。
處理方法：那麼，該情況與紅黑樹的“特性(4)”相沖突。
這種情況下，被插入節點是一定存在非空祖父節點的；
進一步的講，被插入節點也一定存在叔叔節點(即使叔叔節點為空，我們也視之為存在，空節點本身就是黑色節點)。
了解這點之後，我們依據"叔叔節點的情況"，将這種情況進一步劃分為3種情況(Case)。
*/
import com.sun.org.apache.regexp.internal.RE;
import static lime.xiaoniu.RBTree.Color.BLACK;
import static lime.xiaoniu.RBTree.Color.RED;
/**
* @Author : LimeOracle
* @Descri : 依據"叔叔節點的情況"，将這種情況進一步劃分為3種情況(Case)。
* @Remark :
* Case 1
* B B
* / \ / \
* R R 或 R R
* / \
* CR CR
* 目前節點的父節點是紅色，且目前節點的祖父節點的另一個子節點（叔叔節點）也是紅色。
* (01) 将“父節點”設為黑色。
(02) 将“叔叔節點”設為黑色。
(03) 将“祖父節點”設為“紅色”。
(04) 将“祖父節點”設為“目前節點”(紅色節點)；即，之後繼續對“目前節點”進行操作。
* Case 2
* B B
* / \ / \
* R B 或 B R
* \ /
* CR CR
* 目前節點的父節點是紅色，叔叔節點是黑色，且目前節點是其父節點的右孩子
* (01) 将“父節點”作為“新的目前節點”。
(02) 以“新的目前節點”為支點進行左旋。
* Case 3
* B B
* / \ / \
* R B 或 B R
* / \
* CR CR
* 目前節點的父節點是紅色，叔叔節點是黑色，且目前節點是其父節點的左孩子
* (01) 将“父節點”設為“黑色”。
(02) 将“祖父節點”設為“紅色”。
(03) 以“祖父節點”為支點進行右旋。
*
* 上面三種情況(Case)處理問題的核心思路都是：将紅色的節點移到根節點；然後，将根節點設為黑色。
*/
public class RBTree<T extends Comparable<T>> {
private RBTNode<T> mRoot;
enum Color{RED,BLACK}
public class RBTNode<T extends Comparable<T>>{
Color color;//顔色
T key; //關鍵字（鍵值）
RBTNode<T> left;//左孩子
RBTNode<T> right;//右孩子
RBTNode<T> parent;//父節點
public RBTNode(T key,Color color,RBTNode<T> parent,RBTNode<T> left,RBTNode<T> right){
this.key = key;
this.color = color;
this.parent = parent;
this.left = left;
this.right = right;
}
@Override
public String toString() {
return "RBTNode{" +
"color=" + color +
", key=" + key +
", left=" + left +
", right=" + right +
", parent=" + parent +
'}';
}
}
private void leftRotate(RBTNode<T> x){
RBTNode<T> y = x.right;
x.right = y.left;
if(null != y.left){
y.left.parent = x;
}
y.parent = x.parent;
if(null == x.parent){
this.mRoot = y;
}else{
if(x.parent.left == x){
x.parent.left = y;
}else {
x.parent.right = y;
}
}
y.left = x;
x.parent = y;
}
private void rightRotate(RBTNode x){
RBTNode y = x.left;
x.left = y.right;
if(null != y.right){
y.right.parent = x;
}
y.parent = x.parent;
if(null == x.parent){
this.mRoot = y;
}else{
if(x.parent.left == x){
x.parent.left = y;
}else{
x.parent.right = y;
}
}
y.right = x;
x.parent = y;
}
private void insert(RBTNode<T> node){
int cmp;
RBTNode<T> y = null;
RBTNode<T> x = this.mRoot;
// 1. 将紅黑樹當作一顆二叉查找樹，将節點添加到二叉查找樹中。
while (x != null){
y = x;
cmp = node.key.compareTo(x.key);
if(cmp < 0){
x = x.left;
}else{
x = x.right;
}
}
node.parent = y;
if(null != y){
cmp = node.key.compareTo(y.key);
if(cmp < 0){
y.left = node;
}else{
y.right = node;
}
}else{
this.mRoot = node;
}
// 2. 設定節點的顔色為紅色
node.color = RED;
// 3. 将它重新修正為一顆二叉查找樹
insertFixUp(node);
}
public void insert(T key){
RBTNode<T> node = new RBTNode<T>(key,BLACK,null,null,null);
if(null != node){
insert(node);
}
}
/**
* @Author : LimeOracle
* @Descri : 紅黑樹插入修正函數
* @Remark :
* 在向紅黑樹中插入節點之後(失去平衡)，再調用該函數；
* 目的是将它重新塑造成一顆紅黑樹。
*/
private void insertFixUp(RBTNode<T> node){
RBTNode<T> parent,gparent;
// 若“父節點存在，并且父節點的顔色是紅色”
while ((parent = node.parent) != null && RED == parent.color){
gparent = parent.parent;
//若“父節點”是“祖父節點的左孩子”
if(parent == gparent.left){
// Case 1條件：叔叔節點是紅色
// (01) 将“父節點”設為黑色。
// (02) 将“叔叔節點”設為黑色。
// (03) 将“祖父節點”設為“紅色”。
// (04) 将“祖父節點”設為“目前節點”(紅色節點)；即，之後繼續對“目前節點”進行操作。
RBTNode<T> uncle = gparent.right;
if(uncle != null && RED == uncle.color){
parent.color = BLACK;
uncle.color = BLACK;
gparent.color = RED;
node = gparent;
continue;
}
// Case 2條件：叔叔是黑色，且目前節點是右孩子
// (01) 将“父節點”作為“新的目前節點”。
// (02) 以“新的目前節點”為支點進行左旋。
if(parent.right == node){
RBTNode<T> tmp;
leftRotate(parent);
tmp = parent;parent = node;node = tmp;
}
// Case 3條件：叔叔是黑色，且目前節點是左孩子。
if(parent.left == node){
// (01) 将“父節點”設為“黑色”。
// (02) 将“祖父節點”設為“紅色”。
// (03) 以“祖父節點”為支點進行右旋。
parent.color = BLACK;
gparent.color = RED;
rightRotate(gparent);
}
}else{
//若“z的父節點”是“z的祖父節點的右孩子”
// Case 1條件：叔叔節點是紅色
RBTNode<T> uncle = gparent.left;
if(uncle.color == RED){
parent.color = BLACK;
uncle.color = BLACK;
gparent.color = RED;
node = gparent;
continue;
}
// Case 2條件：叔叔是黑色，且目前節點是左孩子
if(parent.left == node){
RBTNode<T> tmp;
rightRotate(parent);
tmp = parent;parent = node;node = parent;
}
// Case 3條件：叔叔是黑色，且目前節點是右孩子。
if(parent.right == node){
parent.color = BLACK;
gparent.color = RED;
leftRotate(gparent);
}
}
}
this.mRoot.color = BLACK;
}
public void inOrder(){
inOrder(this.mRoot);
}
private void inOrder(RBTNode<T> x){
if(null == x){
return;
}
inOrder(x.left);
System.out.print(x.key + " ");
inOrder(x.right);
}
public static void main(String[] args){
RBTree<Integer> root = new RBTree<Integer>();
root.insert(80);
root.insert(40);
root.insert(120);
root.insert(20);
root.insert(60);
root.insert(100);
root.insert(140);
root.insert(10);
root.insert(50);
root.insert(90);
root.insert(10);
root.insert(30);
root.inOrder();
}
} 3. 鳴謝：
![oracle中的start with connect by用法[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)