刪除元素

刪除元素本身比較簡單，就是采用二叉樹的刪除規(guī)則。

• 如果刪除的位置有兩個葉子節(jié)點，則從其右子樹中取最小的元素放到刪除的位置，然后把刪除位置移到替代元素的位置，進入下一步。
• 如果刪除的位置只有一個葉子節(jié)點（有可能是經(jīng)過第一步轉(zhuǎn)換后的刪除位置），則把那個葉子節(jié)點作為替代元素，放到刪除的位置，然后把這個葉子節(jié)點刪除。
• 如果刪除的位置沒有葉子節(jié)點，則直接把這個刪除位置的元素刪除即可。
• 針對紅黑樹，如果刪除位置是黑色節(jié)點，還需要做再平衡。
• 如果有替代元素，則以替代元素作為當前節(jié)點進入再平衡。
• 如果沒有替代元素，則以刪除的位置的元素作為當前節(jié)點進入再平衡，平衡之后再刪除這個節(jié)點。

1. public V remove(Object key) {
2. // 獲取節(jié)點
3. Entry<K,V> p = getEntry(key);
4. if (p == null)
5. return null;
6. V oldValue = p.value;
7. // 刪除節(jié)點
8. deleteEntry(p);
9. // 返回刪除的value
10. return oldValue;
11. }
12. private void deleteEntry(Entry<K,V> p) {
13. // 修改次數(shù)加1
14. modCount++;
15. // 元素個數(shù)減1
16. size--;
17. if (p.left != null && p.right != null) {
18. // 如果當前節(jié)點既有左子節(jié)點，又有右子節(jié)點
19. // 取其右子樹中最小的節(jié)點
20. Entry<K,V> s = successor(p);
21. // 用右子樹中最小節(jié)點的值替換當前節(jié)點的值
22. p.key = s.key;
23. p.value = s.value;
24. // 把右子樹中最小節(jié)點設(shè)為當前節(jié)點
25. p = s;
26. // 這種情況實際上并沒有刪除p節(jié)點，而是把p節(jié)點的值改了，實際刪除的是p的后繼節(jié)點
27. }
28. // 如果原來的當前節(jié)點（p）有2個子節(jié)點，則當前節(jié)點已經(jīng)變成原來p的右子樹中的最小節(jié)點了，也就是說其沒有左子節(jié)點了
29. // 到這一步，p肯定只有一個子節(jié)點了
30. // 如果當前節(jié)點有子節(jié)點，則用子節(jié)點替換當前節(jié)點
31. Entry<K,V> replacement = (p.left != null ? p.left : p.right);
32. if (replacement != null) {
33. // 把替換節(jié)點直接放到當前節(jié)點的位置上（相當于刪除了p，并把替換節(jié)點移動過來了）
34. replacement.parent = p.parent;
35. if (p.parent == null)
36. root = replacement;
37. else if (p == p.parent.left)
38. p.parent.left = replacement;
39. else
40. p.parent.right = replacement;
41. // 將p的各項屬性都設(shè)為空
42. p.left = p.right = p.parent = null;
43. // 如果p是黑節(jié)點，則需要再平衡
44. if (p.color == BLACK)
45. fixAfterDeletion(replacement);
46. } else if (p.parent == null) {
47. // 如果當前節(jié)點就是根節(jié)點，則直接將根節(jié)點設(shè)為空即可
48. root = null;
49. } else {
50. // 如果當前節(jié)點沒有子節(jié)點且其為黑節(jié)點，則把自己當作虛擬的替換節(jié)點進行再平衡
51. if (p.color == BLACK)
52. fixAfterDeletion(p);
53. // 平衡完成后刪除當前節(jié)點（與父節(jié)點斷絕關(guān)系）
54. if (p.parent != null) {
55. if (p == p.parent.left)
56. p.parent.left = null;
57. else if (p == p.parent.right)
58. p.parent.right = null;
59. p.parent = null;
60. }
61. }
62. }

刪除再平衡

經(jīng)過上面的處理，真正刪除的肯定是黑色節(jié)點才會進入到再平衡階段。

