排序二叉樹(shù)是一種特殊結(jié)構(gòu)的二叉樹(shù)，可以非常方便地對(duì)樹(shù)中所有節(jié)點(diǎn)進(jìn)行排序和檢索。

排序二叉樹(shù)要么是一棵空二叉樹(shù)，要么是具有下列性質(zhì)的二叉樹(shù)：

紅黑樹(shù)

排序二叉樹(shù)雖然可以快速檢索，但在最壞的情況下：如果插入的節(jié)點(diǎn)集本身就是有序的，要么是由小到大排列，要么是由大到小排列，那么最后得到的排序二叉樹(shù)將變成鏈表：所有節(jié)點(diǎn)只有左節(jié)點(diǎn)（如果插入節(jié)點(diǎn)集本身是大到小排列）；或所有節(jié)點(diǎn)只有右節(jié)點(diǎn)（如果插入節(jié)點(diǎn)集本身是小到大排列）。在這種情況下，排序二叉樹(shù)就變成了普通鏈表，其檢索效率就會(huì)很差。

為了改變排序二叉樹(shù)存在的不足，Rudolf Bayer 與 1972年發(fā)明了另一種改進(jìn)后的排序二叉樹(shù)：紅黑樹(shù)，他將這種排序二叉樹(shù)稱為“對(duì)稱二叉 B 樹(shù)”，而紅黑樹(shù)這個(gè)名字則由 Leo J. Guibas和 Robert Sedgewick 于 1978 年首次提出。

紅黑樹(shù)是一個(gè)更高效的檢索二叉樹(shù)，因此常常用來(lái)實(shí)現(xiàn)關(guān)聯(lián)數(shù)組。典型地，JDK 提供的集合類 TreeMap本身就是一個(gè)紅黑樹(shù)的實(shí)現(xiàn)。

紅黑樹(shù)在原有的排序二叉樹(shù)增加了如下幾個(gè)要求：

Java 實(shí)現(xiàn)的紅黑樹(shù)

上面的性質(zhì) 3 中指定紅黑樹(shù)的每個(gè)葉子節(jié)點(diǎn)都是空節(jié)點(diǎn)，而且并葉子節(jié)點(diǎn)都是黑色。但 Java 實(shí)現(xiàn)的紅黑樹(shù)將使用 null來(lái)代表空節(jié)點(diǎn)，因此遍歷紅黑樹(shù)時(shí)將看不到黑色的葉子節(jié)點(diǎn)，反而看到每個(gè)葉子節(jié)點(diǎn)都是紅色的。

Java 中實(shí)現(xiàn)的紅黑樹(shù)可能有如圖 6 所示結(jié)構(gòu)：

圖 6. Java紅黑樹(shù)的示意

備注：本文中所有關(guān)于紅黑樹(shù)中的示意圖采用白色代表紅色。黑色節(jié)點(diǎn)還是采用了黑色表示。

根據(jù)性質(zhì)5：紅黑樹(shù)從根節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)的路徑都包含相同數(shù)量的黑色節(jié)點(diǎn)，因此從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑中包含的黑色節(jié)點(diǎn)數(shù)被稱為樹(shù)的“黑色高度（black-height）”。

性質(zhì) 4 則保證了從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度不會(huì)超過(guò)任何其他路徑的兩倍。假如有一棵黑色高度為 3的紅黑樹(shù)：從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的最短路徑長(zhǎng)度是 2，該路徑上全是黑色節(jié)點(diǎn)（黑節(jié)點(diǎn) - 黑節(jié)點(diǎn) - 黑節(jié)點(diǎn)）。最長(zhǎng)路徑也只可能為4，在每個(gè)黑色節(jié)點(diǎn)之間插入一個(gè)紅色節(jié)點(diǎn)（黑節(jié)點(diǎn) - 紅節(jié)點(diǎn) - 黑節(jié)點(diǎn) - 紅節(jié)點(diǎn) - 黑節(jié)點(diǎn)），性質(zhì) 4保證絕不可能插入更多的紅色節(jié)點(diǎn)。由此可見(jiàn)，紅黑樹(shù)中最長(zhǎng)路徑就是一條紅黑交替的路徑。

紅黑樹(shù)和平衡二叉樹(shù)

紅黑樹(shù)并不是真正的平衡二叉樹(shù)，但在實(shí)際應(yīng)用中，紅黑樹(shù)的統(tǒng)計(jì)性能要高于平衡二叉樹(shù)，但極端性能略差。

由此我們可以得出結(jié)論：對(duì)于給定的黑色高度為 N 的紅黑樹(shù)，從根到葉子節(jié)點(diǎn)的最短路徑長(zhǎng)度為 N-1，最長(zhǎng)路徑長(zhǎng)度為 2 *(N-1)。

提示：排序二叉樹(shù)的深度直接影響了檢索的性能，正如前面指出，當(dāng)插入節(jié)點(diǎn)本身就是由小到大排列時(shí)，排序二叉樹(shù)將變成一個(gè)鏈表，這種排序二叉樹(shù)的檢索性能最低：N個(gè)節(jié)點(diǎn)的二叉樹(shù)深度就是 N-1。

紅黑樹(shù)通過(guò)上面這種限制來(lái)保證它大致是平衡的——因?yàn)榧t黑樹(shù)的高度不會(huì)無(wú)限增高，這樣保證紅黑樹(shù)在最壞情況下都是高效的，不會(huì)出現(xiàn)普通排序二叉樹(shù)的情況。

由于紅黑樹(shù)只是一個(gè)特殊的排序二叉樹(shù)，因此對(duì)紅黑樹(shù)上的只讀操作與普通排序二叉樹(shù)上的只讀操作完全相同，只是紅黑樹(shù)保持了大致平衡，因此檢索性能比排序二叉樹(shù)要好很多。

但在紅黑樹(shù)上進(jìn)行插入操作和刪除操作會(huì)導(dǎo)致樹(shù)不再符合紅黑樹(shù)的特征，因此插入操作和刪除操作都需要進(jìn)行一定的維護(hù)，以保證插入節(jié)點(diǎn)、刪除節(jié)點(diǎn)后的樹(shù)依然是紅黑樹(shù)。

愛(ài)華網(wǎng)本文地址 » http://www.klfzs.com/a/25101016/293134.html