------------ 本文來(lái)自 阿P官方博客
------------ 在線測(cè)試紅黑樹：紅黑樹在線測(cè)試
一囱挑、紅黑樹
自平衡二叉查找樹(Binary Search Tree)
二叉查找樹：
基于二叉樹
左子樹小于根醉顽，右子樹大于根
缺點(diǎn)：如果選錯(cuò)根節(jié)點(diǎn)，整個(gè)樹就不再平衡
特點(diǎn)
所有節(jié)點(diǎn)非紅即黑
根節(jié)點(diǎn)一定是黑色
紅節(jié)點(diǎn)的子節(jié)點(diǎn)一定是黑色
最低層的葉子節(jié)點(diǎn)一定是黑色
從根節(jié)點(diǎn)到任意葉子節(jié)點(diǎn)經(jīng)歷過(guò)的黑色節(jié)點(diǎn)一定相同
新增的節(jié)點(diǎn)顏色一定是紅色節(jié)點(diǎn)
紅黑樹時(shí)間復(fù)雜度：O(logN) 與二分查找法一致
第一次查找數(shù)量 n/2
第二次查找數(shù)量 n/2/2
第三次查找數(shù)量 n/2/2/2
…...
第m次查找數(shù)量 n/(2^m)
由此我們可以得知時(shí)間復(fù)雜度=logN
二平挑、紅黑樹修正（遵循以下步驟進(jìn)行修正）
當(dāng)前節(jié)點(diǎn)為紅游添，父節(jié)點(diǎn)為紅，并且叔父節(jié)點(diǎn)為紅或?yàn)榭? 父節(jié)點(diǎn)通熄、叔父節(jié)點(diǎn)涂黑唆涝，祖父節(jié)點(diǎn)涂紅。對(duì)祖父節(jié)點(diǎn)繼續(xù)操作
當(dāng)前節(jié)點(diǎn)為紅且是右子葉唇辨，父節(jié)點(diǎn)為紅廊酣，并且叔父節(jié)點(diǎn)為黑
以當(dāng)前節(jié)點(diǎn)為軸，進(jìn)行左旋
當(dāng)前節(jié)點(diǎn)為紅且是左子葉赏枚，父節(jié)點(diǎn)為紅亡驰，并且叔父節(jié)點(diǎn)為黑
父節(jié)點(diǎn)涂黑，祖父節(jié)點(diǎn)涂紅嗡贺，以父節(jié)點(diǎn)為軸隐解，進(jìn)行右旋
三、紅黑樹JAVA實(shí)現(xiàn)類
package RBTree;
/**
* 紅黑樹
*
*/
public class RBTreeDemo<T extends Comparable<T>> {
Node root;//根節(jié)點(diǎn)
Node min;//最左節(jié)點(diǎn)
Node max;//最右節(jié)點(diǎn)
Boolean RED = true;
Boolean BLACK = false;
/**
* 新增
* @param val
*/
public void add(T val)
{
if (this.root == null) {
//根節(jié)點(diǎn)為黑色
this.root = new Node<T>(val, this.BLACK, null, null, null);
return;
}
Node node = this.root;
//當(dāng)前節(jié)點(diǎn)
Node current = new Node<T>(val, this.RED, null, null, null);
//遍歷樹诫睬，進(jìn)行插入
while (true) {
if (val.compareTo((T) node.val) > 0) {//放右子節(jié)點(diǎn)
if (node.right == null) {
node.right = current;
current.parent = node;
break;
}
node=node.right;
} else {//放左子節(jié)點(diǎn)
if (node.left == null) {
node.left = current;
current.parent = node;
break;
}
node=node.left;
}
}
//插入完進(jìn)行自平衡
fixUp(current);
}
/**
* 自平衡
*/
public void fixUp(Node node)
{
//當(dāng)前節(jié)點(diǎn)沒(méi)父節(jié)點(diǎn)煞茫，則涂黑
if (node.parent == null) {
node.color = this.BLACK;
this.root = node;
return;
}
//當(dāng)前節(jié)點(diǎn)沒(méi)有祖父節(jié)點(diǎn)
if (node.parent.parent == null) {
return;
}
//叔父節(jié)點(diǎn) 可以為空
Node uncleNode = this.getUncleNode(node);
//當(dāng)前節(jié)點(diǎn)為紅，且父節(jié)點(diǎn)為紅
if (node.color == this.RED && node.parent.color == this.RED) {
//叔父節(jié)點(diǎn)為空或者為紅摄凡，就進(jìn)行涂色
if (uncleNode == null || uncleNode.color == this.RED) {
node.parent.color = this.BLACK;
if (uncleNode != null) {
uncleNode.color=this.BLACK;
}
node.parent.parent.color = this.RED;
this.fixUp(node.parent.parent);
} else if (uncleNode.color == this.BLACK) {
//自己是左子葉
if (node.parent.left.equals(node)) {
this.right(node);
this.fixUp(node.parent);//右旋后续徽，修改當(dāng)前節(jié)點(diǎn)顏色
} else {//自己是右子葉
this.left(node);
this.fixUp(node.left);//曾經(jīng)的父節(jié)點(diǎn)
}
}
}
}
/**
* 叔父節(jié)點(diǎn)，可以為空
* @param node
* @return
*/
private Node getUncleNode(Node node) {
Node uncleNode= node.parent.parent.left;
if (uncleNode == null || node.parent.equals(uncleNode)) {
uncleNode = node.parent.parent.right;
}
return uncleNode;
}
/**
* 當(dāng)前結(jié)點(diǎn)為紅亲澡，且處于右子葉上钦扭。父節(jié)點(diǎn)為紅，叔父節(jié)點(diǎn)為黑或空時(shí)床绪。以當(dāng)前節(jié)點(diǎn)為軸進(jìn)行左旋
* 當(dāng)前節(jié)點(diǎn)的祖父節(jié)點(diǎn)客情，變成自己的父節(jié)點(diǎn)
* 當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)其弊，變成自己的左節(jié)點(diǎn)
* 當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)，變成當(dāng)前右節(jié)點(diǎn)的右節(jié)點(diǎn)
*/
private void left(Node node) {
Node parent = node.parent;
Node left = node.left;
Node pParent = node.parent.parent;
//祖父節(jié)點(diǎn)
pParent.left = node;
//父節(jié)點(diǎn)
parent.parent = node;
parent.right = left;
//左節(jié)點(diǎn)
left.parent = parent;
//當(dāng)前節(jié)點(diǎn)
node.parent = pParent;
node.left = parent;
}
/**
* 當(dāng)前結(jié)點(diǎn)為紅膀斋，且處于左子葉上梭伐。父節(jié)點(diǎn)為紅，叔父節(jié)點(diǎn)為黑時(shí)仰担。以父節(jié)點(diǎn)為軸進(jìn)行右旋
*/
private void right(Node node) {
Node parent = node.parent;
Node right = parent.right;
Node pParent = node.parent.parent;
Node ppParent = node.parent.parent.parent;
//涂色
pParent.color = this.RED;
parent.color = this.BLACK;
if (ppParent != null) {
//祖祖父節(jié)點(diǎn)
if (ppParent.right.equals(pParent)) {
ppParent.right = parent;
} else {
ppParent.left = parent;
}
}
//祖父節(jié)點(diǎn)
pParent.left = right;
pParent.parent=parent;
//父節(jié)點(diǎn)
parent.right = pParent;
parent.parent = ppParent;
//右子節(jié)點(diǎn)
right.parent = pParent;
}
/**
* 前序遍歷 從根開始遍歷
*/
private String preOrder(Node node) {
if (node == null) {
return null;//如果左側(cè)樹遍歷完成糊识，返回null
}
String strLeft = this.preOrder(node.left);
if (strLeft == null) {
strLeft="";
}
String strRight = this.preOrder(node.right);
if (strRight == null) {
strRight="";
}
return strLeft + node.toString() + strRight;
}
@Override
public String toString() {
//前序遍歷
return preOrder(this.root);
}
/**
* 結(jié)點(diǎn)類
*/
private class Node<T>{
public T val;
public Boolean color;//紅為true
public Node left;
public Node right;
public Node parent;
public Node(T val, Boolean color, Node left, Node right, Node parent) {
super();
this.val = val;
this.color = color;
this.left = left;
this.right = right;
this.parent = parent;
}
@Override
public String toString() {
String left = "-";
String right = "-";
if (this.left != null) {
left = this.left.val.toString();
}
if (this.right != null) {
right = this.right.val.toString();
}
return "[" + left + ", "+this.val.toString() + ", " + right +", "+ getColorName(this.color) + "]";
}
private String getColorName(Boolean color) {
return color == true? "紅" : "黑";
}
@Override
public boolean equals(Object obj) {
Node obj1 = (Node)obj;
return obj1.val == this.val;
}
}
}
