紅黑樹rbtree

紅黑樹（Red Black Tree） 是一種自平衡二叉查找樹，是在計算機科學中用到的一種資料結構，典型的用途是實作關聯數組。

它是在1972年由Rudolf Bayer發明的，當時被稱為平衡二叉B樹（symmetric binary B-trees）。後來，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改為如今的“紅黑樹”。

紅黑樹和AVL樹類似，都是在進行插入和删除操作時通過特定操作保持二叉查找樹的平衡，進而獲得較高的查找性能。

它雖然是複雜的，但它的最壞情況運作時間也是非常良好的，并且在實踐中是高效的： 它可以在O(log n)時間内做查找，插入和删除，這裡的n 是樹中元素的數目。

<a href="http://blog.csdn.net/npy_lp/article/details/7420689" target="_blank">http://blog.csdn.net/npy_lp/article/details/7420689</a>

<a href="https://baike.baidu.com/item/%E7%BA%A2%E9%BB%91%E6%A0%91" target="_blank">https://baike.baidu.com/item/%E7%BA%A2%E9%BB%91%E6%A0%91</a>