文章目錄
- 零、寫在前面
- 一、AVL 樹定義
- 1.1 性質
- 1.2 樹高的證明
- 二、AVL樹實現(AVL樹實現名次樹)
- 2.1 節點定義
- 2.2 左/右旋轉
- 2.3 zig-zag / zag-zig 雙旋
- 2.4 重平衡函數
- 2.5 插入
- 2.6 刪除
- 2.7 排名查詢
- 2.8 查前驅/后繼
- 2.9 查第 k 小
- 2.10 完整代碼
- 三、online judge 驗證
- 3.1 P6136 【模板】普通平衡樹(數據加強版)
零、寫在前面
大二學數據結構的時候寫的AVL代碼稀爛,回過頭來重制一下,在不使用父指針的情況下以較為簡潔的代碼實現AVL。
只是為了方便自己快速復習下AVL樹原理,不作過多原理說明,詳見:AVL樹詳解[C++]
一、AVL 樹定義
AVL 樹 是一種平衡二叉搜索樹,由兩位俄羅斯的數學家 G.M.Adelson-Velskii 和 E.M.Landis 在1962年發明,并以他們名字的首字母命名。
1.1 性質
- 空二叉樹是一個 AVL 樹
- 如果 T 是一棵 AVL 樹,那么其左右子樹也是 AVL 樹,并且 |height(lc) - height(rc) <= 1|,h 是其左右子樹的高度
- 樹高為 O(logn)
平衡因子:左子樹高度 - 右子樹高度
1.2 樹高的證明
設 f n 為高度為 n 的 A V L 樹所包含的最少節點數,則有 f n = { 1 ( n = 1 ) 2 ( n = 2 ) f n ? 1 + f n ? 2 + 1 ( n > 2 ) 根據常系數非齊次線性差分方程的解法 ( 或者對轉移矩陣求特征向量并相似對角化 ) , { f n + 1 } 是一個斐波那契數列。這里 f n 的通項為: f n = 5 + 2 5 5 ( 1 + 5 2 ) n + 5 ? 2 5 5 ( 1 ? 5 2 ) n ? 1 斐波那契數列以指數的速度增長,對于樹高 n 有: n < log ? 1 + 5 2 ( f n + 1 ) < 3 2 log ? 2 ( f n + 1 ) 因此 A V L 樹的高度為 O ( log ? f n ) ,這里的 f n 為結點數。 設 f_{n} 為高度為 n 的 AVL 樹所包含的最少節點數,則有 \\ f_{n}=\left\{\begin{array}{ll} 1 & (n=1) \\ 2 & (n=2) \\ f_{n-1}+f_{n-2}+1 & (n>2) \end{array}\right. \\ 根據常系數非齊次線性差分方程的解法(或者對轉移矩陣求特征向量并相似對角化), \left\{f_{n}+1\right\} 是一個斐波那契數列。這里 f_{n} 的通項為: \\ f_{n}=\frac{5+2 \sqrt{5}}{5}\left(\frac{1+\sqrt{5}}{2}\right)^{n}+\frac{5-2 \sqrt{5}}{5}\left(\frac{1-\sqrt{5}}{2}\right)^{n}-1 \\ 斐波那契數列以指數的速度增長,對于樹高 n 有: \\ n<\log _{\frac{1+\sqrt{5}}{2}}\left(f_{n}+1\right)<\frac{3}{2} \log _{2}\left(f_{n}+1\right) \\ 因此 AVL 樹的高度為 O\left(\log f_{n}\right) ,這里的 f_{n} 為結點數。 設fn?為高度為n的AVL樹所包含的最少節點數,則有fn?=? ? ??12fn?1?+fn?2?+1?(n=1)(n=2)(n>2)?根據常系數非齊次線性差分方程的解法(或者對轉移矩陣求特征向量并相似對角化),{fn?+1}是一個斐波那契數列。這里fn?的通項為:fn?=55+25??(21+5??)n+55?25??(21?5??)n?1斐波那契數列以指數的速度增長,對于樹高n有:n<log21+5???(fn?+1)<23?log2?(fn?+1)因此AVL樹的高度為O(logfn?),這里的fn?為結點數。
二、AVL樹實現(AVL樹實現名次樹)
2.1 節點定義
struct Node {Node *l = nullptr, *r = nullptr; // 左右兒子Key key; // 關鍵字u32 h = 1; // 高度int siz = 1; // 子樹大小Node(Key k): key(k) {} // 構造函數
} *root = nullptr;
// 樹高
int height(Node *t) {return t ? t->h : 0;
}
// 樹大小
int size(Node *t) {return t ? t->siz : 0;
}
// 修正
void pull(Node *t) {t->h = std::max(height(t->l), height(t->r)) + 1;t->siz = size(t->l) + 1 + size(t->r);
}
// 平衡因子
// 根據考研408 給出的標準 height(t->l) - height(t->r)
// 其他的教材,如鄧公的代碼則與本文相反
int factor(Node *t) {return height(t->l) - height(t->r);
}
2.2 左/右旋轉
- 旋轉不改變中序
- 可用于單傾斜型重平衡調整
// 左旋
void rotateL(Node *&t) {Node *r = t->r;t->r = r->l;r->l = t;pull(t);pull(r);t = r;
}
// 右旋
void rotateR(Node *&t) {Node *l = t->l;t->l = l->r;l->r = t;pull(t);pull(l);t = l;
}
2.3 zig-zag / zag-zig 雙旋
- 雙旋用于重平衡
// 右左雙旋
void rotateRL(Node *&t) {rotateR(t->r);rotateL(t);
}
// 左右雙旋
void rotateLR(Node *&t) {rotateL(t->l);rotateR(t);
}
2.4 重平衡函數
- 在插入或者刪除過程中,自頂向上回溯調整
- 如果是 單傾斜型則單旋
- 否則雙旋
- 兩種情況,分為四種子情況,代碼對偶
void reBalance(Node *&t) {int diff = factor(t);if (diff == 2) {int diff = height(t->l->l) - height(t->l->r);if (diff >= 0) {rotateR(t);} else {rotateLR(t);}} else if (diff == -2) {int diff = height(t->r->r) - height(t->r->l);if (diff >= 0) {rotateL(t);} else {rotateRL(t);}}pull(t);
}
2.5 插入
bool insert(Node *&t, Key key) {if (!t) {t = new Node(key);return true;}// 是否多重集// if (t->key == key) return false;bool res = insert(key < t->key ? t->l : t->r, key);reBalance(t);return res;
}
2.6 刪除
- 對于刪除節點,找到中序后繼節點替換刪除即可
bool erase(Node *&t, Key key) {if (!t) return false;bool res;if (t->key == key) {if (t->l && t->r) {Node *del = t->r;while (del->l) {del = del->l;}std::swap(t->key, del->key);erase(t->r, key);}else {t = t->l ? t->l : t->r;}res = true;}else {res = erase(key < t->key ? t->l : t->r, key);}if (t) {reBalance(t);}return res;
}
2.7 排名查詢
- 定義一個關鍵字x的排名為 樹中比 x 小的節點數 + 1
int rank(Key key) {Node *t = root;int res = 0;while (t) {if (t->key < key) {res += size(t->l) + 1;t = t->r;} else {t = t->l;}}return res + 1;
}
2.8 查前驅/后繼
Node *pre(Key key) {Node *res = nullptr;Node *t = root;while (t) {if (t->key < key) {res = t;t = t->r;} else {t = t->l;}}return res;
}Node *suf(Key key) {Node *res = nullptr;Node *t = root;while (t) {if (t->key > key) {res = t;t = t->l;} else {t = t->r;}}return res;
}
2.9 查第 k 小
Node *kth(int k) {Node *res = root;while(res) {if (size(res->l) >= k) {res = res->l;} else if(size(res->l) + 1 == k) {break;} else {k -= size(res->l) + 1;res = res->r;}}return res;
}
2.10 完整代碼
template<typename Key>
class AVLTree {
private:struct Node {Node *l = nullptr, *r = nullptr;Key key;u32 h = 1;int siz = 1;Node(Key k): key(k) {}} *root = nullptr;int height(Node *t) {return t ? t->h : 0;}int size(Node *t) {return t ? t->siz : 0;}void pull(Node *t) {t->h = std::max(height(t->l), height(t->r)) + 1;t->siz = size(t->l) + 1 + size(t->r);}int factor(Node *t) {return height(t->l) - height(t->r);}void rotateL(Node *&t) {Node *r = t->r;t->r = r->l;r->l = t;pull(t);pull(r);t = r;}void rotateR(Node *&t) {Node *l = t->l;t->l = l->r;l->r = t;pull(t);pull(l);t = l;}void rotateRL(Node *&t) {rotateR(t->r);rotateL(t);}void rotateLR(Node *&t) {rotateL(t->l);rotateR(t);}void reBalance(Node *&t) {int diff = factor(t);if (diff == 2) {int diff = height(t->l->l) - height(t->l->r);if (diff >= 0) {rotateR(t);} else {rotateLR(t);}} else if (diff == -2) {int diff = height(t->r->r) - height(t->r->l);if (diff >= 0) {rotateL(t);} else {rotateRL(t);}}pull(t);}bool insert(Node *&t, Key key) {if (!t) {t = new Node(key);return true;}// 是否多重集// if (t->key == key) return false;bool res = insert(key < t->key ? t->l : t->r, key);reBalance(t);return res;}bool erase(Node *&t, Key key) {if (!t) return false;bool res;if (t->key == key) {if (t->l && t->r) {Node *del = t->r;while (del->l) {del = del->l;}std::swap(t->key, del->key);erase(t->r, key);}else {t = t->l ? t->l : t->r;}res = true;}else {res = erase(key < t->key ? t->l : t->r, key);}if (t) {reBalance(t);}return res;}
public:bool insert(Key key) {return insert(root, key);}bool erase(Key key) {return erase(root, key);}int rank(Key key) {Node *t = root;int res = 0;while (t) {if (t->key < key) {res += size(t->l) + 1;t = t->r;} else {t = t->l;}}return res + 1;}Node *pre(Key key) {Node *res = nullptr;Node *t = root;while (t) {if (t->key < key) {res = t;t = t->r;} else {t = t->l;}}return res;}Node *suf(Key key) {Node *res = nullptr;Node *t = root;while (t) {if (t->key > key) {res = t;t = t->l;} else {t = t->r;}}return res;}Node *kth(int k) {Node *res = root;while(res) {if (size(res->l) >= k) {res = res->l;} else if(size(res->l) + 1 == k) {break;} else {k -= size(res->l) + 1;res = res->r;}}return res;}std::vector<Key> getAll() {std::vector<Key> res;auto dfs = [&](auto &&self, Node *t) -> void{if (!t) return;self(self, t->l);res.push_back(t->key);self(self, t->r);};dfs(dfs, root);return res;}
};
三、online judge 驗證
3.1 P6136 【模板】普通平衡樹(數據加強版)
題目鏈接
P6136 【模板】普通平衡樹(數據加強版)
AC代碼
#include <bits/stdc++.h>using i64 = long long;
using u32 = unsigned int;template<typename Key>
class AVLTree {
private:struct Node {Node *l = nullptr, *r = nullptr;Key key;u32 h = 1;int siz = 1;Node(Key k): key(k) {}} *root = nullptr;int height(Node *t) {return t ? t->h : 0;}int size(Node *t) {return t ? t->siz : 0;}void pull(Node *t) {t->h = std::max(height(t->l), height(t->r)) + 1;t->siz = size(t->l) + 1 + size(t->r);}int factor(Node *t) {return height(t->l) - height(t->r);}void rotateL(Node *&t) {Node *r = t->r;t->r = r->l;r->l = t;pull(t);pull(r);t = r;}void rotateR(Node *&t) {Node *l = t->l;t->l = l->r;l->r = t;pull(t);pull(l);t = l;}void rotateRL(Node *&t) {rotateR(t->r);rotateL(t);}void rotateLR(Node *&t) {rotateL(t->l);rotateR(t);}void reBalance(Node *&t) {int diff = factor(t);if (diff == 2) {int diff = height(t->l->l) - height(t->l->r);if (diff >= 0) {rotateR(t);} else {rotateLR(t);}} else if (diff == -2) {int diff = height(t->r->r) - height(t->r->l);if (diff >= 0) {rotateL(t);} else {rotateRL(t);}}pull(t);}bool insert(Node *&t, Key key) {if (!t) {t = new Node(key);return true;}// 是否多重集// if (t->key == key) return false;bool res = insert(key < t->key ? t->l : t->r, key);reBalance(t);return res;}bool erase(Node *&t, Key key) {if (!t) return false;bool res;if (t->key == key) {if (t->l && t->r) {Node *del = t->r;while (del->l) {del = del->l;}std::swap(t->key, del->key);erase(t->r, key);}else {t = t->l ? t->l : t->r;}res = true;}else {res = erase(key < t->key ? t->l : t->r, key);}if (t) {reBalance(t);}return res;}
public:bool insert(Key key) {return insert(root, key);}bool erase(Key key) {return erase(root, key);}int rank(Key key) {Node *t = root;int res = 0;while (t) {if (t->key < key) {res += size(t->l) + 1;t = t->r;} else {t = t->l;}}return res + 1;}Node *pre(Key key) {Node *res = nullptr;Node *t = root;while (t) {if (t->key < key) {res = t;t = t->r;} else {t = t->l;}}return res;}Node *suf(Key key) {Node *res = nullptr;Node *t = root;while (t) {if (t->key > key) {res = t;t = t->l;} else {t = t->r;}}return res;}Node *kth(int k) {Node *res = root;while(res) {if (size(res->l) >= k) {res = res->l;} else if(size(res->l) + 1 == k) {break;} else {k -= size(res->l) + 1;res = res->r;}}return res;}std::vector<Key> getAll() {std::vector<Key> res;auto dfs = [&](auto &&self, Node *t) -> void{if (!t) return;self(self, t->l);res.push_back(t->key);self(self, t->r);};dfs(dfs, root);return res;}
};int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n, m;std::cin >> n >> m;AVLTree<int> set;for (int i = 0; i < n; ++ i) {int x;std::cin >> x;set.insert(x);}int last = 0;int ans = 0;while(m --) {int t, x;std::cin >> t >> x;x ^= last;if (t == 1) {set.insert(x);} else if(t == 2) {set.erase(x);} else if(t == 3) {last = set.rank(x);ans ^= last;} else if(t == 4) {last = set.kth(x)->key;ans ^= last;} else if(t == 5) {last = set.pre(x)->key;ans ^= last;} else {last = set.suf(x)->key;ans ^= last;}}std::cout << ans << '\n';return 0;
}