因為刪除的是黑色節(jié)點，導(dǎo)致整顆樹不平衡了，所以這里我們假設(shè)把刪除的黑色賦予當前節(jié)點，這樣當前節(jié)點除了它自已的顏色還多了一個黑色，那么：

（1）如果當前節(jié)點是根節(jié)點，則直接涂黑即可，不需要再平衡；

（2）如果當前節(jié)點是紅+黑節(jié)點，則直接涂黑即可，不需要平衡；

（3）如果當前節(jié)點是黑+黑節(jié)點，則我們只要通過旋轉(zhuǎn)把這個多出來的黑色不斷的向上傳遞到一個紅色節(jié)點即可，這又可能會出現(xiàn)以下四種情況：

（假設(shè)當前節(jié)點為父節(jié)點的左子節(jié)點）

（假設(shè)當前節(jié)點為父節(jié)點的右子節(jié)點，正好反過來）

讓我們來看看TreeMap中的實現(xiàn)：

1. /**
2. * 刪除再平衡
3. *（1）每個節(jié)點或者是黑色，或者是紅色。
4. *（2）根節(jié)點是黑色。
5. *（3）每個葉子節(jié)點（NIL）是黑色。（注意：這里葉子節(jié)點，是指為空(NIL或NULL)的葉子節(jié)點?。?/span>
6. *（4）如果一個節(jié)點是紅色的，則它的子節(jié)點必須是黑色的。
7. *（5）從一個節(jié)點到該節(jié)點的子孫節(jié)點的所有路徑上包含相同數(shù)目的黑節(jié)點。
8. */
9. private void fixAfterDeletion(Entry<K,V> x) {
10. // 只有當前節(jié)點不是根節(jié)點且當前節(jié)點是黑色時才進入循環(huán)
11. while (x != root && colorOf(x) == BLACK) {
12. if (x == leftOf(parentOf(x))) {
13. // 如果當前節(jié)點是其父節(jié)點的左子節(jié)點
14. // sib是當前節(jié)點的兄弟節(jié)點
15. Entry<K,V> sib = rightOf(parentOf(x));
16. // 情況1）如果兄弟節(jié)點是紅色
17. if (colorOf(sib) == RED) {
18. // （1）將兄弟節(jié)點設(shè)為黑色
19. setColor(sib, BLACK);
20. // （2）將父節(jié)點設(shè)為紅色
21. setColor(parentOf(x), RED);
22. // （3）以父節(jié)點為支點進行左旋
23. rotateLeft(parentOf(x));
24. // （4）重新設(shè)置x的兄弟節(jié)點，進入下一步
25. sib = rightOf(parentOf(x));
26. }
27. if (colorOf(leftOf(sib)) == BLACK &&
28. colorOf(rightOf(sib)) == BLACK) {
29. // 情況2）如果兄弟節(jié)點的兩個子節(jié)點都是黑色
30. // （1）將兄弟節(jié)點設(shè)置為紅色
31. setColor(sib, RED);
32. // （2）將x的父節(jié)點作為新的當前節(jié)點，進入下一次循環(huán)
33. x = parentOf(x);
34. } else {
35. if (colorOf(rightOf(sib)) == BLACK) {
36. // 情況3）如果兄弟節(jié)點的右子節(jié)點為黑色
37. // （1）將兄弟節(jié)點的左子節(jié)點設(shè)為黑色
38. setColor(leftOf(sib), BLACK);
39. // （2）將兄弟節(jié)點設(shè)為紅色
40. setColor(sib, RED);
41. // （3）以兄弟節(jié)點為支點進行右旋
42. rotateRight(sib);
43. // （4）重新設(shè)置x的兄弟節(jié)點
44. sib = rightOf(parentOf(x));
45. }
46. // 情況4）
47. // （1）將兄弟節(jié)點的顏色設(shè)為父節(jié)點的顏色
48. setColor(sib, colorOf(parentOf(x)));
49. // （2）將父節(jié)點設(shè)為黑色
50. setColor(parentOf(x), BLACK);
51. // （3）將兄弟節(jié)點的右子節(jié)點設(shè)為黑色
52. setColor(rightOf(sib), BLACK);
53. // （4）以父節(jié)點為支點進行左旋
54. rotateLeft(parentOf(x));
55. // （5）將root作為新的當前節(jié)點（退出循環(huán)）
56. x = root;
57. }
58. } else { // symmetric
59. // 如果當前節(jié)點是其父節(jié)點的右子節(jié)點
60. // sib是當前節(jié)點的兄弟節(jié)點
61. Entry<K,V> sib = leftOf(parentOf(x));
62. // 情況1）如果兄弟節(jié)點是紅色
63. if (colorOf(sib) == RED) {
64. // （1）將兄弟節(jié)點設(shè)為黑色
65. setColor(sib, BLACK);
66. // （2）將父節(jié)點設(shè)為紅色
67. setColor(parentOf(x), RED);
68. // （3）以父節(jié)點為支點進行右旋
69. rotateRight(parentOf(x));
70. // （4）重新設(shè)置x的兄弟節(jié)點
71. sib = leftOf(parentOf(x));
72. }
73. if (colorOf(rightOf(sib)) == BLACK &&
74. colorOf(leftOf(sib)) == BLACK) {
75. // 情況2）如果兄弟節(jié)點的兩個子節(jié)點都是黑色
76. // （1）將兄弟節(jié)點設(shè)置為紅色
77. setColor(sib, RED);
78. // （2）將x的父節(jié)點作為新的當前節(jié)點，進入下一次循環(huán)
79. x = parentOf(x);
80. } else {
81. if (colorOf(leftOf(sib)) == BLACK) {
82. // 情況3）如果兄弟節(jié)點的左子節(jié)點為黑色
83. // （1）將兄弟節(jié)點的右子節(jié)點設(shè)為黑色
84. setColor(rightOf(sib), BLACK);
85. // （2）將兄弟節(jié)點設(shè)為紅色
86. setColor(sib, RED);
87. // （3）以兄弟節(jié)點為支點進行左旋
88. rotateLeft(sib);
89. // （4）重新設(shè)置x的兄弟節(jié)點
90. sib = leftOf(parentOf(x));
91. }
92. // 情況4）
93. // （1）將兄弟節(jié)點的顏色設(shè)為父節(jié)點的顏色
94. setColor(sib, colorOf(parentOf(x)));
95. // （2）將父節(jié)點設(shè)為黑色
96. setColor(parentOf(x), BLACK);
97. // （3）將兄弟節(jié)點的左子節(jié)點設(shè)為黑色
98. setColor(leftOf(sib), BLACK);
99. // （4）以父節(jié)點為支點進行右旋
100. rotateRight(parentOf(x));
101. // （5）將root作為新的當前節(jié)點（退出循環(huán)）
102. x = root;
103. }
104. }
105. }
106. // 退出條件為多出來的黑色向上傳遞到了根節(jié)點或者紅節(jié)點
107. // 則將x設(shè)為黑色即可滿足紅黑樹規(guī)則
108. setColor(x, BLACK);
109. }

