紅黑樹的旋轉操作紅黑樹的旋轉操作和AVL樹一樣,分為Ll 、RR、LR、RL四種旋轉類型,差別在於旋轉完成後改變的是結點的顏色,而不是平衡因子。旋轉動畫演示請
2.2 黑叔當叔父結點為黑色時,需要進行旋轉,以下圖示了所有的旋轉可能情形1:情形2:情形3:情形4:可以觀察到,當旋轉完成後,新的旋轉根全部為黑色,此時不需
紅黑樹上結點的刪除紅黑樹本身是一棵二叉查找樹,它的刪除和二叉查找樹的刪除類似。首先要找到真正的刪除點,當被刪除結點n存在左右孩子時,真正的刪除點應該是n的中序
3、雙黑當舊點和新點都為黑色時(新點為空結點時,亦屬於這種情況),情況比較復雜,需要根據舊點兄弟結點的顏色來決定進行什麼樣的操作。我們使用“兄”來表示舊點的兄
3.2.3 黑兄紅侄黑兄紅侄有以下四種情形,下面分別進行圖示:情形1:情形2:情形3:情形4:由以上圖例所示,看完以上四張圖的兄弟有可能會有一個疑問,如果情形