對洛谷題解上的代碼進行了修改，刪除了一些不必要的更新操作，以及修改了個人認為原來的代碼不合理之處（可能是并不能理解原來的代碼為何這么寫） ，并添加了自己的注釋

#include <bits/stdc++.h> using namespace std; struct AVLnode {// 數(shù)據(jù)int data;// 節(jié)點高度int high;// 相同數(shù)據(jù)的個數(shù)int freq;// 樹的大小int size;// 左子節(jié)點AVLnode *ls;// 右子節(jié)點AVLnode *rs;// 默認構(gòu)造函數(shù)，初始化數(shù)據(jù)，高度，相同數(shù)據(jù)個數(shù)，樹的大小，左子節(jié)點，右子節(jié)點AVLnode() : data(0), high(1), freq(1), size(1), ls(NULL), rs(NULL) {}// 帶參構(gòu)造函數(shù)，初始化數(shù)據(jù)a，高度，相同數(shù)據(jù)個數(shù)，樹的大小，左子節(jié)點，右子節(jié)點AVLnode(int a) : data(a), high(1), freq(1), size(1), ls(NULL), rs(NULL) {} }; // 獲取節(jié)點的大小 int GetSize(AVLnode* p) {if (p == NULL)return 0;return p->size; } // 獲取節(jié)點的高度 int GetHigh(AVLnode* p) {if (p == NULL)return 0;return p->high; } // 更新節(jié)點的大小、高度 void update(AVLnode*& p) {// 該節(jié)點的大小為左子樹的大小、右子樹的大小和該節(jié)點相同數(shù)據(jù)的個數(shù)之和p->size = GetSize(p->ls) + GetSize(p->rs) + p->freq;// 該節(jié)點的高度為左子樹的高度 + 右子樹的高度 + 自身貢獻高度1p->high = max(GetHigh(p->ls), GetHigh(p->rs)) + 1; } // 對樹的旋轉(zhuǎn)、插入、刪除操作都有可能改變根節(jié)點，需要傳引用 // 對樹的查詢不改變樹的結(jié)構(gòu)，不需要傳引用// 左左不平衡，將該節(jié)點右旋 void LeftLeft(AVLnode*& p) {AVLnode* q = p->ls;p->ls = q->rs;q->rs = p;update(p);update(q);p = q; } // 右右不平衡，將該節(jié)點左旋 void RightRight(AVLnode*& p) {AVLnode* q = p->rs;p->rs = q->ls;q->ls = p;update(p);update(q);p = q; } // 左右不平衡，將該節(jié)點的左子節(jié)點左旋，轉(zhuǎn)化為左左不平衡情形，再將該節(jié)點右旋 void LeftRight(AVLnode*& p) {RightRight(p->ls);LeftLeft(p); } // 右左不平衡，將該節(jié)點的右子節(jié)點右旋，轉(zhuǎn)化為右右不平衡情形，再將該節(jié)點左旋 void RightLeft(AVLnode*& p) {LeftLeft(p->rs);RightRight(p); } // 插入數(shù)據(jù)x void Insert(AVLnode*& p, int x) {// 若根節(jié)點為空，說明這個子樹為空樹，只需要創(chuàng)建一個新節(jié)點即可if (p == NULL) { p = new AVLnode(x);return;}// 若插入的數(shù)據(jù)x，在樹中存在，只需要將相同數(shù)據(jù)的個數(shù)+1，并更新該節(jié)點的高度和相同數(shù)據(jù)個數(shù)if (p->data == x) {++p->freq;update(p);return;}// 若插入的數(shù)據(jù)x小于目前節(jié)點p的數(shù)據(jù)，則往目前節(jié)點的左子樹插入數(shù)據(jù)x，并更新節(jié)點p的高度// 接著調(diào)節(jié)樹使得樹仍處于平衡狀態(tài)// 由于往目前節(jié)點左子樹插入數(shù)據(jù)x，所以只可能導(dǎo)致樹“左傾”(?)，故只會發(fā)生左右不平衡或左左不平衡// 在發(fā)生樹“左傾”的情況下時// 當插入的數(shù)據(jù)x小于左節(jié)點數(shù)據(jù)時，發(fā)生左左不平衡// 當插入的數(shù)據(jù)x大于（不可能等于，若等于，則往左子樹插入數(shù)據(jù)x時不會導(dǎo)致樹不平衡）右節(jié)點數(shù)據(jù)時，發(fā)生左右不平衡if (x < p->data) {Insert(p->ls, x), update(p);if (GetHigh(p->ls) - GetHigh(p->rs) == 2) {if (x < p->ls->data)LeftLeft(p);elseLeftRight(p);}}// 若插入的數(shù)據(jù)x大于（不會等于，因為等于的情況已經(jīng)在上面return掉了）目前節(jié)點p的數(shù)據(jù)，則往目前節(jié)點的右子樹插入數(shù)據(jù)x，并更新節(jié)點p的高度// 調(diào)整平衡的方式與上面類似else {Insert(p->rs, x), update(p);if (GetHigh(p->rs) - GetHigh(p->ls) == 2) {if (x > p->rs->data)RightRight(p);elseRightLeft(p);}} } // 刪除數(shù)據(jù)x void Erase(AVLnode*& p, int x) {// 該節(jié)點為空，什么也不用做if (p == NULL)return;// 若刪除的數(shù)據(jù)x比目前節(jié)點數(shù)據(jù)小，在左子樹里刪，比目前節(jié)點大，在右子樹里刪// 同插入，需要調(diào)整平衡// 若刪左子樹的數(shù)據(jù)，則可能發(fā)生“右傾”，反之，發(fā)生“左傾”// 不妨考慮“右傾”情形，此時無法通過刪除的數(shù)據(jù)x來判斷是右右不平衡還是右左不平衡。// 只能通過右節(jié)點的右子樹高度和右節(jié)點的左子樹高度比大小來判斷是何種情形。// 需要注意右節(jié)點的左子樹高度和右節(jié)點的右子樹高度在發(fā)生“右傾”的情況下也是有可能相等的，這和插入情形不同。// 此時調(diào)整平衡的方式也應(yīng)該是右右不平衡的方式（即只需要左旋）。// “左傾”情形同理。if (x < p->data) {Erase(p->ls, x), update(p);if (GetHigh(p->rs) - GetHigh(p->ls) == 2) {if (GetHigh(p->rs->rs) >= GetHigh(p->rs->ls))RightRight(p);elseRightLeft(p);}} else if (x > p->data) {Erase(p->rs, x), update(p);if (GetHigh(p->ls) - GetHigh(p->rs) == 2) {if (GetHigh(p->ls->ls) >= GetHigh(p->ls->rs))LeftLeft(p);elseLeftRight(p);}}// 若刪除的數(shù)據(jù)x和該節(jié)點的數(shù)據(jù)相等，則要刪該節(jié)點// 若該節(jié)點相同數(shù)據(jù)的個數(shù)大于1，只需要把相同節(jié)點個數(shù)-1else {if (p->freq > 1) {--p->freq;update(p);return;}// 若左子樹和右子樹都存在，則找該節(jié)點的后繼，即大于它的最小值，只需一開始找右子樹，之后一路向左// 用該節(jié)點后繼的節(jié)點代替該節(jié)點，刪掉該節(jié)點，并更新// 調(diào)整平衡，只可能是“左傾”，調(diào)整方法同上if (p->ls && p->rs) {AVLnode* q = p->rs;while (q->ls)q = q->ls;p->freq = q->freq;p->data = q->data;q->freq = 1;Erase(p->rs, q->data);update(p);if (GetHigh(p->ls) - GetHigh(p->rs) == 2) {if (GetHigh(p->ls->ls) >= GetHigh(p->ls->rs))LeftLeft(p);elseLeftRight(p);}}// 若只存在左子樹或只存在右子樹，子承父業(yè)，刪掉父節(jié)點即可，又由于刪之前是平衡的樹，所以刪后不會發(fā)生不平衡的情形// 若左子樹和右子樹都不存在，直接刪即可，又由于刪之前是平衡的樹，所以刪后不會發(fā)生不平衡的情形else {AVLnode* q = p;if (p->ls)p = p->ls;else if (p->rs)p = p->rs;elsep = NULL;delete q;q = NULL;}} } // 查詢val的排名 int GetRank(AVLnode* p, int val) {// 此種情況，結(jié)果為左子樹大小+1if (p->data == val)return GetSize(p->ls) + 1;// 此種情況，找左子樹中val的排名if (val < p->data)return GetRank(p->ls, val);// 此種情況，找右子樹中val的排名，加上左子樹的大小，加節(jié)點本身的個數(shù)return GetRank(p->rs, val) + GetSize(p->ls) + p->freq; } // 查詢排名為rank的數(shù)據(jù) int GetVal(AVLnode* p, int rank) {// 此種情況，結(jié)果為左子樹中找排名rank的數(shù)據(jù)if (GetSize(p->ls) >= rank)return GetVal(p->ls, rank);// 此種情況，結(jié)果為節(jié)點本身的數(shù)據(jù)if (GetSize(p->ls) + p->freq >= rank)return p->data;// 此種情況，結(jié)果為右子樹中找排名為rank去掉左子樹大小再去掉節(jié)點本身個數(shù)的數(shù)據(jù)return GetVal(p->rs, rank - GetSize(p->ls) - p->freq); } // 查找val前驅(qū) int GetPrev(AVLnode* p, int val) {// 最大值大于等于-10e7int ans = -(10e7 + 5); AVLnode* q = p;while (q) {// 存在val這個節(jié)點，先找左子樹，再一路向右，答案即為一路向右if (q->data == val) {if (q->ls) {q = q->ls;while (q->rs)q = q->rs;ans = q->data;}break;}// 不存在val這個節(jié)點，就找小于val的最大值if (q->data < val && q->data > ans)ans = q->data;// 往下遍歷q = q->data < val ? q->rs : q->ls;}return ans; } // 查找val后繼 int GetNext(AVLnode* p, int val) {// 方法同上int ans = 10e7 + 5;AVLnode *q = p;while (q) {if (q->data == val) {if (q->rs) {q = q->rs;while (q->ls)q = q->ls;ans = q->data;}break;}if (q->data > val && q->data < ans)ans = q->data;q = q->data < val ? q->rs : q->ls;}return ans; } int main() {int n;scanf("%d", &n);AVLnode* root = NULL;while (n--) {int opt, x;scanf("%d%d", &opt, &x);switch (opt) {case 1:Insert(root, x);break;case 2:Erase(root, x);break;case 3:printf("%d\n", GetRank(root, x));break;case 4:printf("%d\n", GetVal(root, x));break;case 5:printf("%d\n", GetPrev(root, x));break;case 6:printf("%d\n", GetNext(root, x));break;}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的洛谷P3369 AVL树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。