博主欢迎转载，但请给出本文链接，我尊重你，你尊重我，谢谢~
http://www.cnblogs.com/chenxiwenruo/p/6803291.html
特别不喜欢那些随便转载别人的原创文章又不给出链接的
所以不准偷偷复制博主的博客噢~~
题意：给你一个插入的序列，问你最后AVL树的根节点是多少
AVL树模板题
如果会AVL树，那么就是水题
如果不会的话，那么就是难题
我刚开始也不会，所以根本写不出来AVL树。。。
后来花了一些时间学习了下，感觉网上很多模板都是用class写的，太麻烦了
模板就是应该要简洁点、方便的，A题的时候哪有功夫写那么复杂的模板
我就用的struct结构体来写的，一样好用，尽可能地简洁
后面(具体时间还不确定)我会给出AVL树的学习专栏
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int maxn=30; int n; struct Node{ int l,r; int val; int h; }; struct AVLTree{ Node node[maxn]; int cnt=0; int height(int u){ if(u==-1) return 0; return node[u].h; } /** k1 is the current root，(向)右旋，顺时针旋转 对k1的左儿子L的左子树L进行了一次插入，所以是LL */ int RotateLL(int k1){ int k2; k2=node[k1].l; node[k1].l=node[k2].r; node[k2].r=k1; node[k1].h=max(height(node[k1].l),height(node[k1].r))+1; node[k2].h=max(height(node[k2].l),node[k1].h)+1; return k2; //new root } /** k1 is the current root，(向)左旋，逆时针旋转 对k1的右儿子R的右子树R进行了一次插入，所以是RR */ int RotateRR(int k1){ int k2; k2=node[k1].r; node[k1].r=node[k2].l; node[k2].l=k1; node[k1].h=max(height(node[k1].l),height(node[k1].r))+1; node[k2].h=max(height(node[k2].r),node[k1].h)+1; return k2;// new root } /** 对k1的左儿子L的右子树R进行插入，所以是LR 先对k1的左儿子进行(向)左旋操作 再对k1进行(向)右旋操作 */ int RotateLR(int k1){ node[k1].l=RotateRR(node[k1].l); int root=RotateLL(k1); return root; } /** 对k1的右儿子R的左子树L进行插入，所以是RL 先对k1的右儿子进行(向)右旋操作 再对k1进行(向)左旋操作 */ int RotateRL(int k1){ node[k1].r=RotateLL(node[k1].r); int root=RotateRR(k1); return root; } /** 插入操作 就分LLLRRRRL四种情况 */ int insert_val(int val,int root){ //int res=root; if(root==-1){ node[cnt].l=node[cnt].r=-1; node[cnt].val=val; node[cnt].h=1; root=cnt; cnt++; //return cnt; } else if(val<node[root].val){ node[root].l=insert_val(val,node[root].l); int left=node[root].l; int right=node[root].r; if(height(left)-height(right)==2){ if(val<node[left].val){ root=RotateLL(root); } else{ root=RotateLR(root); } } } else if(val>node[root].val){ node[root].r=insert_val(val,node[root].r); int left=node[root].l; int right=node[root].r; if(height(left)-height(right)==-2){ if(val>node[right].val){ root=RotateRR(root); } else{ root=RotateRL(root); } } } else{ //nothing } node[root].h=max(height(node[root].l),height(node[root].r))+1; return root; } }avltree; /* void dfs(int u){ if(u==-1) return; dfs(avltree.node[u].l); printf("%d:%d ",u,avltree.node[u].val); dfs(avltree.node[u].r); } */ int main() { int a; int root=-1; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&a); root=avltree.insert_val(a,root); //printf("root:%d ",root); //dfs(root); } printf("%d ",avltree.node[root].val); return 0; }
如果之前不了解AVL数的基本旋转操作，可以参考下面这个博客，算是讲的比较清楚的：