[算法]紅黑樹

一.《算法導論》 chapter 13

1.總述

一種很好的“平衡”二叉搜尋樹；

近乎平衡，沒有一條路徑的長度是其他路徑的2倍；

最壞情況下，基本動态集合操作(search,insert,delete等)的時間複雜度是O(lgn)

2.紅黑樹滿足條件 --定義

 紅色r,黑色b

1.每個節點r/b；

2.根節點b;

3.所有葉子b;

4.若一個節點r,則其2各子節點b;

5.從每個節點到葉子節點，路徑上包含相同數量的b

3.高度

黑高（black-height）;

一棵有n個内部節點的紅黑樹，高度至多為2lg(n+1)

4.基本動态操作

略，詳見書

二.在C++ STL的應用

set、map、multiset、multimap的内部都是由紅黑樹實作，預設是從小到達排序。

例如：

set<int> leastNumbers; //小頂堆

set<int, greater<int>> largeNumbers; //大頂堆

三.題目：《劍指offer》最小的k個數