資訊專欄INFORMATION COLUMN
摘要：對于一棵有效的紅黑樹二叉樹而言我們必須增加如下規(guī)則每個節(jié)點都只能是紅色或者黑色根節(jié)點是黑色每個葉節(jié)點節(jié)點，空節(jié)點是黑色的。這些約束強制了紅黑樹的關鍵性質(zhì)從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。
群里的大哥說了，要想懂紅黑樹的應用，先要看TreeMap。
想要解鎖更多新姿勢？請訪問http://blog.tengshe789.tech/
OK，現(xiàn)在開始：
紅黑樹簡介紅黑樹又稱紅-黑二叉樹，它首先是一顆二叉樹，它具體二叉樹所有的特性。同時紅黑樹更是一顆自平衡的排序二叉樹。
? 一般的二叉樹他們都需要滿足一個基本性質(zhì)--即樹中的任何節(jié)點的值大于它的左子節(jié)點，且小于它的右子節(jié)點。因為按照這個基本性質(zhì)使得樹的檢索效率大大提高。但我們知道在生成二叉樹的過程是非常容易失衡的，最壞的情況就是一邊倒（只有右/左子樹），這樣勢必會導致二叉樹的檢索效率大大降低（O(n)），所以為了維持二叉樹的平衡，大牛們提出了各種實現(xiàn)的算法，如：AVL，SBT，伸展樹，TREAP ，紅黑樹等等。
? 平衡二叉樹必須具備如下特性：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。也就是說該二叉樹的任何一個等等子節(jié)點，其左右子樹的高度都相近。
紅黑樹顧名思義就是節(jié)點是紅色或者黑色的平衡二叉樹，它通過顏色的約束來維持著二叉樹的平衡。對于一棵有效的紅黑樹二叉樹而言我們必須增加如下規(guī)則：
? 1、每個節(jié)點都只能是紅色或者黑色
? 2、根節(jié)點是黑色
? 3、每個葉節(jié)點（NIL節(jié)點，空節(jié)點）是黑色的。
? 4、如果一個結(jié)點是紅的，則它兩個子節(jié)點都是黑的。也就是說在一條路徑上不能出現(xiàn)相鄰的兩個紅色結(jié)點。
? 5、從任一節(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點。
? 這些約束強制了紅黑樹的關鍵性質(zhì): 從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。結(jié)果是這棵樹大致上是平衡的。因為操作比如插入、刪除和查找某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同于普通的二叉查找樹。所以紅黑樹它是復雜而高效的，其檢索效率O(log n)。下圖為一顆典型的紅黑二叉樹。
關于TreeMap我沒看懂啊啊啊啊，我看懂了在更新(立FLAG
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/76631.html
摘要：源碼剖析由于紅黑樹的操作我這里不說了，所以這里基本上也就沒什么源碼可以講了，因為這里面重要的算法都是，這里的是指，他們是算法導論的作者，也就是說里面算法都是參照算法導論的偽代碼。因為紅黑樹是平衡的二叉搜索樹，所以其包含操作的時間復雜度都為。 本文章首發(fā)于個人博客，鑒于sf博客樣式具有賞心悅目的美感，遂發(fā)表于此，供大家學習、批評。本文還在不斷更新中，最新版可移至個人博客。? 繼上篇文章...
摘要：它有什么圖表加粗文字如何使用這個圖表庫可以通過存儲庫下載或通過包管理器安裝。數(shù)據(jù)可以直接從文件加載到圖表中。它有什么圖表如何使用該庫可在包管理器和他們自己的內(nèi)容傳送網(wǎng)絡中使用。該庫專為風格的數(shù)據(jù)可視化而設計，提供一系列高度可配置的圖表。 現(xiàn)在有很多圖表庫，但哪一個最好用？這可能取決于許多因素，如業(yè)務需求，數(shù)據(jù)類型，圖表本身的目的等等。在本文中，每個JavaScript圖表庫將與一些關鍵...
摘要：它有什么圖表加粗文字如何使用這個圖表庫可以通過存儲庫下載或通過包管理器安裝。數(shù)據(jù)可以直接從文件加載到圖表中。它有什么圖表如何使用該庫可在包管理器和他們自己的內(nèi)容傳送網(wǎng)絡中使用。該庫專為風格的數(shù)據(jù)可視化而設計，提供一系列高度可配置的圖表。 現(xiàn)在有很多圖表庫，但哪一個最好用？這可能取決于許多因素，如業(yè)務需求，數(shù)據(jù)類型，圖表本身的目的等等。在本文中，每個JavaScript圖表庫將與一些關鍵...
摘要：它有什么圖表加粗文字如何使用這個圖表庫可以通過存儲庫下載或通過包管理器安裝。數(shù)據(jù)可以直接從文件加載到圖表中。它有什么圖表如何使用該庫可在包管理器和他們自己的內(nèi)容傳送網(wǎng)絡中使用。該庫專為風格的數(shù)據(jù)可視化而設計，提供一系列高度可配置的圖表。 現(xiàn)在有很多圖表庫，但哪一個最好用？這可能取決于許多因素，如業(yè)務需求，數(shù)據(jù)類型，圖表本身的目的等等。在本文中，每個JavaScript圖表庫將與一些關鍵...
摘要：當往中放入新的鍵值對后，可能會破壞紅黑樹的性質(zhì)。修復操作要重新使紅黑樹恢復平衡，修復操作的源碼分析如下方法分析如下上面對部分代碼邏輯就行了分析，通過配圖的形式解析了每段代碼邏輯所處理的情況。四總結(jié)本文可以看做是本人紅黑樹詳細分析一文的延續(xù)。 一、簡介 TreeMap最早出現(xiàn)在JDK 1.2中，是 Java 集合框架中比較重要一個的實現(xiàn)。TreeMap 底層基于紅黑樹實現(xiàn)，可保證在log...
閱讀 744·2021-11-11 16:54
閱讀 3065·2021-09-26 09:55
閱讀 2015·2021-09-07 10:20
閱讀 1211·2019-08-30 10:58
閱讀 1057·2019-08-28 18:04
閱讀 707·2019-08-26 13:57
閱讀 3598·2019-08-26 13:45
閱讀 1164·2019-08-26 11:42
