樹結(jié)構(gòu)
樹的高度篙骡，深度柱锹，層
二叉樹
二叉樹每個節(jié)點只能有兩個叉张抄。
滿二叉樹
完全二叉樹
除最后一層革半，其它層節(jié)點個數(shù)都要達到最大碑定，最后一層葉子節(jié)點靠左排列（如果只有一個叉那就靠左，即優(yōu)先靠左排列）
二叉樹的遍歷
- 前序遍歷是指又官，對于樹中的任意節(jié)點來說延刘，先打印這個節(jié)點，然后再打印它的左子樹六敬，最后打印它的右子樹碘赖。
- 中序遍歷是指，對于樹中的任意節(jié)點來說，先打印它的左子樹普泡，然后再打印它本身播掷，最后打印它的右子樹。
- 后序遍歷是指撼班，對于樹中的任意節(jié)點來說歧匈，先打印它的左子樹，然后再打印它的右子樹砰嘁，最后打印這個節(jié)點本身件炉。
遍歷口訣
前序
先根節(jié)點 左順 右順
中序
左子樹：左逆 根節(jié)點 右順 最終到父節(jié)點 右子樹：左逆 根節(jié)點 右順
后續(xù)
左逆 右逆 根節(jié)點
code
遞推公式
前序遍歷的遞推公式：
preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)
中序遍歷的遞推公式：
inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)
后序遍歷的遞推公式：
postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r
BinarySortTreeNode
package com.pl.arithmetic.binarySortTree;
/**
* <p>
*
* @Description: TODO
* </p>
* @ClassName BinarySortTreeNode
* @Author pl
* @Date 2020/10/13
* @Version V1.0.0
*/
public class BinarySortTreeNode {
private int value;
private String name;
BinarySortTreeNode leftNode;
BinarySortTreeNode rightNode;
/**
*前序排序
*
* @param
* @return void
* @exception
* @author silenter
* @date 2020/10/13 7:04
*/
public void preOrder(){
System.out.println(this.value);
if (this.leftNode!=null){
this.leftNode.preOrder();
}
if (this.rightNode!=null){
this.rightNode.preOrder();
}
}
/**
*中序排序
*
* @param
* @return void
* @exception
* @author silenter
* @date 2020/10/13 7:04
*/
public void infixOrder(){
if (this.leftNode!=null){
this.leftNode.infixOrder();
}
System.out.println(this.value);
if (this.rightNode!=null){
this.rightNode.infixOrder();
}
}
/**
*后續(xù)排序
*
* @param
* @return void
* @exception
* @author silenter
* @date 2020/10/13 7:05
*/
public void postOrder(){
if (this.leftNode!=null){
this.leftNode.postOrder();
}
if (this.rightNode!=null){
this.rightNode.postOrder();
}
System.out.println(this.value);
}
}
二叉樹的存儲
二叉樹的存儲可以有兩種方式存儲
- 數(shù)組（順序二叉樹）
- 鏈表
順序二叉樹（BinarySortTree）
二叉樹的順序存儲是將二叉樹的所有結(jié)點，按照一定的次序矮湘，存儲到一片連續(xù)的存儲單元中（數(shù)組）斟冕，一般針對完全二叉樹。
code
package com.pl.arithmetic.binaryTree.arrayBinaryTree;
/**
* <p>
*
* @Description: 數(shù)組二叉樹缅阳，順序二叉樹
* </p>
* @ClassName ArrayBinaryTree
* @Author pl
* @Date 2020/11/6
* @Version V1.0.0
*/
public class BinarySortTree {
private int arr[];
public BinarySortTree(int[] arr) {
this.arr = arr;
}
public void preOrder() {
preOrder(0);
}
/**
* 前序遍歷
*
* @param index 數(shù)組索引磕蛇，角標
* @return void
* @throws
* @author silenter
* @date 2020/11/6 21:57
*/
public void preOrder(int index) {
//@1 先判斷是否數(shù)組越界 和數(shù)組是否為空
if (index > arr.length) {
System.out.println("無此節(jié)點");
return;
}
if (arr == null && arr.length == 0) {
System.out.println("數(shù)組為空");
return;
}
System.out.println(arr[index]);
//數(shù)組角標和數(shù)組大小永遠是小于關(guān)系
//@2 左子樹
if (index * 2 + 1 < arr.length) {
preOrder(index * 2 + 1);
}
//@3 右子樹
if (index * 2 + 2 < arr.length) {
preOrder(index * 2 + 2);
}
}
}
BinarySortTreeDemo
public class BinarySortTreeDemo {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7};
//創(chuàng)建一個 ArrBinaryTree
ArrayBinaryTree arrBinaryTree = new ArrayBinaryTree(arr);
arrBinaryTree.preOrder(); // 1,2,4,5,3,6,7
}
}
輸出
二叉查找樹
二叉查找樹要求，在樹中的任意一個節(jié)點十办，其左子樹中的每個節(jié)點的值秀撇，都要小于這個節(jié)點的值，而右子樹節(jié)點的值都大于這個節(jié)點的值
二叉查找樹的查找橘洞，新增捌袜，刪除
package com.pl.arithmetic.binaryTree.binarySearchTree;
/**
* <p>
*
* @Description: TODO
* </p>
* @ClassName BinarySortTreeDemo
* @Author pl
* @Date 2020/11/14
* @Version V1.0.0
*/
public class BinarySortTreeDemo {
private Node root;
public BinarySortTreeDemo(Node root) {
this.root = root;
}
public BinarySortTreeDemo() {
}
//添加結(jié)點的方法
public void add(Node node) {
if (root == null) {
root = node;//如果root為空則直接讓root指向node
} else {
root.addNode(node);
}
}
//中序遍歷
public void infixOrder() {
if (root != null) {
root.infixOrder();
} else {
System.out.println("二叉排序樹為空，不能遍歷");
}
}
//查找要刪除的結(jié)點
public Node search(int value) {
Node temp = null;
if (root == null) {
throw new RuntimeException("根節(jié)點為空");
} else {
temp = root.searchNode(value);
if (temp == null) {
throw new RuntimeException("未查詢到指定節(jié)點");
}
return temp;
}
}
/**
* 查詢某一個節(jié)點的父節(jié)點炸枣，只有該節(jié)點為父節(jié)點時，才返回null弄唧，如果找不到該節(jié)點的父節(jié)點适肠，則直接拋出異常
*
* @param value
* @return com.pl.arithmetic.binaryTree.binarySearchTree.Node
* @throws
* @author silenter
* @date 2020/11/14 11:23
*/
public Node searchParent(int value) {
Node temp = null;
if (root == null) {
throw new RuntimeException("根節(jié)點為空");
} else if (value == root.value) {
System.out.println("當該節(jié)點為根節(jié)點時，返回null,且只有這一種情況返回null");
return null;
} else {
temp = root.searchParentNode(value);
if (temp == null) {
throw new RuntimeException("該節(jié)點父節(jié)點為空");
}
return temp;
}
}
/**
* 查找右子樹中最小的節(jié)點
*
* @param node
* @return com.pl.arithmetic.binaryTree.binarySearchTree.Node
* @throws
* @author silenter
* @date 2020/11/14 10:53
*/
public Node searchRightMixNode(Node node) {
return this.root.searchRightMixNode(node);
}
/**
* 刪除節(jié)點
* 有三種情況：
* 1.要刪除節(jié)點為葉子節(jié)點
* 2.要刪除節(jié)點有一個子節(jié)點
* 3.要刪除節(jié)點有兩個節(jié)點
*
* @param value
* @return void
* @throws
* @author silenter
* @date 2020/11/14 10:26
*/
public void delNode(int value) {
//@1先查詢出要刪除節(jié)點是以上哪種情況的節(jié)點
Node matchNode = this.search(value);
//@2 若該節(jié)點不為空候引，查詢該節(jié)點的父節(jié)點
Node parentNode = this.searchParent(value);
//@3 對該節(jié)點進行判斷為三種情況中的哪種
//@3.1 要刪除節(jié)點為葉子節(jié)點
if (matchNode.left == null && matchNode.right == null) {
if (parentNode.left.value == matchNode.value) {
parentNode.left = null;
System.out.println("待刪除節(jié)點無子節(jié)點侯养，為左子樹節(jié)點，已刪除");
return;
}
if (parentNode.right.value == matchNode.value) {
parentNode.right = null;
System.out.println("待刪除節(jié)點無子節(jié)點澄干，為右子樹節(jié)點逛揩，已刪除");
return;
}
}
//@3.2 要刪除節(jié)點左右子樹都不為空
if (matchNode.left != null && matchNode.right != null) {
Node rightTreeMixnode = this.searchRightMixNode(matchNode.right);
delNode(rightTreeMixnode.value);
//刪除節(jié)點更確切的說是替換該節(jié)點的值，而不是替換該節(jié)點麸俘，如果替換該節(jié)點則會有改變整個樹結(jié)構(gòu)的可能
matchNode.value = rightTreeMixnode.value;
System.out.println("要刪除節(jié)點左右子樹都不為空辩稽，已刪除");
return;
}
//@3.3 要刪除節(jié)點有一個子樹
if (matchNode.left != null) {
if (parentNode.left.value == matchNode.value) {
parentNode.left = matchNode.left;
System.out.println("要刪除節(jié)有左子樹，該節(jié)點原為左子樹節(jié)點从媚，已刪除");
}
if (parentNode.right.value == matchNode.value) {
parentNode.right = matchNode.left;
System.out.println("要刪除節(jié)有左子樹逞泄，該節(jié)點原為右子樹節(jié)點，已刪除");
}
} else if (matchNode.right != null) {
if (parentNode.left.value == matchNode.value) {
parentNode.left = matchNode.right;
System.out.println("要刪除節(jié)有右子樹，該節(jié)點原為右子樹節(jié)點喷众，已刪除");
}
if (parentNode.right.value == matchNode.value) {
parentNode.right = matchNode.right;
System.out.println("要刪除節(jié)有右子樹各谚，該節(jié)點原為右子樹節(jié)點，已刪除");
}
}
}
public Node getRoot() {
return root;
}
}
兩種存儲方式的對比
二叉樹既可以用鏈式存儲到千，也可以用數(shù)組順序存儲昌渤。數(shù)組順序存儲的方式比較適合完全二叉樹，其他類型的二叉樹用數(shù)組存儲會比較浪費存儲空間憔四。
支持重復數(shù)據(jù)的二叉查找樹
我們利用對象的某個字段作為鍵值（key）來構(gòu)建二叉查找樹膀息。我們把對象中的其他字段叫作衛(wèi)星數(shù)據(jù)。
針對的都是不存在鍵值相同的情況加矛，有兩種方式來解決：
1.同一個節(jié)點存儲多個數(shù)據(jù)
利用鏈表或者支持動態(tài)擴容的數(shù)組履婉。
2.把這個新插入的數(shù)據(jù)當作大于這個節(jié)點的值來處理
每個節(jié)點仍然只存儲一個數(shù)據(jù)。在查找插入位置的過程中斟览，如果碰到一個節(jié)點的值毁腿，與要插入數(shù)據(jù)的值相同，我們就將這個要插入的數(shù)據(jù)放到這個節(jié)點的右子樹苛茂。
查找
遇到值相同的節(jié)點已烤，我們并不停止查找操作，而是繼續(xù)在右子樹中查找妓羊，直到遇到葉子節(jié)點胯究，才停止。這樣就可以把鍵值等于要查找值的所有節(jié)點都找出來躁绸。
刪除
對于刪除操作裕循，我們也需要先查找到每個要刪除的節(jié)點，然后再按前面講的刪除操作的方法净刮，依次刪除剥哑。
二叉樹的時間復雜度
二叉樹的插入，查找淹父，刪除都和樹的高度成正比株婴，如果求出二叉樹的層數(shù)公式，也就是求出二叉樹數(shù)據(jù)操作的時間復雜度暑认。
高度和節(jié)點的關(guān)系推導過程
在包含 n 個節(jié)點的滿二叉樹中困介，第一層包含 1 個節(jié)點，第二層包含 2 個節(jié)點蘸际，第三層包含 4 個節(jié)點座哩，依次類推，下面一層節(jié)點個數(shù)是上一層的 2 倍捡鱼，第 K 層包含的節(jié)點個數(shù)就是 2^(K-1)八回。
如果是完全二叉樹中酷愧，最后一層節(jié)點小于2^(K-1)。
n表示節(jié)點個數(shù)缠诅，L表示層數(shù)
n >= 1+2+4+8+...+2^(L-2)+1
n <= 1+2+4+8+...+2^(L-2)+2^(L-1)
這是一個等比數(shù)列求和溶浴。
根據(jù)等比公式
求L的取值范圍為：
[log2(n+1), log2n +1]
完全二叉樹的層數(shù)小于等于 log2n +1，也就是說管引，完全二叉樹的高度小于等于 log2n
通過大O理論可知其數(shù)據(jù)操作時間復雜度為:O(logn)士败。
可以看出二叉樹的數(shù)據(jù)操作時間復雜度很穩(wěn)定且高效，但是這個時間復雜度只適用于完全二叉樹褥伴，或者滿二叉樹谅将，二叉樹在極端情況下可能退化成鏈表，所以需要對二叉樹這種數(shù)據(jù)結(jié)構(gòu)進行升級重慢，讓他的數(shù)據(jù)操作的時間復雜度永遠符合O(logn)饥臂。
也就是在二叉查找樹的基礎(chǔ)上進行平衡，使之數(shù)據(jù)操作的時間復雜度永遠符合時間復雜度公式O(logn)似踱，這種升級版的二叉樹結(jié)構(gòu)為:
平衡二叉樹
二叉查找樹和散列表的對比
散列表的插入隅熙、刪除、查找操作的時間復雜度可以做到常量級的 O(1)核芽，非常高效囚戚。而二叉查找樹在比較平衡的情況下，插入轧简、刪除驰坊、查找操作時間復雜度才是 O(logn)。
二叉查找樹的優(yōu)勢
- 散列表順序輸出困難哮独，需要額外排序拳芙；
a. 散列表中的數(shù)據(jù)是無序存儲的，如果要輸出有序的數(shù)據(jù)皮璧，需要先進行排序态鳖。而對于二叉查找樹來說，我們只需要中序遍歷恶导，就可以在 O(n) 的時間復雜度內(nèi)，輸出有序的數(shù)據(jù)序列浸须。 - 散列表擴容代價比較大惨寿；
a. 散列表擴容耗時很多，而且當遇到散列沖突時删窒，性能不穩(wěn)定裂垦，盡管二叉查找樹的性能不穩(wěn)定，但是在工程中肌索，我們最常用的平衡二叉查找樹的性能非常穩(wěn)定蕉拢，時間復雜度穩(wěn)定在 O(logn)。 - 散列表查詢效率不一定比二叉樹高；
a. 籠統(tǒng)地來說晕换，盡管散列表的查找等操作的時間復雜度是常量級的午乓，但因為哈希沖突的存在，這個常量不一定比 logn 小闸准，所以實際的查找速度可能不一定比 O(logn) 快益愈。加上哈希函數(shù)的耗時，也不一定就比平衡二叉查找樹的效率高夷家。 - 散列表涉及更復雜蒸其；
a. 散列表的構(gòu)造比二叉查找樹要復雜，需要考慮的東西很多库快。比如散列函數(shù)的設(shè)計摸袁、沖突解決辦法、擴容义屏、縮容等靠汁。平衡二叉查找樹只需要考慮平衡性這一個問題，而且這個問題的解決方案比較成熟湿蛔、固定膀曾。 - 由于裝載因子，會浪費內(nèi)存阳啥；
a. 為了避免過多的散列沖突添谊，散列表裝載因子不能太大，特別是基于開放尋址法解決沖突的散列表察迟，不然會浪費一定的存儲空間斩狱。
平衡二叉查找樹
發(fā)明平衡二叉查找樹這類數(shù)據(jù)結(jié)構(gòu)的初衷是，解決普通二叉查找樹在頻繁的插入扎瓶、刪除等動態(tài)更新的情況下所踊，出現(xiàn)時間復雜度退化的問題。
平衡二叉查找樹中“平衡”的意思概荷，其實就是讓整棵樹左右看起來比較“對稱”秕岛、比較“平衡”，不要出現(xiàn)左子樹很高误证、右子樹很矮的情況继薛。這樣就能讓整棵樹的高度相對來說低一些，相應的插入愈捅、刪除遏考、查找等操作的效率高一些。
AVLTree(Adelson-Velsky-Landis Tree)
一種高度平衡二叉搜索樹
AVL樹是最先發(fā)明的自平衡二叉查找樹蓝谨。在AVL樹中任何節(jié)點的兩個兒子子樹的高度最大差別為一灌具，所以它也被稱為高度平衡樹青团。
AVL樹調(diào)整平衡的方式
左旋轉(zhuǎn)
右旋轉(zhuǎn)
雙旋轉(zhuǎn)
略
左旋右旋口訣
左旋動右給左
右旋動左給右
code
node
package com.pl.arithmetic.binaryTree.avl;
/**
* <p>
*
* @Description: TODO
* </p>
* @ClassName Node
* @Author pl
* @Date 2020/11/14
* @Version V1.0.0
*/
public class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
// AVLTree ---------------------------------------
public int leftHeight(){
if (left == null){
return 0;
}
return left.height();
}
public int rightHeight(){
if (right == null){
return 0;
}
return right.height();
}
/**
* 計算當前節(jié)點的樹高度
*
* @param
* @return int
* @exception
* @author silenter
* @date 2020/11/20 7:28
*/
public int height(){
return Math.max(left == null ?0:left.height(),right == null?0:right.height())+1;
}
/**
* 左旋前提右子樹高于左子樹
* 左旋右旋
*
* 創(chuàng)建新節(jié)點，代替當前根節(jié)點咖楣，左子樹和當前節(jié)點一樣督笆，右子樹變成右子樹的左子樹
* 右子樹等于當前節(jié)點右子樹的右子節(jié)點，當前節(jié)點的值等于右子節(jié)點的值截歉，當前節(jié)點左子樹指向新節(jié)點胖腾，
*
* @param
* @return void
* @exception
* @author silenter
* @date 2020/11/20 8:13
*/
public void leftRoute(){
Node newNode = new Node(this.value);
newNode.left = this.left;
newNode.right = this.right.left;
this.value = right.value;
this.right = right.right;
this.left = newNode;
}
/**
* 右旋的前提，左子樹高于右子樹
*
* @param
* @return void
* @exception
* @author silenter
* @date 2020/11/20 8:14
*/
public void rightRoute(){
Node newNode = new Node(this.value);
newNode.left = left.right;
newNode.right = right;
value = left.value;
left = left.left;
right = newNode;
}
/**
* 添加節(jié)點 和bst相比瘪松，只有添加不同
*
* @param node
* @return void
* @exception
* @author silenter
* @date 2020/11/14 9:31
*/
public void addNode(Node node){
verifyNode(node);
if (node.value<this.value){
if (this.left!=null){
this.left.addNode(node);
}else if (this.left == null){
this.left = node;
}
}
if (node.value>this.value){
if (this.right!=null){
this.right.addNode(node);
}else if (this.right == null){
this.right = node;
}
}
//左高右旋
if (leftHeight()-rightHeight()>1){
if (right != null && left.rightHeight()>left.leftHeight()){
left.leftRoute();
rightRoute();
}else {
rightRoute();
}
}
//右高左旋
if (rightHeight()-leftHeight()>1){
if (right != null && right.leftHeight()>right.rightHeight()){
right.rightRoute();
leftRoute();
}else {
leftRoute();
}
}
}
// AVLTree ---------------------------------------
public Node searchRightMixNode(Node node){
Node tempNode = node;
while (tempNode.left!=null){
tempNode = tempNode.left;
}
return tempNode;
}
/**
* 查找指定節(jié)點
*
* @param value
* @return com.pl.arithmetic.binaryTree.binarySearchTree.Node
* @exception
* @author silenter
* @date 2020/11/14 10:18
*/
public Node searchNode(int value){
Node tempNode = null;
if (this.value == value){
tempNode = this;
System.out.println("找到指定節(jié)點");
return tempNode;
}
if (tempNode ==null){
if (value<this.value && this.left!=null){
tempNode = this.left.searchNode(value);
}
if (value>this.value&&this.right!=null){
tempNode = this.right.searchNode(value);
}
}
return tempNode;
}
/**
* 查找當前節(jié)點的父節(jié)點
*
* @param value
* @return com.pl.arithmetic.binaryTree.binarySearchTree.Node
* @exception
* @author silenter
* @date 2020/11/14 9:32
*/
public Node searchParentNode(int value){
if ((this.left !=null && this.left.value == value) || (this.right !=null && this.right.value == value)){
System.out.println("找到該父節(jié)點"+this);
return this;
}else{
if (value <this.value && this.left!=null){
return this.left.searchParentNode(value);
}else if (value>this.value && this.right!=null) {
return this.right.searchParentNode(value);
}
}
return null;
}
/**
* 前序遍歷
*
* @param
* @return void
* @exception
* @author silenter
* @date 2020/11/14 9:19
*/
//中序遍歷
public void infixOrder() {
if(this.left != null) {
this.left.infixOrder();
}
System.out.println(this);
if(this.right != null) {
this.right.infixOrder();
}
}
public void verifyNode(Node node){
if (node ==null){
throw new RuntimeException("node為空");
}
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
}
AVLTree
package com.pl.arithmetic.binaryTree.avl;
/**
* <p>
*
* @Description: TODO
* </p>
* @ClassName AVLTree
* @Author pl
* @Date 2020/11/20
* @Version V1.0.0
*/
public class AVLTree {
private Node root;
public Node getRoot() {
return root;
}
// 添加結(jié)點的方法
public void add(Node node) {
if (root == null) {
root = node;// 如果root為空則直接讓root指向node
} else {
root.addNode(node);
}
}
// 中序遍歷
public void infixOrder() {
if (root != null) {
root.infixOrder();
} else {
System.out.println("二叉排序樹為空咸作，不能遍歷");
}
}
}
AVLTreeDemo
package com.pl.arithmetic.binaryTree.avl;
/**
* <p>
*
* @Description: TODO
* </p>
* @ClassName AVLTreeDemo
* @Author pl
* @Date 2020/11/20
* @Version V1.0.0
*/
public class AVLTreeDemo {
public static void main(String[] args) {
//int[] arr = {4,3,6,5,7,8};
//int[] arr = { 10, 12, 8, 9, 7, 6 };
int[] arr = { 10, 11, 7, 6, 8, 9 };
//創(chuàng)建一個 AVLTree對象
AVLTree avlTree = new AVLTree();
//添加結(jié)點
for(int i=0; i < arr.length; i++) {
avlTree.add(new Node(arr[i]));
}
//遍歷
System.out.println("中序遍歷");
avlTree.infixOrder();
System.out.println("在平衡處理~~");
System.out.println("樹的高度=" + avlTree.getRoot().height()); //3
System.out.println("樹的左子樹高度=" + avlTree.getRoot().leftHeight()); // 2
System.out.println("樹的右子樹高度=" + avlTree.getRoot().rightHeight()); // 2
System.out.println("當前的根結(jié)點=" + avlTree.getRoot());//8
}
}
紅黑樹（RB-Tree）
為何要引入紅黑樹？
AVL 樹是一種高度平衡的二叉樹宵睦，所以查找的效率非常高记罚，但是，有利就有弊壳嚎，AVL 樹為了維持這種高度的平衡桐智，就要付出更多的代價。每次插入烟馅、刪除都要做調(diào)整说庭，就比較復雜、耗時郑趁。所以襟雷，對于有頻繁的插入避矢、刪除操作的數(shù)據(jù)集合撩嚼，使用 AVL 樹的代價就有點高了按咒。
紅黑樹只是做到了近似平衡，并不是嚴格的平衡梭纹，所以在維護平衡的成本上躲惰，要比 AVL 樹要低。
紅黑樹的應用
紅黑樹（Red-Black Tree变抽，以下簡稱RBTree）的實際應用非常廣泛础拨，比如Linux內(nèi)核中的完全公平調(diào)度器、高精度計時器绍载、ext3文件系統(tǒng)等等太伊，各種語言的函數(shù)庫如Java的TreeMap和TreeSet，C++ STL的map逛钻、multimap、multiset等锰提。
RBTree也是函數(shù)式語言中最常用的持久數(shù)據(jù)結(jié)構(gòu)之一曙痘，在計算幾何中也有重要作用芳悲。值得一提的是，Java 8中HashMap的實現(xiàn)也因為用RBTree取代鏈表边坤，性能有所提升名扛。
紅黑樹的定義
- 任何一個節(jié)點都有顏色，黑色或者紅色
- 根節(jié)點是黑色的
- 任何相鄰的節(jié)點都不能同時為紅色
- 任何一個節(jié)點向下遍歷到其子孫的葉子節(jié)點茧痒，所經(jīng)過的黑節(jié)點個數(shù)必須相等（據(jù)不平衡肮韧，從而保持整體平衡）
- 空節(jié)點被認為是黑色的，即葉子節(jié)點是黑色的旺订。
notice
紅黑樹的高度
紅黑樹是在原先的二叉查找樹的基礎(chǔ)上引入黑色節(jié)點來平衡二叉樹高度弄企，即如果將紅色節(jié)點構(gòu)成的樹比作BSTree，其高度近似于㏒??
区拳，那么引入紅色節(jié)點的紅黑樹拘领，根據(jù)紅黑樹的定義3,4可知，紅黑樹中的的最長路徑（從根節(jié)點到葉子節(jié)點）即此路徑上紅黑節(jié)點數(shù)量相等樱调，那么紅黑樹最多比BSTree高一般约素，即紅黑樹的高度近似于2㏒??。
所以笆凌，紅黑樹的高度只比高度平衡的 AVL 樹的高度㏒??僅僅大了一倍圣猎，在性能上，下降得并不多乞而。這樣推導出來的結(jié)果不夠精確送悔，實際上紅黑樹的性能更好。
紅黑樹的插入
紅黑樹的插入操作可以分為兩步：
1.插入
2.插入后的平衡調(diào)整
插入后的修復操作有三種情況
- 關(guān)注節(jié)點（a）晦闰，父節(jié)點放祟，叔叔節(jié)點均為紅色。
a. 將關(guān)注節(jié)點 a 的父節(jié)點 b呻右、叔叔節(jié)點 d 的顏色都設(shè)置成黑色跪妥；
b. 將關(guān)注節(jié)點 a 的祖父節(jié)點 c 的顏色設(shè)置成紅色；
c. 關(guān)注節(jié)點變成 a 的祖父節(jié)點 c声滥；
d. 跳到 CASE 2 或者 CASE 3眉撵。
2.關(guān)注節(jié)點（a）和父節(jié)點均為紅色，叔叔節(jié)點為黑色落塑，且關(guān)注的節(jié)點是父節(jié)點的右子節(jié)點纽疟。
a. 關(guān)注節(jié)點變成節(jié)點 a 的父節(jié)點 b；
b. 圍繞新的關(guān)注節(jié)點b 左旋憾赁；
c. 跳到 CASE 3污朽。
3.關(guān)注節(jié)點(a)和父節(jié)點均為紅色，叔叔節(jié)點為黑色龙考，關(guān)注節(jié)點 a 是其父節(jié)點 b 的左子節(jié)點
a. 圍繞關(guān)注節(jié)點 a 的祖父節(jié)點 c 右旋蟆肆；
b. 將關(guān)注節(jié)點 a 的父節(jié)點 b矾睦、兄弟節(jié)點 c 的顏色互換。
c. 調(diào)整結(jié)束炎功。
code
private void insert(RBTNode<T> node) {
int cmp;
RBTNode<T> parentNode = null;
RBTNode<T> tempNode = this.mRoot;
// 1. 將紅黑樹當作一顆二叉查找樹枚冗，將節(jié)點添加到二叉查找樹中。
while (tempNode != null) {
parentNode = tempNode;
cmp = node.key.compareTo(tempNode.key);
if (cmp < 0)
tempNode = tempNode.left;
else
tempNode = tempNode.right;
}
node.parent = parentNode;
if (parentNode!=null) {
cmp = node.key.compareTo(parentNode.key);
if (cmp < 0)
parentNode.left = node;
else
parentNode.right = node;
} else {
this.mRoot = node;
}
// 2. 設(shè)置節(jié)點的顏色為紅色
node.color = RED;
// 3. 將它重新修正為一顆二叉查找樹
insertFixUp(node);
}
/*
* 紅黑樹插入修正函數(shù)
*
* 在向紅黑樹中插入節(jié)點之后(失去平衡)蛇损，再調(diào)用該函數(shù)赁温；
* 目的是將它重新塑造成一顆紅黑樹。
*
* 參數(shù)說明：
* node 插入的結(jié)點
*/
private void insertFixUp(RBTNode<T> node) {
RBTNode<T> parent, gparent;
// 若“父節(jié)點存在淤齐，并且父節(jié)點的顏色是紅色”
while (((parent = parentOf(node))!=null) && isRed(parent)) {
gparent = parentOf(parent);
//若“父節(jié)點”是“祖父節(jié)點的左孩子”
if (parent == gparent.left) {
// Case 1條件：叔叔節(jié)點是紅色
RBTNode<T> uncle = gparent.right;
if ((uncle!=null) && isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
//每將一個節(jié)點變?yōu)榧t色節(jié)點股囊，需要重新檢查其是否有兩個相連節(jié)點為紅色，所以需要將當前節(jié)點變成新變?yōu)榧t色節(jié)點的gparent
node = gparent;
continue;
}
// Case 2條件：叔叔是黑色毁涉，且當前節(jié)點是右孩子
if (parent.right == node) {
RBTNode<T> tmp;
leftRotate(parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3條件：叔叔是黑色，且當前節(jié)點是左孩子贫堰。
setBlack(parent);
setRed(gparent);
rightRotate(gparent);
} else { //若“z的父節(jié)點”是“z的祖父節(jié)點的右孩子”
// Case 1條件：叔叔節(jié)點是紅色
RBTNode<T> uncle = gparent.left;
if ((uncle!=null) && isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(gparent);
node = gparent;
continue;
}
// Case 2條件：叔叔是黑色蛤袒，且當前節(jié)點是左孩子
if (parent.left == node) {
RBTNode<T> tmp;
rightRotate(parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3條件：叔叔是黑色珍德，且當前節(jié)點是右孩子。
setBlack(parent);
setRed(gparent);
leftRotate(gparent);
}
}
// 將根節(jié)點設(shè)為黑色
setBlack(this.mRoot);
}
紅黑樹的刪除
紅黑樹的刪除也是分為兩步：
1.指定節(jié)點的刪除
2.刪除節(jié)點后的平衡修復
刪除修復操作分為四種情況(刪除黑節(jié)點后)：
- 待刪除的節(jié)點的兄弟節(jié)點是紅色的節(jié)點。
- 待刪除的節(jié)點的兄弟節(jié)點是黑色的節(jié)點，且兄弟節(jié)點的子節(jié)點都是黑色的且改。
- 待調(diào)整的節(jié)點的兄弟節(jié)點是黑色的節(jié)點，且兄弟節(jié)點的左子節(jié)點是紅色的，右節(jié)點是黑色的(兄弟節(jié)點在右邊)，如果兄弟節(jié)點在左邊的話，就是兄弟節(jié)點的右子節(jié)點是紅色的，左節(jié)點是黑色的未斑。
- 待調(diào)整的節(jié)點的兄弟節(jié)點是黑色的節(jié)點芽突，且右子節(jié)點是是紅色的(兄弟節(jié)點在右邊)，如果兄弟節(jié)點在左邊壹哺，則就是對應的就是左節(jié)點是紅色的静陈。
修復完畢標志：
刪除修復操作在遇到被刪除的節(jié)點是紅色節(jié)點或者到達root節(jié)點時胡岔，修復操作完畢肄鸽。
notice：
紅黑樹刪除后的平衡實質(zhì)是節(jié)點的借調(diào)
刪除修復操作是針對刪除黑色節(jié)點才有的，當黑色節(jié)點被刪除后會讓整個樹不符合RBTree的定義的第四條擂错。需要做的處理是從兄弟節(jié)點上借調(diào)黑色的節(jié)點過來昨凡，如果兄弟節(jié)點沒有黑節(jié)點可以借調(diào)的話爽醋，就只能往上追溯，將每一級的黑節(jié)點數(shù)減去一個土匀，使得整棵樹符合紅黑樹的定義子房。
刪除操作的總體思想是從兄弟節(jié)點借調(diào)黑色節(jié)點使樹保持局部的平衡，如果局部的平衡達到了，就看整體的樹是否是平衡的证杭，如果不平衡就接著向上追溯調(diào)整田度。
刪除操作-case 1
由于兄弟節(jié)點是紅色節(jié)點的時候，無法借調(diào)黑節(jié)點解愤，所以需要將兄弟節(jié)點提升到父節(jié)點镇饺，由于兄弟節(jié)點是紅色的，根據(jù)RBTree的定義送讲，兄弟節(jié)點的子節(jié)點是黑色的奸笤，就可以從它的子節(jié)點借調(diào)了。
case 1這樣轉(zhuǎn)換之后就會變成后面的case 2哼鬓，case 3监右，或者case 4進行處理了。上升操作需要對C做一個左旋操作异希，如果是鏡像結(jié)構(gòu)的樹只需要做對應的右旋操作即可健盒。
之所以要做case 1操作是因為兄弟節(jié)點是紅色的，無法借到一個黑節(jié)點來填補刪除的黑節(jié)點称簿。
刪除操作-case 2
case 2的刪除操作是由于兄弟節(jié)點可以消除一個黑色節(jié)點扣癣，因為兄弟節(jié)點和兄弟節(jié)點的子節(jié)點都是黑色的，所以可以將兄弟節(jié)點變紅憨降，這樣就可以保證樹的局部的顏色符合定義了父虑。這個時候需要將父節(jié)點A變成新的節(jié)點，繼續(xù)向上調(diào)整授药，直到整顆樹的顏色符合RBTree的定義為止士嚎。
case 2這種情況下之所以要將兄弟節(jié)點變紅，是因為如果把兄弟節(jié)點借調(diào)過來烁焙，會導致兄弟的結(jié)構(gòu)不符合RBTree的定義航邢，這樣的情況下只能是將兄弟節(jié)點也變成紅色來達到顏色的平衡。當將兄弟節(jié)點也變紅之后骄蝇，達到了局部的平衡了膳殷，但是對于祖父節(jié)點來說是不符合定義4的。這樣就需要回溯到父節(jié)點九火，接著進行修復操作赚窃。
刪除操作-case 3
case 3的刪除操作是一個中間步驟，它的目的是將左邊的紅色節(jié)點借調(diào)過來岔激，這樣就可以轉(zhuǎn)換成case 4狀態(tài)了勒极，在case 4狀態(tài)下可以將D，E節(jié)點都階段過來虑鼎，通過將兩個節(jié)點變成黑色來保證紅黑樹的整體平衡辱匿。
之所以說case-3是一個中間狀態(tài)键痛，是因為根據(jù)紅黑樹的定義來說，下圖并不是平衡的匾七，他是通過case 2操作完后向上回溯出現(xiàn)的狀態(tài)絮短。之所以會出現(xiàn)case 3和后面的case 4的情況，是因為可以通過借用侄子節(jié)點的紅色昨忆，變成黑色來符合紅黑樹定義4.
刪除操作-case 4
Case 4的操作是真正的節(jié)點借調(diào)操作丁频，通過將兄弟節(jié)點以及兄弟節(jié)點的右節(jié)點借調(diào)過來，并將兄弟節(jié)點的右子節(jié)點變成紅色來達到借調(diào)兩個黑節(jié)點的目的邑贴，這樣的話席里，整棵樹還是符合RBTree的定義的。
Case 4這種情況的發(fā)生只有在待刪除的節(jié)點的兄弟節(jié)點為黑拢驾，且子節(jié)點不全部為黑奖磁，才有可能借調(diào)到兩個節(jié)點來做黑節(jié)點使用，從而保持整棵樹都符合紅黑樹的定義繁疤。
實際上這張圖是錯誤的署穗，最終需要將C節(jié)點變成黑色節(jié)點，因為原先關(guān)注節(jié)點的兄弟節(jié)點是黑色嵌洼，如果變成紅色則影響局部平衡了。
code
/*
* 刪除結(jié)點(node)封恰，并返回被刪除的結(jié)點
*
* 參數(shù)說明：
* node 刪除的結(jié)點
*/
private void remove(RBTNode<T> node) {
RBTNode<T> child, parent;
boolean color;
// 被刪除節(jié)點的"左右孩子都不為空"的情況麻养。
if ( (node.left!=null) && (node.right!=null) ) {
// 被刪節(jié)點的后繼節(jié)點。(稱為"取代節(jié)點")
// 用它來取代"被刪節(jié)點"的位置诺舔，然后再將"被刪節(jié)點"去掉鳖昌。
RBTNode<T> replace = node;
// 獲取后繼節(jié)點
replace = replace.right;
while (replace.left != null)
replace = replace.left;
// "node節(jié)點"不是根節(jié)點(只有根節(jié)點不存在父節(jié)點)
if (parentOf(node)!=null) {
if (parentOf(node).left == node)
//這里直接替換了
parentOf(node).left = replace;
else
parentOf(node).right = replace;
} else {
// "node節(jié)點"是根節(jié)點，更新根節(jié)點低飒。
this.mRoot = replace;
}
// child是"取代節(jié)點"的右孩子许昨，也是需要"調(diào)整的節(jié)點"。
// "取代節(jié)點"肯定不存在左孩子褥赊！因為它是一個后繼節(jié)點糕档。
child = replace.right;
parent = parentOf(replace);
// 保存"取代節(jié)點"的顏色
color = colorOf(replace);
// "被刪除節(jié)點"是"它的后繼節(jié)點的父節(jié)點"
//以下調(diào)整取代節(jié)點的右子樹
if (parent == node) {
parent = replace;
} else {
// child不為空
if (child!=null)
setParent(child, parent);
//這里替換取代節(jié)點的右子樹到其父節(jié)點下，將取代節(jié)點的右子樹賦值為刪除節(jié)點的右子樹拌喉，此時取代節(jié)點已經(jīng)被刪除了
parent.left = child;
replace.right = node.right;
setParent(node.right, replace);
}
replace.parent = node.parent;
replace.color = node.color;
replace.left = node.left;
node.left.parent = replace;
//只有取代節(jié)點是黑色才修復速那，將取代節(jié)點的右子樹當做當前關(guān)注的節(jié)點進行調(diào)整（雖然是刪除節(jié)點，但是真正刪除的是取代節(jié)點）
if (color == BLACK)
removeFixUp(child, parent);
node = null;
return ;
}
if (node.left !=null) {
child = node.left;
} else {
child = node.right;
}
parent = node.parent;
// 保存"取代節(jié)點"的顏色
color = node.color;
if (child!=null)
child.parent = parent;
// "node節(jié)點"不是根節(jié)點
if (parent!=null) {
if (parent.left == node)
parent.left = child;
else
parent.right = child;
} else {
this.mRoot = child;
}
if (color == BLACK)
removeFixUp(child, parent);
node = null;
}
/*
* 紅黑樹刪除修正函數(shù)
*
* 在從紅黑樹中刪除插入節(jié)點之后(紅黑樹失去平衡)尿背，再調(diào)用該函數(shù)端仰；
* 目的是將它重新塑造成一顆紅黑樹。
*
* 參數(shù)說明：
* node 待修正的節(jié)點(原取代節(jié)點的子節(jié)點田藐，此時這個節(jié)點已經(jīng)替換了取代節(jié)點的位置荔烧，但是此時不影響此節(jié)點原先兄弟節(jié)點和和父節(jié)點的狀態(tài))
*/
private void removeFixUp(RBTNode<T> node, RBTNode<T> parent) {
RBTNode<T> other;
while ((node==null || isBlack(node)) && (node != this.mRoot)) {
if (parent.left == node) {
other = parent.right;
if (isRed(other)) {
// Case 1: x的兄弟w是紅色的
setBlack(other);
setRed(parent);
leftRotate(parent);
other = parent.right;
}
//Case 2: x的兄弟w是黑色鹤竭，且w的倆個孩子也都是黑色的
if (isBlack(other.left)&&isBlack(other.right)) {
//這種情況，其兄弟節(jié)點保持局部平衡，所以不動其兄弟節(jié)點，將關(guān)注節(jié)點換成取代節(jié)點的父節(jié)點，向上追溯
setRed(other);
node = parent;
parent = parentOf(node);
} else {
if (other.right!=null && isBlack(other.right)) {
// Case 3: x的兄弟w是黑色的，并且w的左孩子是紅色早芭，右孩子為黑色调炬。
setBlack(other.left);
setRed(other);
rightRotate(other);
//兄弟節(jié)點調(diào)整為右懸置后的兄弟節(jié)點
other = parent.right;
}
// Case 4: x的兄弟w是黑色的；并且w的右孩子是紅色的，左孩子任意顏色。
setColor(other, colorOf(parent));
setBlack(parent);
setBlack(other.right);
leftRotate(parent);
node = this.mRoot;
break;
}
} else {
other = parent.left;
if (isRed(other)) {
// Case 1: x的兄弟w是紅色的
setBlack(other);
setRed(parent);
rightRotate(parent);
other = parent.left;
}
if (isBlack(other.left) && isBlack(other.right)) {
// Case 2: x的兄弟w是黑色趴捅，且w的倆個孩子也都是黑色的
setRed(other);
node = parent;
parent = parentOf(node);
} else {
if (other.left!=null && isBlack(other.left)) {
// Case 3: x的兄弟w是黑色的猎拨，并且w的左孩子是紅色国觉，右孩子為黑色。
setBlack(other.right);
setRed(other);
leftRotate(other);
other = parent.left;
}
// Case 4: x的兄弟w是黑色的；并且w的右孩子是紅色的，左孩子任意顏色挪丢。
setColor(other, colorOf(parent));
setBlack(parent);
setBlack(other.left);
rightRotate(parent);
node = this.mRoot;
break;
}
}
}
//最后都是讓根節(jié)點為黑色節(jié)點
if (node!=null)
setBlack(node);
}
