[ symmetric binary B-tree ( red black tree ) ] 對稱二叉B樹 ( 紅黑樹 )

紅黑樹是一種有最壞情況擔保的平衡樹，其插入最多會用到2個旋轉，刪除最多用到3個旋轉，其犧牲些許的平衡來加快插入刪除的速度，並有高度上h<=2*log(n+1)的保證。
故其插入刪除之常數會比較小，而查詢之常數會較大(相對於一般高度平衡樹)，而一般的函式庫裡的"關聯數組"通常適用紅黑樹實做的
其平衡原因及方法請參考維基百科
因其操作複雜故不常在競賽中被使用，且刪除速度較size balanced tree慢約2倍

以下提供模板: