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