① 紅黑樹的用途
紅黑樹用在關聯數組、字典的實現上。需要的空間比散列表小。 任何鍵值對應,需要隨機存儲和鍵有序的情況都可以用。
② 紅黑樹，b+樹分別用於什麼場景，為什麼
紅黑樹屬於「黑平衡」的二叉樹，雖然犧牲了一定的平衡性，但是add、remove操作要由優於AVL樹也就是說RB-Tree的「統計性能」更佳！Java中TreeSet，TreeMap的底層都是基於RedBlackTree紅黑樹的；
B+樹主要用在文件系統以及資料庫做索引。比如磁碟存儲、文件系統、MySQL資料庫
③ 什麼是紅黑樹
紅黑樹（Red Black Tree） 是一種自平衡二叉查找樹，是在計算機科學中用到的一種數據結構，典型的用途是實現關聯數組。
紅黑樹是在1972年由Rudolf Bayer發明的，當時被稱為平衡二叉B樹（symmetric binary B-trees）。後來，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改為如今的「紅黑樹」。
樹的旋轉
當我們在對紅黑樹進行插入和刪除等操作時，對樹做了修改，那麼可能會違背紅黑樹的性質。
為了保持紅黑樹的性質，我們可以對相關結點做一系列的調整，通過對樹進行旋轉（例如左旋和右旋操作），即修改樹中某些結點的顏色及指針結構，以達到對紅黑樹進行插入、刪除結點等操作時，紅黑樹依然能保持它特有的性質（五點性質）。
④ 紅黑樹內部節點包含根節點葉節點嗎
紅黑樹內部節點包含根節點葉節點.
好亂。
紅黑樹只有三個性質。
1：根節點和所有外部節點是黑色。
2：根至外部節點中沒有兩個連續的顏色是黑色
3：所有根節點至外部節點的路徑上都有相同數目的黑色節點。
注1：外部節點就是葉節點指向的NULL節點，只不過這里不再指向NULL，而是一個實質性的空節點。
注2：紅黑樹還有另一種規則（路徑指針），但是和上面的是一樣的意思，所以不列舉了。
⑤ 數據結構：紅黑樹
好亂。
紅黑樹只有三個性質。
1：根節點和所有外部節點是黑色。
2：根至外部節點中沒有兩個連續的顏色是黑色
3：所有根節點至外部節點的路徑上都有相同數目的黑色節點。
注1：外部節點就是葉節點指向的NULL節點，只不過這里不再指向NULL，而是一個實質性的空節點。
注2：紅黑樹還有另一種規則（路徑指針），但是和上面的是一樣的意思，所以不列舉了。
以上回答你滿意么？
⑥ AVL樹，紅黑樹，B樹，B+樹，Trie樹都分別應用在哪些現實場景中
在C++ STL中，很多部分(目前包括set, multiset, map, multimap)應用了紅黑樹的變體(SGI STL中的紅黑樹有一些變化，這些修改提供了更好的性能，以及對set操作的支持)。紅黑樹是每個節點都帶有顏色屬性的二叉查找樹，顏色或紅色或黑色。在二叉查找樹強制一般要求以外，對於任何有效的紅黑樹我們增加了如下的額外要求: 性質1. 節點是紅色或黑色。 性質2. 根是黑色。 性質3 每個葉節點是黑色的。 性質4 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點) 性質5. 從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。 An example of a red-black tree 這些約束強制了紅黑樹的關鍵性質: 從根到葉子的最長的可能路徑不多於最短的可能路徑的兩倍長。結果是這個樹大致上是平衡的。因為操作比如插入、刪除和查找某個值的最壞情況時間都要求與樹的高度成比例，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同於普通的二叉查找樹。 要知道為什麼這些特性確保了這個結果，注意到屬性5導致了路徑不能有兩個毗連的紅色節點就足夠了。最短的可能路徑都是黑色節點，最長的可能路徑有交替的紅色和黑色節點。因為根據屬性4所有最長的路徑都有相同數目的黑色節點，這就表明了沒有路徑能多於任何其他路徑的兩倍長。 在很多樹數據結構的表示中，一個節點有可能只有一個子節點，而葉子節點包含數據。用這種範例表示紅黑樹是可能的，但是這會改變一些屬性並使演算法復雜。為此，本文中我們使用 "nil 葉子" 或"空(null)葉子"，如上圖所示，它不包含數據而只充當樹在此結束的指示。這些節點在繪圖中經常被省略，導致了這些樹好象同上述原則相矛盾，而實際上不是這樣。與此有關的結論是所有節點都有兩個子節點，盡管其中的一個或兩個可能是空葉子。
⑦ 為什麼treeset使用紅黑樹而一些資料庫索引使用b樹和b+樹
為什麼treeset使用紅黑樹而一些資料庫索引使用b樹和b+樹
在C++
STL中，很多部分(目前包括set,
multiset,
map,
multimap)應用了紅黑樹的變體(SGI
STL中的紅黑樹有一些變化，這些修改提供了更好的性能，以及對set操作的支持)。紅黑樹是每個節點都帶有顏色屬性的二叉查找樹，顏色或紅色或黑色。
⑧ 紅黑樹的術語
紅黑樹是一種特定類型的二叉樹，它是在計算機科學中用來組織數據比如數字的塊的一種結構。所有數據塊都存儲在節點中。這些節點中的某一個節點總是擔當起始位置的功能，它不是任何節點的兒子，我們稱之為根節點或根。它有最多兩個兒子，都是它連接到的其他節點。所有這些兒子都可以有自己的兒子，以此類推。這樣根節點就有了把它連接到在樹中任何其他節點的路徑。
如果一個節點沒有兒子，我們稱之為葉子節點，因為在直覺上它是在樹的邊緣上。子樹是從特定節點可以延伸到的樹的某一部分，其自身被當作一個樹。在紅黑樹中，葉子被假定為 null 或空。
由於紅黑樹也是二叉查找樹，它們當中每一個節點的比較值都必須大於或等於在它的左子樹中的所有節點，並且小於或等於在它的右子樹中的所有節點。這確保紅黑樹運作時能夠快速的在樹中查找給定的值。
⑨ 紅黑樹和平衡二叉樹 區別
紅黑樹和平衡二叉樹的主要區別如下：
平衡二叉樹（AVL）樹是嚴格的平衡二叉樹，平衡條件必須滿足（所有節點的左右子樹高度差不超過1）。不管我們是執行插入還是刪除操作，只要不滿足上面的條件，就要通過旋轉來保持平衡，而的英文旋轉非常耗時的。所以平衡二叉樹（AVL）適合用於插入與刪除次數比較少，但查找多的情況。
紅黑樹在二叉查找樹的基礎上增加了著色和相關的性質使得紅黑樹相對平衡，從而保證了紅黑樹的查找、插入、刪除的時間復雜度最壞為O(log
n)。所以紅黑樹適用於搜索，插入，刪除操作較多的情況。
(9)紅黑樹查找節點存儲類型擴展閱讀：
平衡二叉樹在Windows
NT內核中廣泛存在。
紅黑樹的應用：
1、在C
++的STL中，地圖和集都是用紅黑樹實現的；
2、著名的Linux的的進程調度完全公平調度程序，用紅黑樹管理進程式控制制塊，進程的虛擬內存區域都存儲在一顆紅黑樹上，每個虛擬地址區域都對應紅黑樹的一個節點，左指針指向相鄰的地址虛擬存儲區域，右指針指向相鄰的高地址虛擬地址空間；
3、IO多路復用的epoll的的的實現採用紅黑樹組織管理的sockfd，以支持快速的增刪改查；
4、Nginx的的的中用紅黑樹管理定時器，因為紅黑樹是有序的，可以很快的得到距離當前最小的定時器；
5、Java中的TreeMap中的實現。
參考資料：
網路-平衡二叉樹
網路-紅黑樹
⑩ 關於演算法導論
概念：
紅黑樹是一種自平衡二叉查找樹，是在計算機科學中用到的一種數據結構，典型的用途是實現關聯數組。它是在1972年由Rudolf Bayer發明的，他稱之為"對稱二叉B樹"，它現代的名字是在 Leo J. Guibas 和 Robert Sedgewick 於1978年寫的一篇論文中獲得的。它是復雜的，但它的操作有著良好的最壞情況運行時間，並且在實踐中是高效的: 它可以在O(log n)時間內做查找，插入和刪除，這里的n 是樹中元素的數目。
紅黑樹是一種很有意思的平衡檢索樹。它的統計性能要好於平衡二叉樹(有些書籍根據作者姓名，Adelson-Velskii和Landis，將其稱為AVL-樹)，因此，紅黑樹在很多地方都有應用。在C++ STL中，很多部分(目前包括set, multiset, map, multimap)應用了紅黑樹的變體(SGI STL中的紅黑樹有一些變化，這些修改提供了更好的性能，以及對set操作的支持)。
背景和術語：
紅黑樹是一種特定類型的二叉樹，它是在計算機科學中用來組織數據比如數字的塊的一種結構。所有數據塊都存儲在節點中。這些節點中的某一個節點總是擔當啟始位置的功能，它不是任何節點的兒子；我們稱之為根節點或根。它有最多兩個"兒子"，都是它連接到的其他節點。所有這些兒子都可以有自己的兒子，以此類推。這樣根節點就有了把它連接到在樹中任何其他節點的路徑。
如果一個節點沒有兒子，我們稱之為葉子節點，因為在直覺上它是在樹的邊緣上。子樹是從特定節點可以延伸到的樹的某一部分，其自身被當作一個樹。在紅黑樹中，葉子被假定為 null 或空。
由於紅黑樹也是二叉查找樹，它們當中每一個節點都的比較值都必須大於或等於在它的左子樹中的所有節點，並且小於或等於在它的右子樹中的所有節點。這確保紅黑樹運作時能夠快速的在樹中查找給定的值。
用途和好處：
紅黑樹和AVL樹一樣都對插入時間、刪除時間和查找時間提供了最好可能的最壞情況擔保。這不只是使它們在時間敏感的應用如即時應用(real time application)中有價值，而且使它們有在提供最壞情況擔保的其他數據結構中作為建造板塊的價值；例如，在計算幾何中使用的很多數據結構都可以基於紅黑樹。
紅黑樹在函數式編程中也特別有用，在這里它們是最常用的持久數據結構之一，它們用來構造關聯數組和集合，在突變之後它們能保持為以前的版本。除了O(log n)的時間之外，紅黑樹的持久版本對每次插入或刪除需要O(log n)的空間。
紅黑樹是 2-3-4樹的一種等同。換句話說，對於每個 2-3-4 樹，都存在至少一個數據元素是同樣次序的紅黑樹。在 2-3-4 樹上的插入和刪除操作也等同於在紅黑樹中顏色翻轉和旋轉。這使得 2-3-4 樹成為理解紅黑樹背後的邏輯的重要工具，這也是很多介紹演算法的教科書在紅黑樹之前介紹 2-3-4 樹的原因，盡管 2-3-4 樹在實踐中不經常使用。
屬性：
紅黑樹是每個節點都有顏色特性的二叉查找樹，顏色的值是紅色或黑色之一。除了二叉查找樹帶有的一般要求，我們對任何有效的紅黑樹加以如下增補要求:
1.節點是紅色或黑色。
2.根是黑色。
3.每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)
4.從每個葉子到根的所有路徑都包含相同數目的黑色節點。
這些約束強制了紅黑樹的關鍵屬性: 從根到葉子的最長的可能路徑不大於最短的可能路徑的兩倍長。結果是這個樹大致上是平衡的。因為操作比如插入、刪除和查找某個值都要求與樹的高度成比例的最壞情況時間，這個在高度上的理論上限允許紅黑樹在最壞情況下都是高效的，而不同於普通的二叉查找樹。
在很多樹數據結構的表示中，一個節點有可能只有一個兒子，而葉子節點包含數據。用這種範例表示紅黑樹是可能的，但是這會改變一些屬性並使演算法復雜。為此，本文中我們使用 "null 葉子" 或"空(null)葉子"，如上圖所示，它不包含數據而只充當樹在此結束的指示。這些節點在繪圖中經常被省略，導致了這些樹好像同上述原則相矛盾，而實際上不是這樣。與此有關的結論是所有節點都有兩個兒子，盡管其中的一個或兩個可能是空葉子。
操作：
在紅黑樹上只讀操作不需要對用於二叉查找樹的操作做出修改，因為它也二叉查找樹。但是，在插入和刪除之後，紅黑屬性可能變得違規。恢復紅黑屬性需要少量(O(log n))的顏色變更(這在實踐中是非常快速的)並且不超過三次樹旋轉(對於插入是兩次)。這允許插入和刪除保持為 O(log n) 次，但是它導致了非常復雜的操作。