一、AVL树
什么是AVL树呢，其实就是普通平衡树加二叉搜索树的结合体，只不过该树的形状趋近于
完全二叉树甚至接近满二叉树。所以平衡性很好，很适合查找工作，但是不适合删除操作
删除的话可能会从最下面进行调平衡从下一直调到根节点，如果多次删除的话，那么效率
就会变得很低
AVL树的核心就在于调平衡，主要介绍调平衡的方法.
怎么区分LL型呢，从高往下数两个，从树最不平衡的那端往下数，
也就是先判断两边谁树高，这里可以看出左树最高，走左树，左树最高再走左树
所以就是LL型(右旋的样子，抽象一下，这样就可以降低左树的高度)
这里是水滴为子树
图片来源于《算法训练营》陈小玉著
这种类型需要先调平衡转换成LL，在调平衡
以上四种情况包含了所有的不平衡状态
下面是代码细节及其注释
#include <iostream> #include <cstring> #include <algorithm> using namespace std; template <class K> class AVLNode { public: AVLNode() :lchild(nullptr), rchild(nullptr), height(1), data(K()) {} AVLNode(K _data) :lchild(nullptr), rchild(nullptr), height(1), data(_data) {} K data; int height; AVLNode<K>* lchild; AVLNode<K>* rchild; }; template<class K> class AVL { public: AVL() :_root(nullptr) {} void clear(AVLNode<K>*& T) { if (!T) return; clear(T->lchild); clear(T->rchild); delete T; T = nullptr; } ~AVL() { clear(_root); } void add(K x) { insert(_root, x); } void del(K x) { Delete(_root,x); } void Create1(AVLNode<K>*& T) { int n = 0; int x = 0; cin >> n; for (int i = 0;i < n;i++) { x = rand(); insert(T, x); } } void show() { inorder(_root); } private: AVLNode<K>* _root; //计算高度接口 int Height(AVLNode<K>* T) { if (!T) return 0; return T->height; } //我们做模块化，耦合度低代码维护性高，复用性强 //更新当前节点的高度,要改变当前节点的值所以用引用 void updateHeight(AVLNode<K>*& T) { if (!T) return;//空节点 T->height = max(Height(T->lchild), Height(T->rchild)) + 1; } //写接口记得画一般情况的图 //左边高，右边低 && LL型 == 右旋 AVLNode<K>* LL_Rotate(AVLNode<K>*& T)//LL旋转，只是转一次,传引用是为了，修改当前节点的值 { AVLNode<K>* tmp = T->lchild;//保存下当前节点左孩子，因为做根节点 T->lchild = tmp->rchild;//把空闲节点，挂接到当前节点的左孩子上，断开了当前节点和tmp的链接 tmp->rchild = T;//把tmp作为当前根节点 updateHeight(T);//更新T节点,往右旋之后只是改变了两个节点的高度，可以自己画图旋转看下 updateHeight(tmp);//更新tmp return tmp;//返回当前更新过后的根节点 } //左边低，右边高 && RR型 == 左旋 AVLNode<K>* RR_Rotate(AVLNode<K>*& T) { AVLNode<K>* tmp = T->rchild;//保存下当前节点右孩子，因为做根节点 T->rchild = tmp->lchild;//把空闲节点，挂接到当前节点的右孩子上，断开了当前节点和tmp的链接 tmp->lchild = T;//把tmp作为当前根节点 updateHeight(T);//更新T节点,往右旋之后只是改变了两个节点的高度，可以自己画图旋转看下 updateHeight(tmp);//更新tmp return tmp; } //画图 //下面这两个旋转就可以复用左旋和右旋接口了 AVLNode<K>* LR_Rotate(AVLNode<K>*& T) { T->lchild = RR_Rotate(T->rchild);//先进行左旋变成LL型，然后调用LL型 //因为旋转后把返回值是根节点，所以链接到T->lchild下面 return LL_Rotate(T); } AVLNode<K>* RL_Rotate(AVLNode<K>* T) { T->rchild = LL_Rotate(T->lchild); return RR_Rotate(T); } void adjust(AVLNode<K>*& T) { if (!T) return;//空树返回 if (Height(T->lchild) - Height(T->rchild) > 1) //左子树高，沿着树高度大的那条下去进行判断 { //然后再判断一下哪个高,判断出是LR类型，还是LL类型 if (Height(T->lchild->lchild) >= Height(T->lchild->rchild)) LL_Rotate(T); else if (Height(T->lchild->rchild) > Height(T->lchild->lchild)) LR_Rotate(T); } else if (Height(T->rchild) - Height(T->lchild) > 1) //右子树高，沿着树高度大的那条下去进行判断 { //然后再判断一下哪个高, 判断出是LR类型，还是LL类型 if (Height(T->rchild->rchild) >= Height(T->rchild->rchild)) RR_Rotate(T); else if (Height(T->rchild->lchild) > Height(T->lchild->lchild)) RL_Rotate(T); } } AVLNode<K>* insert(AVLNode<K>*& T, K x) { if (!T)//树空，创建一个新节点 { T = new AVLNode; T->lchild = T->rchild = nullptr; T->data = x; T->height = 1; return T; } if (T->data == x) return T; if (x < T->data)//向左子树搜索插入 { T->lchild = insert(T->lchild, x); } else if (x > T->data) { T->rchild = insert(T->rchild, x); } //插入过后更新 updateHeight(T); adjust(T); return T; } AVLNode<K>* Delete(AVLNode<K>*& T, int x) { if (!T) return T; if (T->data == x) { if (!T->lchild || !T->rchild)//如果有一个孩子为空 //子承父业 { AVLNode<K>* tmp = T; T = (T->lchild) ? T->lchild : T->rchild; delete tmp; } else { AVLNode<K>* tmp; tmp = T->lchild;//最小的最大 //找前驱节点 while (tmp->rchild) { tmp = tmp->rchild; } //找到最左的最右的节点后，更新data T->data = tmp->data; T->lchild = Delete(T->lchild, T->data);//然后去左子树删除值为tmp->data的节点 } } else if (T->data > x) { T->lchild = Delete(T->lchild, x);//递归去左子树删除 } else { T->rchild = Delete(T->rchild, x);//递归去右子树删除 } updateHeight(T);//删掉一个之后要更新根节点T的高度 adjust(T);//然后调平衡,调平衡会更新高度 return T; } void inorder(AVLNode<K>* T) { if (T == nullptr) return; inorder(T->lchild); cout << T->data << " "; inorder(T->rchild); } }; int main() { AVL<int> t; t.add(4); t.add(5); return 0; }
二,Treap(树堆)
树堆，顾明思异就是树+堆维护的平衡二叉搜索树
也有调平衡操作，跟AVL树调平衡类似，就不介绍了
Treap最主要的操作是随机值val，和key相结合
key是唯一的，val是唯一的(可能会相同)，当节点中
存在着两个值的时候，那么就会生成一个唯一的节点，唯一的话
那么就话增加这颗树的平衡性，并且key维护二叉搜索树的性质
val(随机值)维护堆的性质，那么这样就保证了该树趋近于平衡，虽然
不如AVL树平衡和红黑树，但是他的删除效率比AVL树和红黑树都要
来的高效，因为他保证平衡性不需要维护很多性质，只要用两个值维护好堆的性质
和二叉搜索树的性质即可，所以删除和插入很高效，但是由于随机的值存在
稳定性较差
模板题，题目摘自《算法进阶指南》
以下是代码，具体一些代码细节在注释里
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> using namespace std; const int N = 110000,INF = 1e8; typedef long long LL; int n; struct node { int l,r; int key,val;//节点键值key维护BST，val维护堆的性质，val越随机越好 int cnt,size;//cnt代表这个数出现的次数，size代表当前节点子树里的节点个数 }tr[N]; int root,idx; void pushup(int p)//儿子信息更新父节点信息 { tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + tr[p].cnt; } int get_node(int key) { tr[++idx].key = key; tr[idx].val = rand(); tr[idx].cnt = 1; tr[idx].size = 1; return idx; } //treap树最关键的操作，左旋和右旋 void zig(int& p)//右旋 { int q = tr[p].l;//先把p的左儿子存下来 tr[p].l = tr[q].r;//p的左儿子是q的右儿子 tr[q].r = p; p = q; pushup(p),pushup(tr[p].r); } void zag(int& p)//左旋 { int q = tr[p].r; tr[p].r = tr[q].l; tr[q].l = p; p = q; pushup(p),pushup(tr[p].l); } void bulid() { get_node(-INF); get_node(INF); root = 1,tr[1].r = 2;//根节点是1号，1号的右节点是2号 pushup(root); if(tr[1].val < tr[2].val) zag(root); } void insert(int& p,int key) { if(!p) p = get_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);//孩子节点 } //维护val是根节点root.val > 子树 root.l.val or root.r.val else { 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;//如果删除的值不存在，返回 else if(tr[p].key == key)//找到要删除的值 { //要删除的话有三种情况 //1.cnt > 1 //2.cnt == 1，该点删除的话还需要判断是否是叶子节点 //3.删除的节点就是叶子节点 if(tr[p].cnt > 1) tr[p].cnt--;//如果该值的cnt大于1，说明有，减去一个cnt就行 else if(tr[p].l || tr[p].r)//这里的情况可以把cnt == 1的情况给包括了 {//判断是否有叶子节点,有叶子节点就执行 //如果只有右节点，判断一下，左旋 //如果只有左节点，判断一下，右旋 if(!tr[p].r || tr[tr[p].r].val < tr[tr[p].l].val) //没有右节点,或者右孩子的val小于左孩子的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 if(tr[p].key < key) remove(tr[p].r,key); pushup(p); } int get_rank_by_key(int p,int key)//通过数值找排名 { if(!p) return -INF;//如果没有该值，删除 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)//通过排名找数值 传p而不是传&p { 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;//左子树+当前节点个数>=rank,则就是当前节点 //因为前面执行过来不是大于等于rank，而加了之后才>=rank说明当前这个数就是key return get_key_by_rank(tr[p].r,rank-tr[tr[p].l].size-tr[p].cnt);//-tr[p].cnt，递归右子树，找到 //排名等于rank-tr[tr[p].l].size-tr[p].cnt } int get_prev(int p,int key)//找到前驱节点，最小值最大，比key小的最大值 { if(!p) return -INF; if(tr[p].key>=key) return get_prev(tr[p].l,key);//当前这个数>=key 则要找的数在当前节点的左子树里 return max(tr[p].key, get_prev(tr[p].r, key));//小于的话，说明找到了，每次拿比较过后 //的max值去返回就会的得到最小值最大 } int get_next(int p,int key)//找到后继节点，最大值最小，比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>>n; while(n--) { int op,x; cin>>op>>x; LL ans; if(op == 1) insert(root,x); else if(op == 2) remove(root,x); else if(op == 3) { ans = get_rank_by_key(root,x); cout<<ans<<endl; } else if(op == 4) { ans = get_key_by_rank(root,x); cout<<ans<<endl; } else if(op == 5) { ans = get_prev(root,x); cout<<ans<<endl; } else if(op == 6) { ans = get_next(root,x); cout<<ans<<endl; } } return 0; }
