平衡樹不好打?試試Trie字典樹！
Woc,考場(面試)忘記打平衡樹怎麼辦,Trie救你命
文本只發佈於部落格園,其他地方出現本文均是未經許可的盜版。
演算法導入
眾所周知平衡樹很難打(大佬除外),還老是調錯。萬一這種事情發生在關鍵時刻你就GG了。那我們怎麼辦呢？
從本質上介紹,平衡樹作用就是維護一個有序的序列(關係)。很多操作我們用vector(數組)+lower_bound(二分查找),都可以實現。但是vector插入不便,導致序列維護不便。如果用list(鏈表)代替vector,那麼查找又很慢。怎麼辦呢？
考慮到我們一般都是維護一個整數的排序，那麼我能不能找到一種支援動態排序的數據結構。堆可以進行動態處理，但是只有第一個是有序的，他的子節點只能滿足比他小(大)。
難道除了平衡樹我們就沒有別的方法了嗎？答案是有的。看看下面的樹。
Root–>A[“0”]
Root–>B[“1”]
A[“0”]–>C[“0”]
A[“0”]–>D[“1”]
B[“1”]–>E[“0”]
B[“1”]–>F[“1”]
C[“0”].->G[“0”]
D[“1”].->H[“1”]
E[“0”].->I[“2”]
F[“1”].->K[“3”]
這不是01Trie(字典樹)嗎？這能當平衡樹？？？？
別急，仔細看看。
這個Trie是不是左子樹小於右子樹？
好像是啊
再想想為什麼？
應該是二進位關係,左邊的節點當前這一位是0,後面更小的位再大,也不可能比當前這一位是1的大了。
沒錯
你再想想，Trie字典樹是不是可以動態插入？
好像是
所以我們可以利用這種關係實現平衡了。甚至我們還能很簡單的實現可持久化。
但是不難看出有幾個缺點。
-
空間要比一般平衡樹大，一個int32最壞情況需要32個int32去記錄他。當然實際情況也不可能都是這樣。實際運用中有許多的重複節點，可以重複利用的。知道數字範圍的時候也能調整樹高解決。在一道平衡樹的模板題，記憶體是FHQ_Treap的1.7倍,速度更快，記憶體是Splay的2/3，速度差不多。是紅黑樹的4/5，速度是1/2。
-
不能直接輸入負數(除非你建樹的時候把符號位也建立進去，不過這樣你也不好解決大小查找，畢竟負數是補碼，情況和正數相反)。你需要加一個比較大的數值使得負數變為正數。
-
不能進行序列操作(不過支援這個操作的平衡樹也不多)。
當然直接用Trie也不行，你還需要維護幾個資訊,否則你沒法實現一些功能。
你需要維護
- 每個節點對應子樹大小
- 每個葉子節點的值的數量(為了支援重複值插入)
程式碼實現
提前定義
這裡我定義樹高為25層
const int MAXLOG=25;
節點資訊
需要保存兩個兒子，節點子樹大小，葉子節點計數
程式碼如下
struct node
{
int ch[2];
int sze, cnt;
} Tree[MAXLOG];
int p; //模擬一個記憶體池,這是對應的頂。
插入&刪除 操作
插入操作其實和一般樹沒什麼區別，唯一不同的地方就是你需要維護節點的sze和cnt資訊。
刪除操作和插入操作其實一樣，區別就是一個做加法，一個做減法。
程式碼如下
void updata(int x, int offset) // 插入/刪除 offset個x,插入正,刪除負
{
int now = 0; //0是根
for (int i = MAXLOG - 1; i >= 0; i--)
{
bool now_bit = (x & (1 << i) != 0); //第i位的數值
if (!Tree[now].ch[now_bit] == 0) //指向空,需要分配子節點
Tree[now].ch[now_bit] = ++p;
now = Tree[now].ch[now_bit];
Tree[now].sze += offset; //這條子樹鏈上的節點都需要
}
Tree[now].cnt += offset; //跑到葉子節點了
}
數取排名
程式碼也是比較簡單,就是注意當節點為NULL的時候就可以退出了。
int get_rank(int x) //獲取比x小的數的數量,不包括本身
{
int now = 0; //0是根
int ans = 0;
for (int i = MAXLOG - 1; i >= 0; i--)
{
bool now_bit = ((x & (1 << i)) != 0); //第i位的數值
if (now_bit == 1) //處於大的那一邊
ans += Tree[Tree[now].ch[0]].sze; //把比自己小的那些加上
now = Tree[now].ch[now_bit];
if (now == 0) //別忘了,這裡的0是空的意思
break;
}
return ans;
}
排名取數
int get_kth(int k) //通過排名大小
{
int now = 0; //0是根
int ans = 0;
for (int i = MAXLOG - 1; i >= 0; i--)
{
int temp = Tree[Tree[now].ch[0]].sze; //看看自己前面有多少
if (k <= temp) //還在更前面
now = Tree[now].ch[0];
else //在自己後面
{
k -= temp; //更新相對在右子樹的位置
now = Tree[now].ch[1];
ans |= (1 << i); //可以確定這一位是1
}
if (now == 0) //別忘了,這裡的0是空的意思
break;
}
return ans;
}
求前驅&後繼
這個也是草雞簡單
int pre(int x)
{
return get_kth(get_rank(x));
}
int nxt(int x)
{
return get_kth(get_rank(x + 1) + 1);
}
更多
由於這個樹是基於Trie的,Trie能可持久化,這個也能。不過可持久化我們以後再講。
完整程式碼下載地址://files.cnblogs.com/files/blogs/694685/TrieBST.7z
