平衡樹--treap=tree+heap-創(chuàng)新互聯(lián)

平時常用的平衡樹操作：

1.插入

目前創(chuàng)新互聯(lián)公司已為1000+的企業(yè)提供了網(wǎng)站建設(shè)、域名、虛擬主機、網(wǎng)站托管維護、企業(yè)網(wǎng)站設(shè)計、廣水網(wǎng)站維護等服務(wù)，公司將堅持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。

2.刪除

3.找前驅(qū)/后繼（找某個值的前驅(qū)后繼，首先得找到該值（如果該值不存在也談不上找前驅(qū)后繼））

4.找大值/最小值

5.求某個值的排名

6.求排名是k的數(shù)是哪個

7.比某個數(shù)小的大值

8.比某個數(shù)大的最小值

其中，前4個，C++STL中的set已經(jīng)幫實現(xiàn)了，如果遇到只有這幾種操作的話可以用set就行。

分別對應(yīng)set中的

1.insert()

2.erease()

3.++, --

4.begin(), end() - 1

    • 普通平衡樹? ?https://ac.nowcoder.com/acm/contest/1036/A??

ac代碼：

#include#define endl '\n'
using namespace std;
const int INF = 0x3f3f3f3f;
struct Node{
  int l, r;
  int key, val;
  int cnt, size;
}tr[100005]; // 最多有1e5個結(jié)點，idx表示結(jié)點編號
int root, idx;
void pushup(int p){ // 當(dāng)前父節(jié)點存儲的節(jié)點個數(shù) = 左右兒子結(jié)點數(shù) + 本節(jié)點的數(shù)量
  tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + tr[p].cnt;
}
int create_node(int key){ // 創(chuàng)建結(jié)點
  tr[++ idx].key = key; // 關(guān)鍵字
  tr[idx].val = rand(); // 要把整棵樹弄成隨機的高度，降低樹的平均高度，降低查找次數(shù)為logn
  tr[idx].cnt = tr[idx].size = 1; //當(dāng)前葉結(jié)點數(shù)量為1， 所存儲的子節(jié)點數(shù)size也為1
  return idx;
}
void build(){// 建樹
  create_node(-INF); //添加兩個哨兵，負無窮和正無窮。正無窮在右兒子
  create_node(INF);
  root = 1, tr[1].r = 2;
  pushup(root); // 更新根節(jié)點所存儲的size子節(jié)點個數(shù)
}
void zig(int &p){//右旋
  int q = tr[p].l;
  tr[p].l = tr[q].r, tr[q].r = p, p = q;
  pushup(tr[p].r);
  pushup(p);
}
void zag(int &p){//左旋
  int q = tr[p].r;
  tr[p].r = tr[q].l, tr[q].l = p, p = q;
  pushup(tr[p].l);
  pushup(p);
}
void insert(int &p, int key){
  if(!p) p = create_node(key);
  else if(tr[p].key == key) tr[p].cnt ++;
  else if(tr[p].key >key){
    insert(tr[p].l, key);
    if(tr[tr[p].l].val >tr[p].val) zig(p);//右旋
  }else if(tr[p].key< key){
    insert(tr[p].r, key);
    if(tr[tr[p].r].val >tr[p].val) zag(p);//左旋
  }
  pushup(p);
}
void remove(int &p, int key){
  if(!p) return;
  if(tr[p].key == key){
    if(tr[p].cnt >1 ) tr[p].cnt --;
    else if(tr[p].l || tr[p].r){
      if(!tr[p].r || tr[tr[p].l].val >tr[tr[p].r].val){
        zig(p);
        remove(tr[p].r, key);
      }else{
        zag(p);
        remove(tr[p].l, key);
      }
    }else p = 0;
  }
  else if(tr[p].key >key) remove(tr[p].l, key);
  else remove(tr[p].r, key);
  
  pushup(p);
}
int get_rank_by_key(int p, int key){
  if(!p) return 0;
  if(tr[p].key == key) return tr[tr[p].l].size + 1;
  if(tr[p].key >key) return get_rank_by_key(tr[p].l, key);
  return tr[tr[p].l].size + tr[p].cnt + get_rank_by_key(tr[p].r, key);
}
int get_key_by_rank(int p, int rank){
  if(!p) return INF;
  if(tr[tr[p].l].size >= rank) return get_key_by_rank(tr[p].l, rank);
  if(tr[tr[p].l].size + tr[p].cnt >= rank) return tr[p].key;
  return get_key_by_rank(tr[p].r, rank - tr[tr[p].l].size - tr[p].cnt);
}
int get_prev(int p, int key){
  if(!p) return -INF;
  if(tr[p].key >= key) return get_prev(tr[p].l, key);
  return max(tr[p].key, get_prev(tr[p].r, key));
}
int get_next(int p, int key){
  if(!p) return INF;
  if(tr[p].key<= key) return get_next(tr[p].r, key);
  return min(tr[p].key, get_next(tr[p].l, key));
}
int main(){
  cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
  int t;
  build();
  cin >>t;
  while(t--){
    int op, x;
    cin >>op >>x;
    if(op == 1) insert(root, x);
    else if(op == 2) remove(root, x);
    else if(op == 3) cout<< get_rank_by_key(root, x) - 1<< endl;
    else if(op == 4) cout<< get_key_by_rank(root, x + 1)<< endl;
    else if(op == 5) cout<< get_prev(root, x)<< endl;
    else cout<< get_next(root, x)<< endl;
  }
  return 0;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站標題：平衡樹--treap=tree+heap-創(chuàng)新互聯(lián)
標題鏈接：http://muchs.cn/article28/dddgcp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站建設(shè)、全網(wǎng)營銷推廣、外貿(mào)網(wǎng)站建設(shè)、外貿(mào)建站、ChatGPT、微信公眾號

廣告

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

成都網(wǎng)頁設(shè)計公司