線段樹Segment Tree
對于有一類問題，時常關注的是一個區間或者是一個線段，那麼就可以使用線段樹來解決。比較經典的問題，就是區間染色問題：有一面牆，長度為n，每次選擇一段牆來染色，一開始4-6繪制成黃色，然後1-10繪制藍色，2-7繪制紅色，若幹次繪色之後能看見多少種顔色，或者是在區間「i，j」區間裡面可以看到多少種顔色。是以主要有兩個操作，染色操作和查詢操作。使用數組操作其實是可以的，染色就隻需要把對應下标的内容，修改就好了；查找隻需要周遊，這樣複雜度就都是
，這樣很明顯效率是不夠的。
實質的應用就是區間查詢，比如統計2017年的消費最高的使用者，或者是某一個太空區間天體的總量。使用線段樹的之後：
| 使用數組實作 | 使用線段樹實作 | |
|---|---|---|
| 更新 | |  |
| 查詢 | | |
線段樹大緻的樣子。可以看到線段樹不是完全二叉樹，因為如果是十個元素，是不一定都集中在左邊的，這時候就不一定是完全二叉樹了，但是一定是平衡二叉樹。平衡二叉樹的定義是，最短深度和最大深度的差隻能為1，也就是不能超過1。雖然不是完全二叉樹，但是依然可以用數組來表示，将下面的空節點全部補全，這樣這棵樹就變成滿二叉樹了。如果區間有n個元素，而
，那麼就需要2n個空間來存儲。如果不是，那麼就需要4n個，因為多出的那一個需要一整行取填補它。
Create
建立線段樹其實很簡單，可以看到上面是對半分開。
private int leftChild(int index) {
return 2 * index + 1;
}
private int rightChild(int index) {
return 2 * index + 2;
}
求左右子樹的下标。
public class SegmentTree<E> {
private E[] data;
private E[] tree;
private Merger<E> merger;
public SegmentTree(E[] arr, Merger<E> merger) {
this.merger = merger;
data = (E[]) new Object[arr.length];
for (int i = 0; i < arr.length; i++) {
data[i] = arr[i];
}
tree = (E[]) new Object[4 * arr.length];
buildSegmentTree(0, 0, data.length - 1);
}
data是傳進來的資料，tree是樹的資料merger是操作。還是遞歸，因為樹這種資料結構用起遞歸是天然的友善。參數要有兩個主要的參數，左邊和右邊的邊界，其實按照上面的圖就是中分。當l >= r的時候就是遞歸的最終條件，這個時候直接相等即可，否則就遞歸建構。
private void buildSegmentTree(int treeIndex, int l, int r) {
if (l >= r) {
tree[treeIndex] = data[l];
return;
} else {
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
int mid = l + (r - l) / 2;
buildSegmentTree(leftTreeIndex, l, mid);
buildSegmentTree(rightTreeIndex, mid + 1, r);
tree[treeIndex] = merger.merger(tree[leftTreeIndex], tree[rightTreeIndex]);
}
}
merger是一個接口，這是因為如果把這個功能寫死了，那麼線段樹的功能就死了。比如求和，如果寫死了那麼這個樹就隻能求和。而如果加上了接口，最小值最大值也是可以的。線段樹其實也是一種空間換時間的做法。
public static void main(String[] args) {
Integer[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
SegmentTree<Integer> segmentTree = new SegmentTree<Integer>(arr, (a, b) -> a > b?a:b);
segmentTree.show();
}
查找最大值。Merger就是就是一個接口，具體實作是看業務需求。
Query
線段樹是二分的，那麼這個時候如果要查找的區間并不是是剛剛好二分的一邊那就需要一個區間找一點一個區間找一點這樣的來組合了。比如找A[2,5]，那麼[0,3]找一邊，[4,7]找一邊就好了。
同樣是使用遞歸實作，首先參數要包含的就是樹的邊界和要求的邊界，如果邊界是完全一樣的，直接把目前樹對應的值傳回即可，如果邊界是在左邊，那就遞歸左邊找，右邊就右邊找，兩邊都包含還是遞歸相加傳回即可。
ry(int queryL, int queryR) {
if (queryL < 0 || queryL >= data.length || queryR < 0 || queryR >= data.length || queryL > queryR) {
throw new IllegalArgumentException("permater is illgel!");
}
return query(0, 0, data.length - 1, queryL, queryR);
}
private E query(int treeIndex, int l, int r, int queryL, int queryR) {
if (l == queryL && r == queryR) {
return tree[treeIndex];
}
int mid = l + (r - l) / 2;
int left = leftChild(treeIndex);
int right = rightChild(treeIndex);
if (queryL >= mid + 1) {
return query(right, mid + 1, r, queryL, queryR);
} else if (queryR <= mid) {
return query(left, l, mid, queryL, queryR);
} else {
return merger.merger(query(left, l, mid, queryL, mid), query(right, mid + 1, r, mid + 1, queryR));
}
}
Leecode303
這道題目其實就可以用剛剛的線段樹解決，使用上面的線段樹就可以直接解決。但其實這并不是最好的解決方法，因為這個題目在前面是要求有一個構造函數的，聯想到在ACM這些題目中有一種方法就是打表法，打表時間是不計入時間的，使用這個時候就可以在構造函數的時候計算疊代元素的和即可，比如存到了第4個元素，那麼第四個元素這個空就不存第四個元素，而是存第四個元素前面的和，包括了第四個元素，也就是[0,4]的和，這樣計算的時候隻需要一次減法即可。但是這裡學到了SegmentTree就直接用了
public class NumArray {
private SegementTree segementTree;
public NumArray(int[] nums) {
segementTree = new SegementTree(nums);
}
public int sumRange(int i, int j) {
if (segementTree == null){
return 0;
}
return segementTree.query(i, j);
}
public static void main(String[] args) {
int[] nums = {-2, 0, 3, -5, 2, -1};
NumArray numArray = new NumArray(nums);
// System.out.println(numArray.sumRange(0, 2));
}
}
Update
再來看一道題目：
這個題目和上一個題目是有相似之處的，但是不同的是它是要求可變的，也就是涉及到了線段樹的可變操作。
線段樹的更新其實最簡單的。首先參數肯定是更新的索引和變量，遞歸尋找索引所存在的樹，找到之後不論左右子樹有沒有改變，全部重新相加即可。更新還是查找複雜度都會是
。
public void set(int index, E e) {
if (index < 0 || index >= data.length) {
throw new IllegalArgumentException("index is illgel!!!");
}
data[index] = e;
set(0, 0, data.length - 1, index, e);
}
private void set(int treeIndex, int l, int r, int index, E e) {
if (l == r){
tree[treeIndex] = e;
return;
}
int mid = l + (r - l)/2;
int left = leftChild(index);
int right = rightChild(index);
if (index <= mid){
set(left, l, mid, index, e);
}else if (index > mid){
set(right, mid+1, right, index, e);
}
tree[treeIndex] = merger.merger(tree[left], tree[right]);
}
上面那個題目也是一樣的，隻需要在update裡面添加set函數即可。
二維線段樹
這裡介紹其實是一維的線段樹，還存在有二維的線段樹。一維的意思就是我們處理的就是一個一維的資料，也就是一條線上。同樣把這個思想擴充到二維空間：
線段樹隻是一種設計思想，三維就分成八個，也是一樣的。另外，這裡的線段樹區分是使用平均操作，但是有時候在某一個區間通路很少，再某一個區間很多，這樣就可以不均分，也叫動态線段樹。
字典樹Trie
之前所讨論的樹都是二叉樹，無論是搜尋時還是線段樹，或者是後面要講的紅黑樹都是二叉樹，而字典樹是多叉樹。通常字典樹是用來處理字元串。比如有20萬個字元，要進行查詢，如果是用樹結構基本就是
，但是如果用字典樹，這複雜度和數量沒有關系了，隻和你查詢的這個字元串的長度有關。
當周遊到葉子，那麼就周遊出了一個單詞。在設計節點的時候，按照正常操作，還是要存儲節點内容，和指向下一個節點的指針。但是要注意，在查詢的時候，我們是直接知道了下一個字元，也就是在查找之前就已經知道下一個字母了，和查字典一樣，是以是并不需要目前節點的内容。如果一個單詞是另一個單詞的結尾，那麼有可能就不是葉子節點了，是以還需要一個辨別來辨別這個是不是單詞結尾。
建立字典樹就比較簡單了，之前提到，需要辨別和指向下一個節點，由于這個節點數量是不知道的，是以用映射來替代。
public class Trie {
private class Node {
public boolean isWord;
public TreeMap<Character, Node> next;
public Node(boolean isWord) {
this.isWord = isWord;
next = new TreeMap<>();
}
public Node() {
this(false);
}
}
private Node root;
private int size;
public Trie() {
root = new Node();
this.size = 0;
}
add
添加元素也很簡單，添加的時候周遊字元串下一個字元，通過這個字元找到下一個節點，如果到了最後一個，那麼就要設定辨別，表示這個是一個單詞。但是這裡有一個小陷阱，有可能有插入重複單詞，這個時候就需要判斷辨別來維護size了。
public void add(String word) {
Node cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.next.get(c) == null) {
cur.next.put(c, new Node());
}
cur = cur.next.get(c);
}
if (!cur.isWord) {
cur.isWord = true;
size++;
}
}
Selection
查找方法其實也很簡單，首先看看目前next的映射裡面有沒有目前要查找的字元，如果沒有，直接就傳回false，如果有就留下。當周遊到最後一個的時候不能直接傳回true，因為如果辨別不是true，那麼隻能說明是恰好有這個單詞在，而不是有這個單詞，這個單詞可能是剛剛好是某一個單詞的字首而已。
public boolean contains(String word) {
Node cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.next.get(c) != null){
cur = cur.next.get(c);
}else {
return false;
}
}
return cur.isWord;
}
字首搜尋
電話本的搜尋如果你打入一個字母，就可以出現前面單詞是這個字母的所有人，這個就是字首搜尋，資料庫也有這樣的搜尋。
其實和之前的搜尋沒有什麼差别：
public boolean isPrefix(String word){
Node cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.next.get(c) == null){
return false;
}
cur = cur.next.get(c);
}
return true;
}
Leecode208
Leecode裡面有一道這樣的題目，就是實作字典樹：
和之前所實作的完全一樣，直接替換一下即可。
Leecode211
和以往的不同，這個題目添加了類似于正規表達式的比對，點代表任何字元。其他都差不多，就是搜尋不一樣。遇到點自然就是要周遊所有的可能了。使用遞歸實作比較簡單，首先是判斷邊界條件，如果要比較的索引已經是最後一個字元了，那就直接傳回辨別。辨別有的才能算有。如果不是，那就要遞歸通路了，是具體字元，就和之前的查找一樣，如果是"."，周遊所有下一個節點的字元，隻要有一個符合那就可以繼續，如果都沒有或者是空，那麼久可以傳回false了。
private boolean match(Node node, String word, int index) {
if (index == word.length()) {
return node.isWord;
}
char c = word.charAt(index);
if (c != '.') {
if (node.next.get(c) == null) {
return false;
} else {
return match(node.next.get(c), word, index + 1);
}
} else {
for (char key : node.next.keySet()) {
if (match(node.next.get(key), word, index + 1)) {
return true;
}
}
return false;
}
}
Trie作為map使用
這個題目要求計算包含字首的單詞的權值相加是多少。用遞歸很容易可以解答。首先要确認字首在這個字典樹裡面有的，然後再字首的基礎上把後面的單詞全部加起來即可。因為我們關注的是value值而不是單詞，是以不需要Word，也就是辨別，有沒有都無所謂，value為0就沒有單詞，也可以替代的。
public int sum(String prefix) {
Node cur = root;
for (int i = 0; i < prefix.length(); i++) {
char c = prefix.charAt(i);
if (cur.next.get(c) == null){
return 0;
}
cur = cur.next.get(c);
}
return sum(cur);
}
private int sum(Node cur){
int res = cur.value;
for (char key : cur.next.keySet()){
res += sum(cur.next.get(key));
}
return res;
}
}
最後的遞歸看起來好像沒有判斷遞歸到底的條件，但是實際上已經包含了，當節點的下一個是空的時候，就不經過for循環了，就可以直接傳回。
AVL樹
對于二叉樹，有時候會存在一些比較極端的情況，如果按照順序插入，就會變成類似連結清單那種情況，這個時候就複雜度就會回到n了，沒有展現出樹的優勢。是以在插入的時候，我們需要維持樹的結構。比較經典的平衡二叉樹之一就是AVL樹了。
平衡二叉樹
首先聲明是平衡二叉樹，首先滿的二叉樹肯定是一棵平衡二叉樹，平衡二叉樹可以使得樹的高度可以達到一個最低的高度。線段樹也是一個平衡二叉樹。在AVL裡面，任意一個節點左右節點高度差不不能超過1。是以需要标注每一個節點的高度，高度可以從底層開始計算，有了高度，那麼就可以計算平衡因子，平衡因子其實就是兩棵左右子樹的高度差，如果高度差沒有超過1那麼就算是平衡了。
添加操作
出現不平橫的時候隻有兩種情況，一個就是添加的時候，另一個就是删除的時候。插入的時候，需要向上維護平衡性。
1.插入的元素是在不平衡節點的左側的左側。也就是一直向左側插入元素。
這也是最簡單的一種情況，插入的時候左孩子比較深，補全：
可以看到，這種情況下首先目前節點的平衡因子一定大于0，其次左側孩子的平衡因子是大于等于0。第一個條件很好了解，二叉樹不平衡的條件，第二個條件是因為，既然是左側多添加了一個節點，左邊肯定比右邊高，而平衡因子在這裡計算的是左邊減去右邊，是以肯定是大于等于0的了。事實上應該隻有大于0，因為等于0的話，那就意味着左邊子樹單獨拿出來是平衡的，但是如果是平衡又要比右邊子樹多的話，那就意味着要比右邊多數兩個，但是多出一個的時候就已經需要改變的了，是以應該隻是大于0，然而，這隻是在添加的情況下有，删除就不一定了，比如上面情況，右邊子樹的有一個右子樹，删除的時候剛剛高把那個右子樹删了，而左邊恰好等于0，那麼還是需要換的。另外，還有一個更重要的原因，當左子樹等于0的時候，或者是右子樹等于0的時候，進行的旋轉隻能是左旋轉，或者右旋轉，當然對應的前提條件是目前節點是左邊導緻的不平衡或者是右邊。**這個時候一個要進行右旋轉。 **
右旋轉
5對應的右節點接到7的左節點上，旋轉完之後還需要更改高度，先更改子樹的高度再更改節點高度。Data Structure_樹線段樹Segment Tree字典樹TrieAVL樹紅黑樹
2.插入的元素是右子樹的右子樹，也就是一直向右側插入元素。
這個時候就應該是右側子樹導緻的，一直向右側插入元素，那麼右子樹的右邊肯定也多出來了。是以就需要左旋轉。
左旋轉
Data Structure_樹線段樹Segment Tree字典樹TrieAVL樹紅黑樹
3.如果是往左子樹的右子樹插入了導緻不平衡，那麼一次旋轉是不可以的了。這種情況下隻能回到我們之前解決過的情況處理，可以通過先把目前節點的左節點進行左旋轉變成情況一，再對目前節點進行右旋轉即可。是以就是先對左子樹進行左旋轉，再對目前節點進行右旋轉。
4.如果是往右子樹的左節點添加導緻了不平衡，那麼就需要先右旋轉再進行左旋轉即可。和上面的情況其實是兩兩對應的。
public Node add(Node node, K key, V value) {
if (node == null) {
size++;
return new Node(key, value);
}
if (key.compareTo(node.key) > 0) {
node.right = add(node.right, key, value);
} else if (key.compareTo(node.key) < 0) {
node.left = add(node.left, key, value);
} else {
node.value = value;
}
node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
int balanceFactor = getBalanceFactor(node);
if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) {
return rightRotate(node);
}
if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) {
return leftRotate(node);
}
if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}
先添加元素，添加完之後再依照上面的情況進行調整。
删除操作
删除的時候，維護其實是一樣的。 上面實際上已經列舉了所有的不平衡的情況，所有這裡隻需要在删除的時候添加葛總不平衡的情況即可。
總結
在AVL樹中還可以進行優化，每一次查詢和删除都是達到了logn的時間複雜度。但是每一次更新都需要維護高度，如果目前節點是沒有改變高度的話，其實是不需要維護上層節點的高度的了。因為從祖先節點來看，子樹高度是沒有變化的。AVL樹還有一種優化結構，就是紅黑樹這種資料結構。
紅黑樹
樹的平衡
樹的平衡是指樹的每一個節點的左右子節點的數目大緻一樣。兩邊都相等是最好的，當然這種情況很少見，一般都是兩邊大緻相等。比如在二叉搜尋樹的時候，如果插入的數字是有順序的，那麼就容易退化成極其不平衡的連結清單，搜尋複雜度就會變成
了。是以對于插入順序不是平衡的時候，之前所學過的二叉樹就不再是一種好的資料結構了。這個時候就要使用紅黑樹了，紅黑樹其實也是一種二叉樹，隻不過是增加了某種特性的二叉樹。如果在插入或删除的時候如果出現了不平衡的狀态，那麼就要進行調整，保持樹的平衡。
紅黑樹的特征
首先每一個節點都有顔色，在删除和添加的過程中是需要保持這些顔色的排列規律。從2-3樹來看。2-3樹是滿足二分搜尋樹的基本性質的。但是2-3樹不是二叉樹，節點可以存放一個元素或者是兩個元素。
可以看到，如果隻有一個元素，那麼隻能伸出兩個節點；但是如果存放了2個節點，那麼就可以存放三個節點。那麼如果要滿足二分搜尋樹的性質，如果是一個節點的時候，左小右大，兩個節點的時候就需要左小中右大，中間的要夾在bc中間。
總體的樹結構。二三樹一顆絕對平衡的樹，從根節點到葉子節點經過的節點數是一緻的。對于AVL樹，它的平衡條件沒有太嚴格。
那麼2-3樹是如何維持絕對平衡的？
首先添加一個節點42，如果是空節點，那麼就直接添加作為根節點，這個時候隻有一個節點的樹是一個平衡樹。再添加一個37節點，按照二叉樹的正常操作，應該和目前節點比較，看看添加到哪裡合适，但是對于2-3樹不是，它永遠不會添加到一個空的節點，會添加到最後一個葉子節點上，現在隻有一個根節點，是以就需要和42融合，形成了一個[37,42]的節點。再添加一個12，12比他們都要小，是以應該添加到左子樹去，永遠不會去空的位置，是以還得需要融合，雖然這個融合不符合規矩，但是先進行融合等等處理，這個時候就出現了4節點[12,37,42]。由于不符合規矩，是以可以很容易的就分裂成三個節點。中間節點是37，左右兩邊分别是12和42。再次添加一個18節點，應當添加在左邊，是以自然就添加在了12這個葉子節點上面，滿三個自然就分裂。當添加到第二層的時候再分裂就是這個樣子：但是可以看到，其實不是絕對平衡的。如果一個葉子節點本來就是三節點，添加到一個新的節點變成四節點在進行拆解的時候，就需要和它的父親節點融合。Data Structure_樹線段樹Segment Tree字典樹TrieAVL樹紅黑樹 是以在整一個添加過程中，2-3樹的結構是絕對平衡的。然而還有一種情況：Data Structure_樹線段樹Segment Tree字典樹TrieAVL樹紅黑樹 按照正常操作，上浮融合，自然根節點也要進行融合分裂：Data Structure_樹線段樹Segment Tree字典樹TrieAVL樹紅黑樹 很明顯還是一個平衡的，是以在整一個添加過程中是絕對平衡的。 在葉子節點達到四節點的時候就需要一步一步往上堆，一直到根節點。Data Structure_樹線段樹Segment Tree字典樹TrieAVL樹紅黑樹
紅黑樹的規則
1.每一個節點不是紅色就是黑色。
2.根節點總是黑色。
3.如果節點是紅色，那麼子節點一定是黑色。但是黑色節點下面的子節點可以是紅色也可以是黑色。
4.每一個葉子節點，這裡的葉子節點不是指有數值的葉子節點，而是指最後的空節點叫做葉子節點，也就是null節點是黑色的。
5.從任意一個節點到葉子節點經過的黑色節點是一樣的。
這些規則直接提出來不好了解，來看看對應于2-3樹是怎麼了解的。首先看看紅黑樹顔色在2-3樹中是代表了什麼意義，如果葉子節點是紅色，那麼就代表這個節點和根節點是融合在一起的，黑色就是分開，這個性質很重要。在紅黑樹中根節點一定是黑色，那麼一開始添加的42就是黑色的，然後添加了一個37，這樣這兩個節點就對應了2-3樹的三節點，來了12後紅黑樹的形狀：
可以看到，葉子節點是紅色的，按照剛剛的表述，其實是和父節點融合的，分裂後隻需要改變顔色就好了，是以把兩個葉子節點變成黑色即可。
如果這個節點是葉子節點，這個根節點要繼續向上融合，是以這個節點要變成紅色才代表向上融合。
這個就對應了在三節點上添加元素的操作。
這是一種情況，第二種情況就是再添加的時候節點是合并在了葉子節點上：
這個時候就需要右旋轉了，然後再做顔色翻轉即可。但是做了顔色翻轉之後需要以目前紅色的根節點做向上的判斷，因為根節點變成了紅色，可能會出現兩個連續紅色節點的情況，因為紅色節點的葉子節點一定要黑色。這種情況其實對應的就是添加之後節點分裂的情況。上面第一種情況也是需要分裂，但是不一樣的是添加的順序不一樣導緻了分裂不一樣。還有一種情況就是插入了左節點的右子樹，這種情況也是融合，但是處理方式有所不一樣。事實上用2-3-4樹來了解也是可以的。
再回到上面的幾個規則，如果一個根節點是黑色，葉子節點一定是紅色，這是因為隻有紅色才代表了融合，這個時候就是一個三節點了。最後一個經過同等數量的黑色節點，其實就是經過了2-3樹的節點，因為二三樹是絕對平衡的，是以紅黑樹也有這個性質。至于為什麼每一次添加都是紅色節點，是因為2-3樹永遠不會添加到空節點，會産生融合，是以添加紅色節點代表融合。
添加的時候，添加的節點将是紅色的，從2-3樹的角度來了解，因為加入的葉子節點是不能插入到空節點的，是以自然是紅色代表融合了。從紅黑樹本身的增删功能來看，添加紅色是最保險的方法，因為紅黑樹是看黑色節點的數量來保持平衡的，直接添加黑色一定會導緻不平衡，因為會有一條路多了一個黑色，本來是平衡的，加了一個另外的勢必不平衡。是以設定成紅色是影響最小的。
紅黑樹的修正手段也就幾種，首先就是改變顔色了，然後就是執行旋轉操作。
旋轉其實也很容易了解，左旋轉的時候，beta這個節點接上了x沒有位置放了，是以隻能接在x上，右旋轉也是一樣的意思。是以紅黑樹的插入算法就需要做出改變，插入的時候前面的步驟是一樣的，從根節點向下查找要插入父節點的位置，插入節點之後，後面就需要添加檢測樹的操作，檢測這個樹是否是紅黑樹了，如果不是，那麼就要進行修正。
添加修正的情況有三種，其實對應的就是上面提到的三個情況了：
①插入的是根節點，那麼直接就可以把目前節點變成黑色了，對照規則一，根節點為黑色。同時在2-3樹中黑色代表單個節點，這是自然的了。
②父節點是黑色，這種情況下是沒有違反任何規則，完美度過。
③當父節點是紅色，叔叔節點也是紅色的時候，就需要處理了，添加的節點本身就是紅色，父親又是紅色，這就違反了性質4。由于是連續的兩個黑色，那麼隻需要把父節點設定成黑色就好了，但是設定黑色會違反性質5，是以是行不通的。
左邊紅色的點就是插入的。這裡要注意的是，祖父節點一定是黑色，紅色不可能，紅色節點葉子節點一定是黑色。當把父親節點設定成黑色之後，問題來了，插入節點這邊多了一個黑色，是以把叔叔節點也設定成黑色，這樣的話這整一個分支就變多了一個黑色節點了。是以把祖父節點變成紅色即可：
其實上面的步驟是可以看做是一個2-3樹的分裂添加過程，一開始可以看到祖父節點的兩個節點是紅色，是以祖父是一個三節點，暫時的三節點，還沒有分裂而已，再添加一個的時候需要分裂，是以分出來的那兩個節點是黑色，2-3樹分裂的時候如果不是根節點是要和上頭合并的，是以祖父節點就是紅色了，插入就正常插入到葉子節點合并。在這裡不一定是看成是2-3樹，看成2-3-4樹也是可以的。
④當父節點是紅色，叔叔節點為黑色，插入的節點是父節點的左孩子。
違反了4的規則，如果把左邊的一個節點變成黑色就可以了，但是這樣右違反了5，是以需要祖父的兩個分支增加一個黑色的，祖父節點變成紅色的來處理，可以把父節點變成黑色，祖父節點變成紅色，右旋轉即可。這個情況其實就是剛剛2-3樹模拟的時候的第二種情況了，分裂的時候。
⑤當父節點是紅色色，叔叔節點是黑色，插入為右孩子。
這個情況和上面的情況很相似，左旋轉就回到了上面的情況，按照上面情況處理即可。
總的來說，就是對應着2-3樹的分裂過程，隻不過對應的結構不同可能有所差異。
這個操作，有有點複雜了。
①删除的就是本身的根節點，而且根節點左右子樹是空的。直接删就好了，沒有上面好講的。
②如果删除的節點是紅色的，那麼它的父親節點就一定是黑色的。因為是紅色的，直接拿孩子節點補充就好了，因為是沒有影響的。
③如果删除節點是黑色的，而且兄弟節點是紅色的，兄弟節點的孩子節點是黑色，删除節點的父親節點也是黑色的。
互換兄弟節點和父節點的顔色，然後對父節點做左旋轉。這樣還沒結束，這樣的結果就可以使得變成下面的情況處理了，，這個時候左子樹就可以作為5處理了。
④如果删除節點是黑色，父節點和兄弟節點以及兄弟節點的孩子都是黑色。
左邊少了一個黑色的節點，那麼就需要右邊也少一個，是以把兄弟節點變成紅色即可。這個時候這整一顆樹就都少一個黑色節點了，問題是，這整一顆樹有可能隻是一小部分，是以還需要回到情況1讨論，這裡處理之後回到情況1判斷。
⑤删除的節點為黑色，父親節點為紅色，兄弟節點和兄弟節點的孩子為黑色
這個情況下就隻需要互換顔色即可，左邊少了一個黑色節點，這個時候隻需要把父節點和兄弟節點交換即可，因為因為交換之後兩個子樹都會經過這個父節點，而整個子樹黑色高度沒有變化。這個情況就是真正完成的。
⑥删除的節點是黑色，兄弟節點也是黑色，兄弟孩子的左節點是紅色，兄弟節點的右子樹為黑色，父親節點随便顔色。
這個時候就要對兄弟節點做右旋轉,然後對調兄弟節點和兄弟左孩子節點,那麼情況就轉移到情況7處理了。
⑦删除的節點是黑色，兄弟節點也是黑色，兄弟節點的右孩子為紅色，父親節點和兄弟節點左孩子随便顔色。
這種情況下，先互換父節點和兄弟節點的顔色，再對父節點進行左旋轉操作，那麼左邊，也就是删除了節點的這邊删除前和删除後是沒有變化的，有變化的主要是右邊。
圖錯了，兄弟節點的右子樹是紅色，我懶的改了。
上圖所訓示的标簽都是根據原樹結構标注。沒有經過父節點孩子的右兩條路，一條是左子樹-》右，一條是-》右。左子樹那條是兄弟節點-》父節點-》兄弟節點的孩子節點，這是更新之後的，沒有更新之前的是右子樹-》左子樹，也就是父節點-》兄弟節點，-》兄弟·節點孩子節點，可以看到隻是換了一個順序而已，既然之前是平衡樹，換個順序肯定黑色節點的數量不會變吧，況且隻是交換了顔色而已。
那麼隻是有一條路要跟新了，也就是經過兄弟節點的右子樹那條，紅色那條。之前是經過了父節點-》兄弟節點-》兄弟節點的右節點，現在隻是經過了兄弟節點和右節點，明顯是少了一個黑色節點，很顯然，該黑色就OK了，是以上圖是最終改完的結果，之是以說錯了隻是還沒到說到那一步。
要注意的是，在很多的部落格文章中，删除情況有所差別，有五種的也有四種的，這裡是五種的，四種的是因為把第四和第五中情況和起來了。四種的話應該是這麼寫，兄弟節點和孩子全是黑色，把兄弟節點變成紅色，目前節點切換到父節點重新向上判斷。這裡隻是把父節點分開了。本質是完全一樣的。
紅黑樹的實作
代碼不太好，實作起來有點複雜，哎！
private class Node<T extends Comparable<T>> {
public boolean color;
public T key;
Node<T> left;
Node<T> right;
Node<T> parent;
public Node(T key, boolean color, Node<T> parent, Node<T> left, Node<T> right) {
this.key = key;
this.color = color;
this.parent = parent;
this.left = left;
this.right = right;
}
public T getKey() {
return key;
}
@Override
public String toString() {
String s = "" + key + (this.color == RED ? "R" : "B");
if (this.left != null) {
s += (" " + left.key);
}
if (this.right != null) {
s += (" " + right.key);
}
return s;
}
}
由于帶上了父母節點，用遞歸實作帶父母節點的維護，就有點難度了。
首先添加操作的更新，添加操作使用的是疊代實作，篇幅較大，不貼了。
private void insertFixUp(Node<T> node) {
Node<T> parent, grandParent;
while ((parent = parentOf(node)) != null && isRed(parent)) {
grandParent = parentOf(parent);
if (parent == grandParent.left) {
//third condition,the uncle is red
Node<T> uncle = grandParent.right;
if (uncle != null && isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(grandParent);
node = grandParent;
continue;
}
//fifth condition,the uncle is black and left child of the current node
if (parent.right == node) {
Node<T> temp;
leftRotate(parent);
temp = parent;
parent = node;
node = temp;
}
//fourth condiction,same as above but the right child of the current node.
setBlack(parent);
setRed(grandParent);
rightRotate(grandParent);
} else {
//third condition,the uncle is red.
Node<T> uncle = grandParent.left;
if (uncle != null && isRed(uncle)) {
setBlack(uncle);
setBlack(parent);
setRed(grandParent);
node = grandParent;
continue;
}
//fifth condition,the uncle is black,left child
if (parent.left == node) {
Node<T> temp;
rightRotate(parent);
temp = parent;
parent = node;
node = temp;
}
//fourth condition,the uncle is black,right child
setBlack(parent);
setRed(grandParent);
leftRotate(grandParent);
}
}
setBlack(root);
}
每一次處理完一種情況之後要記得更新目前節點node的資訊，因為處理完後不一定就結束了，可能是更新到了一種新的情況。
删除操作的更新，這個有點複雜。
private void removeFixUp(Node<T> node, Node<T> par) {
Node<T> uncle;
Node<T> parent;
parent = node == null ? par : node.parent;
while ((node == null || isBlack(node)) && node != root) {
if (parent.left == node) {
uncle = parent.right;
//the uncle is red, condition three
if (isRed(uncle)) {
setBlack(uncle);
setRed(parent);
leftRotate(parent);
uncle = parent.right;
}
//the uncle and his child are all black
if ((uncle.left == null || isBlack(uncle.left)) &&
(uncle.right == null || isBlack(uncle.right))) {
setRed(uncle);
node = parent;
parent = parentOf(node);
} else {
//the uncle is black and red of his child on the left
if (uncle.right == null || isBlack(uncle.right)) {
setBlack(uncle.left);
setRed(uncle);
rightRotate(uncle);
uncle = parent.right;
}
setColor(uncle, colorOf(parent));
setBlack(parent);
setBlack(uncle.right);
leftRotate(parent);
node = this.root;
break;
}
} else {
uncle = parent.left;
if (isRed(uncle)) {
setBlack(uncle);
setRed(parent);
rightRotate(parent);
uncle = parent.left;
}
if ((uncle.left == null || isBlack(uncle.left)) &&
(uncle.right == null || isBlack(uncle.right))) {
setRed(uncle);
node = parent;
parent = parentOf(node);
} else {
if (uncle.left == null || isBlack(uncle.left)) {
setBlack(uncle.right);
setRed(uncle);
leftRotate(uncle);
uncle = parent.left;
}
setColor(uncle, colorOf(parent));
setBlack(parent);
setBlack(uncle.left);
rightRotate(parent);
node = this.root;
break;
}
}
}
if (node != null) {
setBlack(node);
}
}
每次處理完後也要記得更新節點的資訊，第一種情況更新完的時候，uncle節點不再是原來的了，是以要進行更新。第二種情況也是，由于處理節點已經切換到了父親節點，于是要對父親節點切換，第三種情況uncle節點也發生了改變，同樣要切換。第四種情況直接結束。
最後附上GitHub及其代碼： https://github.com/GreenArrow2017/DataStructure_Java/tree/master/out/production/DataStructure_Java/Tree