红黑树

				
					
					1
					// 红黑树插入修复
				
			
				
					
					2
					procedure rbInsertFixup(T, z)
				
			
				
					
					3
					  while z.parent 为红色 do
				
			
				
					
					4
					    if z 的叔叔是红色 then
				
			
				
					
					5
					      变色：父、叔变黑，祖父变红
				
			
				
					
					6
					      z = 祖父
				
			
				
					
					7
					    else
				
			
				
					
					8
					      旋转 + 变色（LL/LR/RR/RL）
				
			
				
					
					9
					    end if
				
			
				
					
					10
					  end while
				
			
				
					
					11
					  根节点染黑
				
			
				
					
					12
					end procedure