刪除元素舉例

假設(shè)我們有下面這樣一顆紅黑樹。

我們刪除6號元素，則從右子樹中找到了最小元素7，7又沒有子節(jié)點了，所以把7作為當前節(jié)點進行再平衡。

我們看到7是黑節(jié)點，且其兄弟為黑節(jié)點，且其兄弟的兩個子節(jié)點都是紅色，滿足情況4），平衡之后如下圖所示。

我們再刪除7號元素，則從右子樹中找到了最小元素8，8有子節(jié)點且為黑色，所以8的子節(jié)點9是替代節(jié)點，以9為當前節(jié)點進行再平衡。

我們發(fā)現(xiàn)9是紅節(jié)點，則直接把它涂成黑色即滿足了紅黑樹的特性，不需要再過多的平衡了。

這次我們來個狠的，把根節(jié)點刪除，從右子樹中找到了最小的元素5，5沒有子節(jié)點，所以把5作為當前節(jié)點進行再平衡。

我們看到5是黑節(jié)點，且其兄弟為紅色，符合情況1），平衡之后如下圖所示，然后進入情況2）。

對情況2）進行再平衡后如下圖所示。

然后進入下一次循環(huán)，發(fā)現(xiàn)不符合循環(huán)條件了，直接把x涂為黑色即可，退出這個方法之后會把舊x刪除掉（見deleteEntry()方法），最后的結(jié)果就是下面這樣。

