red-black tree.png
算法導(dǎo)論中的紅黑樹(shù)
- 每個(gè)節(jié)點(diǎn)或者是紅色的，或者是黑色的
- 跟節(jié)點(diǎn)是黑色的
- 每一個(gè)葉子節(jié)點(diǎn)（最后的空節(jié)點(diǎn)）是黑色的
- 如果一個(gè)節(jié)點(diǎn)是紅色的，那么他的孩子節(jié)點(diǎn)都是黑色的
- 從任意一個(gè)節(jié)點(diǎn)到葉子節(jié)點(diǎn)，經(jīng)過(guò)的黑色節(jié)點(diǎn)是一樣的
算法4中的紅黑樹(shù)
紅黑樹(shù)與2-3樹(shù)的等價(jià)性
2-3樹(shù)
滿足二分搜索樹(shù)的基本性質(zhì)
節(jié)點(diǎn)亦可以存放一個(gè)或者兩個(gè)元素
每個(gè)節(jié)點(diǎn)有兩個(gè)孩子或三個(gè)孩子
nodes.png
對(duì)于a節(jié)點(diǎn)，左孩子小于a，右孩子大于a
對(duì)于bc節(jié)點(diǎn)，左孩子小于b，b<中間孩子<c，右孩子>c
2-3 tree example.png
2-3樹(shù)是絕對(duì)平衡的樹(shù)（根節(jié)點(diǎn)到任意一個(gè)葉子節(jié)點(diǎn)所經(jīng)過(guò)的節(jié)點(diǎn)數(shù)量是相同的）
