紅黑樹掠廓，叫red black tree/2b tree，了解紅黑樹之前芦瘾，先了解下2-3樹，2-3樹容易理解
且和紅黑樹有某種等價性，了解2-3樹有助于了解紅黑樹 //
如以上圖過程： //
1）每次插入新節(jié)點時黔衡，都是先找到要插入的最后節(jié)點，與最后節(jié)點相融合腌乡；
2）融合后如果是3節(jié)點盟劫，則后續(xù)不變；
3）融合后如果是4節(jié)點与纽，則分裂一棵子樹侣签，并將其父節(jié)點向上一級融合，直到根節(jié)點為止
2-3樹和紅黑樹的等價性
依照上圖的性質(zhì)急迂，3節(jié)點采用的是左傾的3節(jié)點影所，這樣建出來的紅黑樹稱為左傾紅黑樹，據(jù)此也有
右傾紅黑樹僚碎，即b在上型檀，c在b的右邊，c是紅色表示與父節(jié)點是同一個節(jié)點听盖。//
2-3樹和紅黑樹可以等價為下圖：
如上圖胀溺，好好理解，向紅黑樹中添加元素的情形跟2-3樹中添加元素類似皆看，都是通過融合仓坞、分裂；
//
向紅黑樹中融合元素可以分為以下2類腰吟，共5種情形：（默認添加紅節(jié)點无埃，表明該節(jié)點與父節(jié)點是融合的）
1. 向2節(jié)點中融合元素
情形1）融合的節(jié)點在2節(jié)點的左邊徙瓶；
情形2）融合的節(jié)點在2節(jié)點的右邊；
2. 向3節(jié)點中融合元素
情形3）融合的元素在3節(jié)點的中間嫉称；
情形4）融合的元素在3節(jié)點的左邊侦镇；
情形5）融合的元素在3節(jié)點的右邊；
5種情形如下圖演示：
依據(jù)上面5種情形织阅，向紅黑樹中添加節(jié)點可以歸納為以下流程： //
最后的顏色翻轉(zhuǎn)之后壳繁，新的紅節(jié)點要再向上做判斷，之后重復(fù)這個流程荔棉，直到根節(jié)點為止
續(xù)下一篇《（24）Go實現(xiàn)紅黑樹-實現(xiàn)和總結(jié)》：
http://www.reibang.com/p/172c2717ae19
有bug歡迎指出闹炉，轉(zhuǎn)載請注明出處。
