程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 平衡二叉查找樹

平衡二叉查找樹

編輯:關於C語言

  既Size Balanced Tree。

  左旋 右旋 維護 : 這個比較容易理解,《Size Balanced Tree》對維護操作的復雜度分析是均攤O(1),優美

  插入:普通BST插入,進行樹形狀的調整

  刪除:用BST的刪除方法,要找到刪除節點的最小關鍵字或最大關鍵字,來進行替換。

  代碼

  1 #include <algorithm>

  2 #include <cstdio>

  3 using namespace std;

  4

  5 const int maxn = 100005;

  6  int NEW = 0, n, m;

  7 int size[maxn], left[maxn], right[maxn], key[maxn];

  8 int val[maxn];

  9

  10 void Left_Rotate(int &x) {

  11     int k = right[x];

  12     right[x] = left[k];

  13     left[k] = x;

  14     size[k] = size[x];

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

  16     x = k;

  17 }

  18

  19 void Right_Rotate(int &x) {

  20     int k = left[x];

  21     left[x] = right[k];

  22     right[k] = x;

  23     size[k] = size[x];

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

  25     x = k;

  26 }

  27

  28 void Maintain(int &x, bool Right) {

  29     if(!x) return ;

  30     if(!Right) {

  31         if(size[ left[ left[x] ] ] > size[ right[x] ])

  32             Right_Rotate(x);

  33         else if(size[ right[ left[x] ] ] > size[ right[x] ])

  34             Left_Rotate( left[x] ) , Right_Rotate(x);

  35         else

  36             return ;

  37     } else {

  38         if(size[ right[ right[x] ] ] > size[ left[x] ])

  39             Left_Rotate(x);

  40         else if(size[ left[ right[x] ] ] > size[ left[x] ])

  41             Right_Rotate( right[x] ) , Left_Rotate(x);

  42         else

  43             return ;

  44     }

  45     Maintain(left[x] , false);

  46     Maintain(right[x] , true);

  47     Maintain(x , false);

  48     Maintain(x , true);

  49 }

  50

  51 void insert(int &x, int delta) {

  52     if(!x) {

  53         x = ++ NEW;

  54         size[x] = 1;

  55         key[x] = delta;

  56     } else {

  57         size[x] ++;

  58         if(key[x] > delta)

  59             insert(left[x] , delta);

  60         else

  61             insert(right[x] , delta);

  62         Maintain(x , delta >= key[x]);

  63     }

  64 }

  65

  66 int Delete(int &x, int delta)

  67 {

  68     if(!x) return 0;

  69     size[x] --;

  70     if(delta == key[x] || (delta < key[x] && !left[x]) || (delta > key[x] && !right[x]) )

  71     {

  72         if(left[x] && right[x]) {

  73             int p = Delete(left[x] , delta + 1);

  74             key[x] = key[p];

  75             return p;

  76         } else {

  77             int p = x;

  78             x = left[x] + right[x];

  79             return p;

  80         }

  81     } else {

  82         if(delta < key[x])

  83             Delete(left[x] , delta);

  84         else

  85             Delete(right[x] , delta);

  86     }

  87 }

  88

  89

  90 int select_max(int &x, int k)

  91 {

  92     if(!x) return -1;

  93     int r = size[ right[x] ] + 1;

  94     if(r < k)

  95         select_max(left[x] , k - r);

  96     else if(r > k)

  97         select_max(right[x] , k);

  98     else

  99         return key[x];

  100 }

  101

  102 int select_min(int &x, int k) {

  103     if(!x) return -1;

  104     int l = size[ left[x] ] + 1;

  105     if(l < k)

  106         select_min(right[x] , k - l);

  107     else if(l > k)

  108         select_min(left[x] , k);

  109     else

  110         return key[x];

  111 }

  112

  113 int ans[maxn];

  114 struct NODE { int u, v, k, id; } A[maxn];

  115

  116 bool operator < (const NODE x, const NODE y)

  117 {

  118     if(x.u == y.u)

  119         return x.v < y.v;

  120     return x.u < y.u;

  121 }

  122

  123 int main()

  124 {

  125     NEW = 0;

  126     scanf("%d %d", &n, &m);

  127     int root = 0;

  128

  129     for(int i=1; i

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved