版權所有，轉載請注明出處，謝謝！
http://blog.csdn.net/silangquan/article/details/18655795

創新互聯建站專業為企業提供黎川網站建設、黎川做網站、黎川網站設計、黎川網站制作等企業網站建設、網頁設計與制作、黎川企業網站模板建站服務，十載黎川做網站經驗，不只是建網站，更提供有價值的思路和整體網絡服務。

  連續兩次面試都問到了紅黑樹，關鍵兩次都沒有答好，這次就完整地來學習整理一下。

沒有學習過紅黑樹的同學請參考：

<<Introduction to Algorithms>> Chapter 13 Red-Black Trees Chapter 14 Augmenting Data Structures

教你透徹了解紅黑樹

1.stl中的set底層用的什么數據結構？

2.紅黑樹的數據結構怎么定義的？

3.紅黑樹有哪些性質？

4.紅黑樹的各種操作的時間復雜度是多少？

5.紅黑樹相比于BST和AVL樹有什么優點？

6.紅黑樹相對于哈希表，在選擇使用的時候有什么依據？

7.如何擴展紅黑樹來獲得比某個結點小的元素有多少個？

8.擴展數據結構有什么步驟？

詳細解答

1.stl中的set底層用的什么數據結構？

紅黑樹

2.紅黑樹的數據結構怎么定義？

enum Color {           RED = 0,           BLACK = 1 };  struct RBTreeNode {            struct RBTreeNode*left, *right, *parent;            int   key;            int data;            Color color; };

3.紅黑樹有哪些性質？

一般的，紅黑樹，滿足以下性質，即只有滿足以下全部性質的樹，我們才稱之為紅黑樹：
1）每個結點要么是紅的，要么是黑的。
2）根結點是黑的。
3）每個葉結點（葉結點即指樹尾端NIL指針或NULL結點）是黑的。
4）如果一個結點是紅的，那么它的倆個兒子都是黑的。
5）對于任一結點而言，其到葉結點樹尾端NIL指針的每一條路徑都包含相同數目的黑結點。

4.紅黑樹的各種操作的時間復雜度是多少？

能保證在最壞情況下，基本的動態幾何操作的時間均為O（lgn）

5.紅黑樹相比于BST和AVL樹有什么優點？

紅黑樹是犧牲了嚴格的高度平衡的優越條件為代價，它只要求部分地達到平衡要求，降低了對旋轉的要求，從而提高了性能。紅黑樹能夠以O(log2 n)的時間復雜度進行搜索、插入、刪除操作。此外，由于它的設計，任何不平衡都會在三次旋轉之內解決。當然，還有一些更好的，但實現起來更復雜的數據結構能夠做到一步旋轉之內達到平衡，但紅黑樹能夠給我們一個比較“便宜”的解決方案。

相比于BST，因為紅黑樹可以能確保樹的最長路徑不大于兩倍的最短路徑的長度，所以可以看出它的查找效果是有最低保證的。在最壞的情況下也可以保證O(logN)的，這是要好于二叉查找樹的。因為二叉查找樹最壞情況可以讓查找達到O(N)。

紅黑樹的算法時間復雜度和AVL相同，但統計性能比AVL樹更高，所以在插入和刪除中所做的后期維護操作肯定會比紅黑樹要耗時好多，但是他們的查找效率都是O(logN)，所以紅黑樹應用還是高于AVL樹的. 實際上插入 AVL 樹和紅黑樹的速度取決于你所插入的數據.如果你的數據分布較好,則比較宜于采用 AVL樹(例如隨機產生系列數),但是如果你想處理比較雜亂的情況,則紅黑樹是比較快的

6.紅黑樹相對于哈希表，在選擇使用的時候有什么依據？

權衡三個因素: 查找速度, 數據量, 內存使用，可擴展性。
總體來說，hash查找速度會比map快，而且查找速度基本和數據量大小無關，屬于常數級別;而map的查找速度是log(n)級別。并不一定常數就比log(n) 小，hash還有hash函數的耗時，明白了吧，如果你考慮效率，特別是在元素達到一定數量級時，考慮考慮hash。但若你對內存使用特別嚴格， 希望程序盡可能少消耗內存，那么一定要小心，hash可能會讓你陷入尷尬，特別是當你的hash對象特別多時，你就更無法控制了，而且 hash的構造速度較慢。

紅黑樹并不適應所有應用樹的領域。如果數據基本上是靜態的，那么讓他們待在他們能夠插入，并且不影響平衡的地方會具有更好的性能。如果數據完全是靜態的，例如，做一個哈希表，性能可能會更好一些。

在實際的系統中，例如，需要使用動態規則的防火墻系統，使用紅黑樹而不是散列表被實踐證明具有更好的伸縮性。Linux內核在管理vm_area_struct時就是采用了紅黑樹來維護內存塊的。

紅黑樹通過擴展節點域可以在不改變時間復雜度的情況下得到結點的秩。

7.如何擴展紅黑樹來獲得比某個結點小的元素有多少個？

這其實就是求節點元素的順序統計量，當然任意的順序統計量都可以需要在O(lgn)時間內確定。

在每個節點添加一個size域，表示以結點 x 為根的子樹的結點樹的大小，則有

size[x] = size[[left[x]] + size [right[x]] + 1;

這時候紅黑樹就變成了一棵順序統計樹。

利用size域可以做兩件事：

1). 找到樹中第i小的結點；

OS-SELECT(x;,i) r = size[left[x]] + 1; if i == r      return x elseif i < r      return OS-SELECT(left[x], i) else return OS-SELECT(right[x],  i)

思路：size[left[x]]表示在對x為根的子樹進行中序遍歷時排在x之前的個數，遞歸調用的深度不會超過O(lgn);

2).確定某個結點之前有多少個結點，也就是我們要解決的問題；

OS-RANK(T,x) r = x.left.size + 1; y = x; while y != T.root          if y == y.p.right                  r = r + y.p.left.size +1          y = y.p return r

思路：x的秩可以視為在對樹的中序遍歷種，排在x之前的結點個數加上一。最壞情況下，OS-RANK運行時間與樹高成正比，所以為O (lgn).

8.擴展數據結構有什么步驟？

1).選擇基礎數據結構；

2).確定要在基礎數據結構種添加哪些信息；

3).驗證可用基礎數據結構上的基本修改操作來維護這些新添加的信息；

4).設計新的操作。

另外有需要云服務器可以了解下創新互聯scvps.cn，海內外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業上云的綜合解決方案，具有“安全穩定、簡單易用、服務可用性高、性價比高”等特點與優勢，專為企業上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。

網站欄目：劍指XX游戲(六)-輕松搞定面試中的紅黑樹問題-創新互聯
本文鏈接：http://vcdvsql.cn/article44/deocee.html

成都網站建設公司_創新互聯，為您提供軟件開發、企業建站、品牌網站建設、網站設計公司、動態網站、標簽優化

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