二叉樹的遍歷

我們知道二叉查找樹的遍歷有前序遍歷、中序遍歷、后序遍歷。

（1）前序遍歷，先遍歷我，再遍歷我的左子節(jié)點，最后遍歷我的右子節(jié)點；

（2）中序遍歷，先遍歷我的左子節(jié)點，再遍歷我，最后遍歷我的右子節(jié)點；

（3）后序遍歷，先遍歷我的左子節(jié)點，再遍歷我的右子節(jié)點，最后遍歷我；

這里的前中后都是以“我”的順序為準的，我在前就是前序遍歷，我在中就是中序遍歷，我在后就是后序遍歷。

下面讓我們看看經(jīng)典的中序遍歷是怎么實現(xiàn)的：

1. public class TreeMapTest {
2. public static void main(String[] args) {
3. // 構(gòu)建一顆10個元素的樹
4. TreeNode<Integer> node = new TreeNode<>(1, null).insert(2)
5. .insert(6).insert(3).insert(5).insert(9)
6. .insert(7).insert(8).insert(4).insert(10);
7. // 中序遍歷，打印結(jié)果為1到10的順序
8. node.root().inOrderTraverse();
9. }
10. }
11. /**
12. * 樹節(jié)點，假設(shè)不存在重復(fù)元素
13. * @param <T>
14. */
15. class TreeNode<T extends Comparable<T>> {
16. T value;
17. TreeNode<T> parent;
18. TreeNode<T> left, right;
19. public TreeNode(T value, TreeNode<T> parent) {
20. this.value = value;
21. this.parent = parent;
22. }
23. /**
24. * 獲取根節(jié)點
25. */
26. TreeNode<T> root() {
27. TreeNode<T> cur = this;
28. while (cur.parent != null) {
29. cur = cur.parent;
30. }
31. return cur;
32. }
33. /**
34. * 中序遍歷
35. */
36. void inOrderTraverse() {
37. if(this.left != null) this.left.inOrderTraverse();
38. System.out.println(this.value);
39. if(this.right != null) this.right.inOrderTraverse();
40. }
41. /**
42. * 經(jīng)典的二叉樹插入元素的方法
43. */
44. TreeNode<T> insert(T value) {
45. // 先找根元素
46. TreeNode<T> cur = root();
47. TreeNode<T> p;
48. int dir;
49. // 尋找元素應(yīng)該插入的位置
50. do {
51. p = cur;
52. if ((dir=value.compareTo(p.value)) < 0) {
53. cur = cur.left;
54. } else {
55. cur = cur.right;
56. }
57. } while (cur != null);
58. // 把元素放到找到的位置
59. if (dir < 0) {
60. p.left = new TreeNode<>(value, p);
61. return p.left;
62. } else {
63. p.right = new TreeNode<>(value, p);
64. return p.right;
65. }
66. }
67. }

TreeMap的遍歷

從上面二叉樹的遍歷我們很明顯地看到，它是通過遞歸的方式實現(xiàn)的，但是遞歸會占用額外的空間，直接到線程棧整個釋放掉才會把方法中申請的變量銷毀掉，所以當元素特別多的時候是一件很危險的事。

（上面的例子中，沒有申請額外的空間，如果有聲明變量，則可以理解為直到方法完成才會銷毀變量）

那么，有沒有什么方法不用遞歸呢？

讓我們來看看java中的實現(xiàn)：

1. @Override
2. public void forEach(BiConsumer<? super K, ? super V> action) {
3. Objects.requireNonNull(action);
4. // 遍歷前的修改次數(shù)
5. int expectedModCount = modCount;
6. // 執(zhí)行遍歷，先獲取第一個元素的位置，再循環(huán)遍歷后繼節(jié)點
7. for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e)) {
8. // 執(zhí)行動作
9. action.accept(e.key, e.value);
10. // 如果發(fā)現(xiàn)修改次數(shù)變了，則拋出異常
11. if (expectedModCount != modCount) {
12. throw new ConcurrentModificationException();
13. }
14. }
15. }

