C++ 如何實現平衡的名次樹？

如何最方便的實現，對一棵平衡二叉樹，進行動態的插入，刪除，選擇第k小的key，查詢一個key的rank？

除了用Treap的模板，能不能用C++ STL中的數據結構或者某些變形來實現這個功能？

GCC的Policy-based data structures里自帶: Chapter 22. Policy-Based Data Structures

#include &
#include &
#include &
#include &

cout &<&< "order of 7: " &<&< t.order_of_key(7) &<&< endl; cout &<&< "order of 8: " &<&< t.order_of_key(8) &<&< endl; cout &<&< "order of 1: " &<&< t.order_of_key(1) &<&< endl; cout &<&< "key of rank 5: " &<&< *t.find_by_order(5) &<&< endl; return 0; }

輸出

order of 7: 4
order of 8: 5
order of 1: 0
key of rank 5: 9


另外PBDS里有很多其他有趣的東西，例如thin heap，pairing heap等，不妨看看。

據我所知，不能用STL。

@菜魚ftfish 你說的對

正確答案，使用Order statistic tree

簡單介紹一下：

要讓一棵平衡二叉樹變成一顆order statistic tree，每個節點需要多存儲一個信息：

就是這個當前節點下以此節點為根的子樹的節點數目

演算法原理是這樣的，（非常簡單）

function Select(t, k)
// Returns the k"th element (zero-indexed) of the elements in t
r ← size[left[t]]
if k = r
return key[t]
else if k &< r return Select(left[t], k) else return Select(right[t], k - (r + 1))

如果左子樹剛好k個節點呢，這說明根節點就是我們要找的值，因為根據BST的性質，它的左子樹都比它小，又有k-1個，所以根正好是第k小。

如果左子樹的節點數多於k個呢，說明這個第k小肯定在左邊，因為根據BST的性質，左子樹都比根小，那麼我們遞歸的查找左子樹

如果左子樹的節點數不夠k呢，說明這個第k小肯定在右邊，因為根據BST的性質，左子樹那些節點都要比右子樹的小，所以呢肯定在右邊，就是右邊第 k-r+1小，那麼我們遞歸的查找右子樹。

這樣第k小只需O(logn)就可以找到了。

然後插入/查找/刪除這些都是普通的紅黑樹/AVL咯。

然後才發現題主問了rank（汗）

所謂的rank就是樹節點的index唄

order stats tree 一樣能做：

function Rank(T, x)
// Returns the position of x (one-indexed) in the linear sorted list of elements of the tree T
r ← size[left[x]] + 1
y ← x
while y ≠ T.root
if y = right[y.p]
r ← r + size[left[y.p]] + 1
y ← y.p
return r


求x的rank就是算一個節點前面有多少個節點

如果這個節點就是整個根節點，那麼就是他左子樹的個數

如果這個節點不是根節點，那麼如果它位於左邊子樹上，我們不用管

如果它位於右邊子樹上，那麼我們要統計它父節點左邊子樹有多少個，如果父節點還在一顆右子樹上我們還要這樣算下去，直到根節點

原答案（慢多了）

----------------------------------------------------------------------------------------

第k小問題用堆唄。

刪除第K小：

用斐波那楔堆，取k-1次最小值建一個新斐波那楔堆，然後刪掉第k個在合併，總共時間複雜度度是 k次取最小 O(klogn) + k-1次 insert：O(k-1) + 1次合併 O(1) = O(klog n+k) = O(klog n) （均攤） 最差k=n O(nlogn)

返回第K小：上面那個稍微改改就有了。。。

樹節點裡可以再存個到堆的refer，這樣刪除樹中節點的時候就免除從堆中搜索的問題了，利用樹進行高效的搜索。

刪除：樹查找O(logn) + 斐波那楔堆刪除O(logn) + 樹刪除(假設stl map) O(logn) 所以還是O(logn)

插入：斐波那楔堆插入O(1) +樹插入O(logn)

查找：樹查找O(logn)

@菜魚ftfish 提到的pbds是科學的做法。我在搞OI的時候還知道一個不那麼科學的做法(方法非原創，代碼是我寫的)：

template&
struct RBtree{
#define l _M_left
#define r _M_right
#define p _M_parent
#define node _Rb_tree_node_base
#define key _M_value_field.first
#define size _M_value_field.second
typedef _Rb_tree_node& &> Node; map& M;
void fix_size(node *it){
int it_size=static_cast&(it)-&>size;it_size=1;
if(it-&>l)it_size+=static_cast&(it-&>l)-&>size;
if(it-&>r)it_size+=static_cast&(it-&>r)-&>size;
}
void fix_all(node *it,node *end){
for (;;it=it-&>p){
if (it-&>l)fix_size(it-&>l);if (it-&>r)fix_size(it-&>r);
if (it-&>p==end){fix_size(it);break;}
}
}
void insert(const T x){
pair&::iterator,bool&> fit=M.insert(make_pair(x,0));
if(!fit.second)return;
fix_all(fit.first._M_node,M.end()._M_node);
}
int findkth(int k){
node *x=get_root();
while (k){
int sizel=x-&>l?static_cast&(x-&>l)-&>size:0;
if (k==sizel+1)break;
if (k&<=sizel)x=x-&>l;
else k-=sizel+1,x=x-&>r;
}
return static_cast&(x)-&>key;
}
node *get_root(){
node *it=M.begin()._M_node;
while(it-&>p!=M.end()._M_node)it=it-&>p;
return it;
}
void print(){print_node(get_root(),"");}
void print_node(const node *it,string str){
if(!it){cout&<&(it)-&>key;
cout&<&<"("&<&(it)-&>size&<&<")"&<&l,str+" ");print_node(it-&>r,str+" ");
}
#undef l
#undef r
#undef p
#undef node
#undef key
#undef size
};
RBtree& a;


原理是手動給STL的紅黑樹增加維護size的功能。

對 @Howard Curry 的觀點我是基本贊同的。但是這個(較為麻煩)的做法算是繞過了封裝問題。

樓上提到了樹狀數組。補一個求第k小O(log n)的做法：

int findkth(int k){
int ans=0,cnt=0;
for (int i=20;i&>=0;--i){
ans+=1&<&=n||cnt+c[ans]&>=k)ans-=1&<&