紅黑樹

1. 基于 2-3 Tree

為了讓樹高能夠維持~lg(n)。
保持各個底部空鏈接和root距離相等(為了維持這個性質(zhì)，后面插入時才會有各種變化)

1.1 結(jié)構(gòu)

• 2節(jié)點(含有一個key和兩個鏈接)
• 3節(jié)點(含有兩個key和三個鏈接)

1.2 操作

• 2節(jié)點 插入-->直接添加，變成3節(jié)點
• 3節(jié)點 插入-->直接添加，然后裂變成三個2節(jié)點
• 向父節(jié)點為2節(jié)點的 3節(jié)點 插入-->父節(jié)點變3節(jié)點，然后下面裂變成2個2節(jié)點
• 向父節(jié)點為3節(jié)點的 3節(jié)點 插入-->會一直向上裂變，知道遇到2節(jié)點

2. 紅黑樹就是2-3樹的一個實現(xiàn)

1.1 結(jié)構(gòu)

• 2節(jié)點(含有一個key和兩個鏈接) ，就是普通鏈接，我們叫這種鏈接為黑鏈接
• 3節(jié)點(含有兩個key和三個鏈接)，為了在二叉樹中模擬出這種節(jié)點，我們設(shè)計兩個節(jié)點由左斜鏈接相連的為3節(jié)點，其中的鏈接叫紅鏈接

由此產(chǎn)生兩個性質(zhì)(聯(lián)想2-3樹原型就可以看出):

1. 紅鏈接均為左鏈接
2. 沒有任何一個節(jié)點與兩個紅鏈接相連
3. 樹是黑色平衡的。

如何表示紅鍵：我們在每個node設(shè)一個color，其指代指向這個節(jié)點的鏈接的顏色。