紅黑樹的性質
保證樹中最長路徑的長度不超過最短路徑的長度的兩倍
用什么方法保證上面這一點？將樹中的結點視為是有顏色的
?采用如下的規則：
?? ? ?rule1: 樹中的結點不是紅色就是黑色
?? ? ?rule2: 樹的根節點是黑色的
?? ? ?rule3: 如果一個結點是紅色的，則這個結點的左右孩子都是黑色的
?? ? ?rule4: 對于每個結點，該節點到其所有后代葉節點的簡單路徑上，均包含相同數目的黑色節點
?? ? ?rule5: 每個葉?? ?子節點都是黑色的
?? ??? ?對rule5的說明
?? ??? ?rule5保證了規則體系完備，空結點視為是葉子節點，那么每個空結點就決定了一條路徑，
?? ??? ?rule4在計算路徑長度的時候，并不把空結點計算在內，但是只要存在路徑就必須計算長度
?? ??? ?比如 下面的左下圖是紅黑樹，右下圖不是紅黑樹,(-代表當前結點和有非空左孩子或者右孩子)
?? ??? ??? ??? ?-B-?? ??? ??? ??? ??? ??? ??? ??? ??? ??? ?-B-
?? ??? ??? ?B?? ??? ?-R-? ? ? ? ? ? ? ? ? ? ? ? ? ???B?? ??? ?R-
?? ??? ??? ??? ?B?? ??? ?-B? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? -B
?? ??? ??? ??? ??? ?R?? ??? ??? ??? ??? ??? ??? ??? ??? ??

		while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//緊接著的if()else{}判斷叔叔所在的位置// 這個位置直接確定了下面旋轉的(如果需要的話)方向if (parent == grandfather->_left){Node* uncle = grandfather->_right;//如果叔叔存在，且叔叔的顏色為紅，只需變色即可if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 繼續往上處理cur = grandfather;parent = cur->_parent;}//如果叔叔不存在，或者叔叔的顏色為黑，必須考慮旋轉的情況else{// 當叔叔的顏色為黑，那么要考慮新插入的結點是在// 其父親結點 p 的左子樹上，還是在其父親結點的右子樹上，// 以確定旋轉是進行兩次，還是進行一次if (cur == parent->_left){//如果是如圖所示的結構，只需要調整 c p g 條路徑// 調整的方式是右單旋，函數傳入的參數是g//	    	g//		p		u//  cRotateright(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//如果是如圖所示的結構，只需要調整 c p g 條路徑(其中c是p的右子樹)// 調整的方式是先左單旋，函數傳入的參數是p，調整p和c的父子關系// 再右單旋，傳入的參數是g//	    	g//		p		u//			cRotateleft(parent);Rotateright(grandfather);//此處一定要畫圖進行理解，cur經過兩次最后成為了輩分最高的結點//p和g成為了兄弟，而且都需要變成紅色cur->_col = BLACK;grandfather->_col = RED;}// 如果進行了旋轉，旋轉針對的當前樹中輩分最高的那個節點已經會被調整成黑色break;}}else{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 繼續往上處理cur = grandfather;parent = cur->_parent;}else //叔叔不存在，或存在且為黑的情況{if (cur == parent->_right){//	    	g//		u		p//					cRotateleft(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//	    	g//		u		p//			cRotateright(parent);Rotateleft(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;

? ?R