chúng ta có thể thấy rằng sáu bước sản xuất một phạm vi khá lớn (64), trong khi bảy bước bao gồm handily (128). Như vậy, bảy bước được hiển thị cho 100 mặt hàng trong Bảng là chính xác, cũng như là 10 bước cho một phạm vi của 1000. Tăng gấp đôi phạm vi mỗi lần tạo ra một loạt giống như nâng cao hai quyền lực một, như thể hiện trong thứ ba | Rule 2 the root is always black . Don t worry about this yet. Instead rotate the other way. Position the red arrow on 25 which is now the root the arrow should already point to 25 after the previous rotation . Click the RoL button to rotate left. The nodes will return to the position of Figure . Experiment 3 Start with the position of Figure with nodes 25 and 75 inserted in addition to 50 in the root position. Note that the parent the root is black and both its children are red. Now try to insert another node. No matter what value you use you ll see the message Can t Insert Needs color flip. As we mentioned a color flip is necessary whenever during the insertion process a black node with two red children is encountered. The red arrow should already be positioned on the black parent the root node so click the Flip button. The root s two children change from red to black. Ordinarily the parent would change from black to red but this is a special case because it s the root it remains black to avoid violating Rule 2. Now all three nodes are black. The tree is still red-black correct. Now click the Ins button again to insert the new node. Figure shows the result if the newly inserted node has the key value 12. The tree is still red-black correct. The root is black there s no situation in which a parent and child are both red and all the paths have the same number of black nodes 2 . Adding the new red node didn t change the red-black correctness. Experiment 4 Now let s see what happens when you try to do something that leads to an unbalanced tree. In Figure one path has one more node than the other. This isn t very unbalanced and no red-black rules are violated so neither we nor the red-black algorithms need to worry about it. However suppose that one path differs from another by two or more levels where level is the same as the number of nodes along the path . In this case the red-black rules will always be violated and we ll need to rebalance the tree. .
