顏色翻轉(zhuǎn)
- 顏色翻轉(zhuǎn)過程概述：
- 顏色翻轉(zhuǎn)的觸發(fā)場景：向2-3樹中的3節(jié)點添加元素抓半，新添加的元素要添加到3節(jié)點的最右側(cè)；
- 對應(yīng)到紅黑樹中的情形是：新添加的紅節(jié)點在黑節(jié)點右側(cè)囊嘉，黑節(jié)點的左側(cè)還有一個紅節(jié)點温技，紅黑樹中的這種形態(tài)對應(yīng)到2-3樹中就是一個臨時的4節(jié)點；
- 2-3樹中臨時的4節(jié)點要拆成3個2節(jié)點哗伯，這種形態(tài)對應(yīng)到紅黑樹中就是3個黑節(jié)點荒揣；
- 2-3樹在拆成3個2節(jié)點后，要向上融合焊刹，3個2節(jié)點中間的那個節(jié)點是要融合的，所以它是紅色的恳蹲；
- 最后從結(jié)果看虐块，從一添加的“紅-黑-紅”，到拆完后形成的“黑-紅-黑”嘉蕾，正好形成顏色的翻轉(zhuǎn)贺奠，即所謂的顏色翻轉(zhuǎn)；
- 紅黑樹中涉及的一些結(jié)論：
- 紅黑樹中错忱，如果一個黑節(jié)點左側(cè)沒有紅色節(jié)點的話儡率，它本身就代表2-3樹中一個單獨的2節(jié)點挂据；
-
3個2節(jié)點對應(yīng)到紅黑樹中表示的是這3個節(jié)點都是黑節(jié)點；
- 2-3樹中儿普，臨時的4節(jié)點在拆完后還要向上融合崎逃，融合意味著，2-3樹中臨時4節(jié)點在拆完后向上融合的根眉孩，在紅黑樹中是紅色的个绍；
顏色翻轉(zhuǎn)代碼
- 調(diào)用該方法的先決條件是：node - 黑，node.left - 紅浪汪，node.right - 紅巴柿；
// 顏色翻轉(zhuǎn)
private void flipColors(Node node){
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
右旋轉(zhuǎn)
- 右旋轉(zhuǎn)觸發(fā)的場景：新添加的元素要融合到3節(jié)點的最左邊；
- 對應(yīng)到紅黑樹中的場景是：根節(jié)點是黑死遭，根節(jié)點的左孩子是紅广恢，根節(jié)點左孩子的左孩子是紅；
- 旋轉(zhuǎn)過后呀潭，3個節(jié)點還是對應(yīng)著2-3樹中的臨時4節(jié)點钉迷，所以左右2個孩子的顏色都得是紅的，紅-黑-紅蜗侈，這就對應(yīng)到了顏色翻轉(zhuǎn)的情況了篷牌，繼而進行顏色翻轉(zhuǎn)；
右旋轉(zhuǎn)代碼
// node x
// / \ 右旋轉(zhuǎn) / \
// x T2 -------> y node
// / \ / \
// y T1 T1 T2
private Node rightRotate(Node node){
Node x = node.left;
// 右旋轉(zhuǎn)
node.left = x.right;
x.right = node;
x.color = node.color;
node.color = RED;
return x;
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