是不是很簡單？！

（1）尋找第一個節(jié)點；

從根節(jié)點開始找最左邊的節(jié)點，即最小的元素。

1. final Entry<K,V> getFirstEntry() {
2. Entry<K,V> p = root;
3. // 從根節(jié)點開始找最左邊的節(jié)點，即最小的元素
4. if (p != null)
5. while (p.left != null)
6. p = p.left;
7. return p;
8. }

（2）循環(huán)遍歷后繼節(jié)點；

尋找后繼節(jié)點這個方法我們在刪除元素的時候也用到過，當時的場景是有右子樹，則從其右子樹中尋找最小的節(jié)點。

1. static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
2. if (t == null)
3. // 如果當前節(jié)點為空，返回空
4. return null;
5. else if (t.right != null) {
6. // 如果當前節(jié)點有右子樹，取右子樹中最小的節(jié)點
7. Entry<K,V> p = t.right;
8. while (p.left != null)
9. p = p.left;
10. return p;
11. } else {
12. // 如果當前節(jié)點沒有右子樹
13. // 如果當前節(jié)點是父節(jié)點的左子節(jié)點，直接返回父節(jié)點
14. // 如果當前節(jié)點是父節(jié)點的右子節(jié)點，一直往上找，直到找到一個祖先節(jié)點是其父節(jié)點的左子節(jié)點為止，返回這個祖先節(jié)點的父節(jié)點
15. Entry<K,V> p = t.parent;
16. Entry<K,V> ch = t;
17. while (p != null && ch == p.right) {
18. ch = p;
19. p = p.parent;
20. }
21. return p;
22. }
23. }

讓我們一起來分析下這種方式的時間復(fù)雜度吧。

首先，尋找第一個元素，因為紅黑樹是接近平衡的二叉樹，所以找最小的節(jié)點，相當于是從頂?shù)降琢?，時間復(fù)雜度為O(log n)；

其次，尋找后繼節(jié)點，因為紅黑樹插入元素的時候會自動平衡，最壞的情況就是尋找右子樹中最小的節(jié)點，時間復(fù)雜度為O(log k)，k為右子樹元素個數(shù)；

最后，需要遍歷所有元素，時間復(fù)雜度為O(n)；

所以，總的時間復(fù)雜度為 O(log n) + O(n * log k) ≈ O(n)。

雖然遍歷紅黑樹的時間復(fù)雜度是O(n)，但是它實際是要比跳表要慢一點的，啥？跳表是啥？安心，后面會講到跳表的。

總結(jié)

到這里紅黑樹就整個講完了，讓我們再回顧下紅黑樹的特性：

• 每個節(jié)點或者是黑色，或者是紅色。
• 根節(jié)點是黑色。
• 每個葉子節(jié)點（NIL）是黑色。（注意：這里葉子節(jié)點，是指為空(NIL或NULL)的葉子節(jié)點！）
• 如果一個節(jié)點是紅色的，則它的子節(jié)點必須是黑色的。
• 從一個節(jié)點到該節(jié)點的子孫節(jié)點的所有路徑上包含相同數(shù)目的黑節(jié)點。

除了上述這些標準的紅黑樹的特性，你還能講出來哪些TreeMap的特性呢？

• TreeMap的存儲結(jié)構(gòu)只有一顆紅黑樹；
• TreeMap中的元素是有序的，按key的順序排列；
• TreeMap比HashMap要慢一些，因為HashMap前面還做了一層桶，尋找元素要快很多；
• TreeMap沒有擴容的概念；
• TreeMap的遍歷不是采用傳統(tǒng)的遞歸式遍歷；
• TreeMap可以按范圍查找元素，查找最近的元素；

總結(jié)

本篇文章就到這里了，希望能給你帶來幫助，也希望您能夠多多關(guān)注我們的更多內(nèi)容！

原文鏈接：https://csp1999.blog.csdn.net/article/details/112514930