紅黑樹(shù)
紅黑樹(shù)是一種數(shù)據(jù)結(jié)構(gòu)與算法課堂上常常提到但又不會(huì)細(xì)講的樹(shù)，也是技術(shù)面試中經(jīng)常被問(wèn)到的樹(shù)，然而無(wú)論是書(shū)上還是網(wǎng)上的資料，通常都比較刻板難以理解，能不能一種比較直觀的方式來(lái)理解紅黑樹(shù)呢？本文將以圖形的方式來(lái)解釋紅黑樹(shù)的插入與刪除操作。
對(duì)樹(shù)結(jié)構(gòu)的學(xué)習(xí)是一個(gè)遞進(jìn)的過(guò)程，我們通常所接觸的樹(shù)都是二叉樹(shù)，二叉樹(shù)簡(jiǎn)單來(lái)說(shuō)就是每個(gè)非葉子節(jié)點(diǎn)都有且只有兩個(gè)孩子，分別叫做左孩子和右孩子。二叉樹(shù)中有一類(lèi)特殊的樹(shù)叫二叉查找樹(shù)，二叉查找樹(shù)是一種有序的樹(shù)，對(duì)于每個(gè)非葉子節(jié)點(diǎn)，其左子樹(shù)的值都小于它，其右子樹(shù)的值都大于它。比二叉查找樹(shù)更進(jìn)一步的是二叉平衡樹(shù)，二叉平衡樹(shù)除了保證有序外，還能夠保持每個(gè)節(jié)點(diǎn)左右子樹(shù)的高度相差不超過(guò)1。常見(jiàn)的平衡樹(shù)有AVL樹(shù)，Treap，紅黑樹(shù)，伸展樹(shù)，等等。
紅黑樹(shù)是一種二叉查找樹(shù)，但在每個(gè)節(jié)點(diǎn)上增加一個(gè)存儲(chǔ)位表示節(jié)點(diǎn)的顏色，可以是RED或BLACK。通過(guò)對(duì)任何一條從根到葉子的路徑上各個(gè)節(jié)點(diǎn)著色方式的限制，紅黑樹(shù)確保沒(méi)有一條路徑會(huì)比其他路徑長(zhǎng)出兩倍，因而是接近平衡的。
紅黑樹(shù)滿足一下5個(gè)性質(zhì)：
- 每個(gè)節(jié)點(diǎn)是紅色或者黑色；
- 根節(jié)點(diǎn)是黑色；
- 每個(gè)葉子節(jié)點(diǎn)NIL是黑色；
- 如果一個(gè)節(jié)點(diǎn)是紅色，則它的兩個(gè)孩子都是黑色；（每條路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)）
- 任一節(jié)點(diǎn)到其所有子孫葉子節(jié)點(diǎn)NIL的路徑上包含相同數(shù)目的黑色節(jié)點(diǎn)。
注意，在紅黑樹(shù)中，把傳統(tǒng)二叉樹(shù)的葉子節(jié)點(diǎn)的孩子指向NIL，稱(chēng)NIL為紅黑樹(shù)中的葉子節(jié)點(diǎn)。NIL節(jié)點(diǎn)中含有指向父節(jié)點(diǎn)的指針，這可能是需要把null改為NIL的原因。
一、插入操作
首先以二叉查找樹(shù)的插入方式（插入的新節(jié)點(diǎn)都在葉子節(jié)點(diǎn)處）插入新的節(jié)點(diǎn)，并將其繪為紅色。然后再重繪其顏色或旋轉(zhuǎn)以保持紅黑樹(shù)的性質(zhì)，調(diào)整分為以下三種情況：
1 新節(jié)點(diǎn)N沒(méi)有父節(jié)點(diǎn)（即位于根上）
將新節(jié)點(diǎn)N繪為黑色。
2 新節(jié)點(diǎn)N的父節(jié)點(diǎn)P為黑色
不用調(diào)整。
3 新節(jié)點(diǎn)N的父節(jié)點(diǎn)P為紅色
因?yàn)榧t黑樹(shù)不允許有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)（性質(zhì)4），所以需要調(diào)整，根據(jù)N的叔父節(jié)點(diǎn)顏色分為兩種情況：（我們以 N的父節(jié)點(diǎn)P為左孩子為例，P為右孩子的情況類(lèi)似，不再詳述）
3.1 新節(jié)點(diǎn)N的叔父節(jié)點(diǎn)U為紅色
將新節(jié)點(diǎn)N的父節(jié)點(diǎn)P和叔父節(jié)點(diǎn)U都繪為黑色，將其祖父節(jié)點(diǎn)G繪為紅色，這樣保證從G到每個(gè)null節(jié)點(diǎn)的路徑上所包含的黑色節(jié)點(diǎn)個(gè)數(shù)與原來(lái)保持一致。但由于我們把G變成了紅色，如果G的父親也是紅色，就可能導(dǎo)致連續(xù)兩個(gè)紅色節(jié)點(diǎn)（違反性質(zhì)4），所以，需要重新檢查G是否違反了紅黑樹(shù)性質(zhì)。
3.2 新節(jié)點(diǎn)N的叔父節(jié)點(diǎn)U為黑色
若新節(jié)點(diǎn)N是其父節(jié)點(diǎn)P的左孩子：將其父節(jié)點(diǎn)P繪為黑色，祖父節(jié)點(diǎn)G繪為紅色，然后對(duì)G進(jìn)行一次右旋轉(zhuǎn)。
若新節(jié)點(diǎn)N是其父節(jié)點(diǎn)P的右孩子：對(duì)其父節(jié)點(diǎn)進(jìn)行一次左旋轉(zhuǎn)，問(wèn)題轉(zhuǎn)化為左孩子的情況。
二、刪除操作
《算法導(dǎo)論》和維基百科上的做法都是，當(dāng)刪除一個(gè)黑色節(jié)點(diǎn)D時(shí)，把D的黑色“下推”至其子節(jié)點(diǎn)C，也就是說(shuō)C除了本身的顏色外多了一重額外的黑色，然后不斷把這重額外的黑色沿樹(shù)上移，直到碰到一個(gè)紅色節(jié)點(diǎn)，把其變?yōu)楹谏员ＷC路徑上黑色節(jié)點(diǎn)數(shù)目不變，或者移到樹(shù)的根部，這樣所有路徑上的黑色節(jié)點(diǎn)數(shù)目都減一，保持相等。上移過(guò)程中可能需要旋轉(zhuǎn)和修改一些節(jié)點(diǎn)的顏色，以保證路徑上黑色節(jié)點(diǎn)數(shù)目不變。
這種做法可能有利于代碼的實(shí)現(xiàn)（可用迭代的方式），但卻不便于理解（個(gè)人認(rèn)為）。本著理解優(yōu)先的目的，我根據(jù)被刪除節(jié)點(diǎn)D的孩子是否為NIL做如下分類(lèi)：
1 被刪除節(jié)點(diǎn)D的兩個(gè)孩子都是NIL
1.1 被刪除節(jié)點(diǎn)D是紅色
用NIL替換D即可。
1.2 被刪除節(jié)點(diǎn)D是黑色（我們以D是左孩子為例）
1.2.1 被刪除節(jié)點(diǎn)D的兄弟節(jié)點(diǎn)B的兩個(gè)孩子都為NIL
將D的兄弟節(jié)點(diǎn)B繪為紅色，父節(jié)點(diǎn)P繪為黑色。
圖中半紅半黑表示該節(jié)點(diǎn)可能為紅色，也可能為黑色。如果P原來(lái)是紅色，這樣修改后路徑上的黑色節(jié)點(diǎn)數(shù)目和刪除D之前一樣；如果P原來(lái)是黑色，那么刪除D后會(huì)導(dǎo)致路徑上黑色節(jié)點(diǎn)的數(shù)目比刪除前少了一個(gè)，所以還需繼續(xù)檢查經(jīng)過(guò)P的路徑上黑色節(jié)點(diǎn)數(shù)目的改變是否影響了紅黑樹(shù)的性質(zhì)。
1.2.2 被刪除節(jié)點(diǎn)D的兄弟節(jié)點(diǎn)B有一個(gè)孩子不為NIL
這個(gè)孩子一定是紅色的，否則從D的父節(jié)點(diǎn)到各個(gè)葉子節(jié)點(diǎn)的路徑上黑色節(jié)點(diǎn)的數(shù)目就會(huì)不等（違反性質(zhì)5）。
若這個(gè)孩子為右孩子，將B的這個(gè)右孩子繪為黑色，B繪為其父節(jié)點(diǎn)P原來(lái)的顏色，P繪為黑色，然后對(duì)P進(jìn)行一次左旋轉(zhuǎn)。
若這個(gè)孩子為左孩子，將B的這個(gè)左孩子繪為黑色，B繪為紅色，然后對(duì)B進(jìn)行一次右旋轉(zhuǎn)，問(wèn)題轉(zhuǎn)化為右孩子的情況。
1.2.3 被刪除節(jié)點(diǎn)D的兄弟節(jié)點(diǎn)B的兩個(gè)孩子都不為NIL
若B為紅色，則B的兩個(gè)孩子一定為黑色。將B繪為黑色，B的左孩子繪為紅色，然后對(duì)P進(jìn)行一次左旋轉(zhuǎn)。
若B為黑色，則B的兩個(gè)孩子一定為紅色。將B的父節(jié)點(diǎn)P繪為黑色，B的右孩子繪為黑色，B繪為其父節(jié)點(diǎn)P原來(lái)的顏色，然后對(duì)P進(jìn)行一次左旋轉(zhuǎn)。
2 被刪除節(jié)點(diǎn)D的兩個(gè)孩子都不是NIL
按照二叉查找樹(shù)刪除節(jié)點(diǎn)的方法找到D的后繼節(jié)點(diǎn)S，交換D和S的內(nèi)容（顏色保持不變），被刪除節(jié)點(diǎn)變?yōu)镾，如果S有不為NIL的節(jié)點(diǎn)，那么繼續(xù)用S的后繼節(jié)點(diǎn)替換S，直到被刪除節(jié)點(diǎn)的兩個(gè)孩子都為NIL，問(wèn)題轉(zhuǎn)化為被刪除節(jié)點(diǎn)D的兩個(gè)孩子都為NIL的情況。
3 被刪除節(jié)點(diǎn)D有一個(gè)孩子不是NIL
這個(gè)孩子C一定是紅色節(jié)點(diǎn)，否則從D到各個(gè)NIL節(jié)點(diǎn)的路徑上的黑色節(jié)點(diǎn)數(shù)目就會(huì)不同（違反性質(zhì)5）。
交換D和C的內(nèi)容（顏色保持不變），被刪除節(jié)點(diǎn)變?yōu)镃，問(wèn)題轉(zhuǎn)化為被刪除節(jié)點(diǎn)D的兩個(gè)孩子都為NIL的情況。
二叉樹(shù)的遍歷
二叉樹(shù)的遍歷有三種：前序遍歷、中序遍歷和后序遍歷。每種遍歷的實(shí)現(xiàn)又有遞歸和迭代兩種，這篇文章我們來(lái)討論如何用比較優(yōu)雅的代碼來(lái)實(shí)現(xiàn)二叉樹(shù)的遍歷。
首先我來(lái)定義一個(gè)二叉樹(shù)的節(jié)點(diǎn)：
|
1
2
3
4
5
6
7
8
9
|
public class TreeNode { int val; TreeNode left; TreeNode right; public TreeNode(int x) { val = x; }} |
一、前序遍歷（Preorder Traversal）
簡(jiǎn)單來(lái)講，前序遍歷就是先訪問(wèn)父節(jié)點(diǎn)，再訪問(wèn)左孩子，最后訪問(wèn)右孩子，即以父、左、右的順序來(lái)遍歷。
遞歸實(shí)現(xiàn)非常簡(jiǎn)單，代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
public class Solution { List<Integer> result = new ArrayList<Integer>(); public List<Integer> preorderTraversal(TreeNode root) { dfs(root); return result; } private void dfs(TreeNode root) { if (root == null) { return; } result.add(root.val); dfs(root.left); dfs(root.right); }} |
迭代實(shí)現(xiàn)需要借助一個(gè)棧，存儲(chǔ)沒(méi)被訪問(wèn)的右節(jié)點(diǎn)，代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
public class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<Integer>(); if (root == null) { return result; } Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(root); while (!stack.isEmpty()) { TreeNode curr = stack.pop(); result.add(curr.val); if (curr.right != null) { stack.push(curr.right); } if (curr.left != null) { stack.push(curr.left); } } return result; }} |
二、中序遍歷（Inorder Traversal）
簡(jiǎn)單來(lái)講，中序遍歷就是先訪問(wèn)左孩子，再訪問(wèn)父節(jié)點(diǎn)，最后訪問(wèn)右孩子，即以左、父、右的順序遍歷。
遞歸代碼也比較容易，如下所示：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<Integer>(); recurse(root, result); return result; } private void recurse(TreeNode root, List<Integer> result) { if (root == null) return; recurse(root.left, result); result.add(root.val); recurse(root.right, result); }} |
上面這種寫(xiě)法有別于前序遍歷的遞歸代碼，前序遍歷的遞歸我們使用了成員變量來(lái)存儲(chǔ)遍歷的結(jié)果，這里我們使用方法參數(shù)來(lái)保存遍歷的結(jié)果。兩種寫(xiě)法都可以，喜歡哪種就使用哪種。
中序遍歷的迭代實(shí)現(xiàn)沒(méi)有前序遍歷那么簡(jiǎn)單，雖然也需要借助一個(gè)棧，但迭代終止的條件卻有所不同。想象一下，對(duì)于一棵二叉樹(shù)，我們最先訪問(wèn)的節(jié)點(diǎn)是其最左邊的節(jié)點(diǎn)，我們當(dāng)然可以通過(guò)一個(gè) while 循環(huán)到達(dá)其最左邊，可是當(dāng)我們回退時(shí)，我們?nèi)绾沃滥硞€(gè)節(jié)點(diǎn)的左孩子是否已經(jīng)訪問(wèn)過(guò)了？我們使用一個(gè) curr 變量記錄當(dāng)前訪問(wèn)的節(jié)點(diǎn)，當(dāng)我們把一棵子樹(shù)的右節(jié)點(diǎn)都訪問(wèn)完畢時(shí)，我們就該回退該子樹(shù)的父節(jié)點(diǎn)了，而此時(shí) curr 為 null，所以我們可以以此來(lái)區(qū)分一個(gè)節(jié)點(diǎn)的左子樹(shù)是否已被訪問(wèn)過(guò)。代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode curr = root; while (curr != null || !stack.isEmpty()) { while (curr != null) { stack.push(curr); curr = curr.left; } curr = stack.pop(); result.add(curr.val); curr = curr.right; } return result; }} |
三、后序遍歷（Postorder Traversal）
簡(jiǎn)單來(lái)講，后序遍歷就是先訪問(wèn)左孩子，在訪問(wèn)右孩子，最后訪問(wèn)父節(jié)點(diǎn)， 即以左、右、父的順序遍歷。
仿照中序遍歷，可以很容易地寫(xiě)出后序遍歷的遞歸實(shí)現(xiàn)：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<Integer>(); recurse(root, result); return result; } private void recurse(TreeNode root, List<Integer> result) { if (root == null) return; recurse(root.left, result); recurse(root.right, result); result.add(root.val); }} |
后序遍歷的迭代，也需要一個(gè)標(biāo)識(shí)要區(qū)分一個(gè)節(jié)點(diǎn)的左右孩子是否已經(jīng)訪問(wèn)過(guò)了，如果沒(méi)有，則依次訪問(wèn)其左右孩子，如果訪問(wèn)過(guò)了，則訪問(wèn)該節(jié)點(diǎn)。為此，我們用一個(gè) pre 變量來(lái)表示上一個(gè)訪問(wèn)的節(jié)點(diǎn)，如果上一個(gè)訪問(wèn)的節(jié)點(diǎn)是當(dāng)前節(jié)點(diǎn)的左孩子或右孩子，那么說(shuō)明當(dāng)前節(jié)點(diǎn)的左右孩子已經(jīng)訪問(wèn)過(guò)了，那么就可以訪問(wèn)該節(jié)點(diǎn)了，否則，則需要進(jìn)入左右孩子依次訪問(wèn)。代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
public class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new LinkedList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); if (root != null) stack.push(root); TreeNode pre = root; while (!stack.isEmpty()) { TreeNode curr = stack.peek(); if (curr.left == pre || curr.right == pre || (curr.left == null && curr.right == null)) { result.add(curr.val); stack.pop(); pre = curr; } else { if (curr.right != null) stack.push(curr.right); if (curr.left != null) stack.push(curr.left); } } return result; }} |
后序遍歷的迭代還有另外一種比較簡(jiǎn)單的實(shí)現(xiàn)，我們知道先序遍歷的順序是父、左、右，而后序遍歷的順序是左、右、父，那么如果我們把先序遍歷稍作修改，改成父、右、左的順序，那么就剛好與后序遍歷的順序相反了，以如此順序訪問(wèn)完，最后我們對(duì)訪問(wèn)結(jié)果做個(gè)反轉(zhuǎn)就可以了。而先序遍歷的迭代實(shí)現(xiàn)相對(duì)來(lái)說(shuō)比較容易，仿照上面寫(xiě)法我們可以如下實(shí)現(xiàn)：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new LinkedList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); if (root != null) stack.push(root); while (!stack.isEmpty()) { TreeNode curr = stack.pop(); result.add(curr.val); if (curr.left != null) stack.push(curr.left); if (curr.right != null) stack.push(curr.right); } Collections.reverse(result); return result; }} |
四、總結(jié)
三種遍歷的遞歸實(shí)現(xiàn)都很容易。前序遍歷的迭代實(shí)現(xiàn)最好寫(xiě)，只需要一個(gè)棧就好；中序遍歷最難，循環(huán)條件除了判斷棧是否為空，還要判斷當(dāng)前節(jié)點(diǎn)是否為空，以表示是否左子樹(shù)已經(jīng)遍歷完畢；后續(xù)遍歷的迭代如果轉(zhuǎn)化為前序遍歷的迭代，就容易很多，否則，也需要記錄上一個(gè)訪問(wèn)的節(jié)點(diǎn)，以表示當(dāng)前節(jié)點(diǎn)的左右子樹(shù)是否已經(jīng)訪問(wèn)完畢。
