题目:http://pat.zju.edu.cn/contests/pat-a-practise/1066
题解:
考察数据结构;AVL树。
重点就是四种情况的识别和处理。
代码:
#include<cstdio> #include<cstring> #include<cmath> #include<string> #include<vector> #include<map> #include<set> #include<stack> #include<queue> #include<algorithm> using namespace std; #define INF 0x6fffffff #define MAX 25 struct point { int value; int left; int right; int heigh; }node[MAX]; int idx; int getHeight(int root) { if(root==-1) return -1; return node[root].heigh; } int rotateLL(int root) { int child=node[root].left; node[root].left=node[child].right;//root的左孩纸变成原左孩纸的右孩纸 node[child].right=root;//原root左孩纸的右孩纸变成root node[root].heigh=max(getHeight(node[root].left),getHeight(node[root].right))+1; node[child].heigh=max(getHeight(node[child].left),getHeight(node[child].right))+1; return child; } int rotateRR(int root) { int child=node[root].right; node[root].right=node[child].left;//root的右孩纸变成原右孩纸的左孩纸 node[child].left=root;//原root右孩纸的左孩纸变成root node[root].heigh=max(getHeight(node[root].left),getHeight(node[root].right))+1; node[child].heigh=max(getHeight(node[child].left),getHeight(node[child].right))+1; return child; } int rotateLR(int root) { int child=node[root].left; node[root].left=rotateRR(child); return rotateLL(root); } int rotateRL(int root) { int child=node[root].right; node[root].right=rotateLL(child); return rotateRR(root); } bool isBalance(int root) { return abs(getHeight(node[root].left)-getHeight(node[root].right))<2; } int insertNode(int root,int x)//插入新结点 { if(root!=-1) { if(x>node[root].value)//右 { node[root].right=insertNode(node[root].right,x); if(!isBalance(root)) { if(x>node[node[root].right].value)//右右 root=rotateRR(root); else//右左 root=rotateRL(root); } } else { node[root].left=insertNode(node[root].left,x); if(!isBalance(root)) { if(x>node[node[root].left].value)//左右 root=rotateLR(root); else//左左 root=rotateLL(root); } } } else { node[idx].value=x; node[idx].left=node[idx].right=-1; node[idx].heigh=0; root=idx; ++idx; } node[root].heigh=max(getHeight(node[root].left),getHeight(node[root].right))+1; return root; } void dfs(int root) { if(root==-1) return; if(node[root].left!=-1) { printf("%d left-> %d\n",node[root].value,node[node[root].left].value); dfs(node[root].left); } if(node[root].right!=-1) { printf("%d right-> %d\n",node[root].value,node[node[root].right].value); dfs(node[root].right); } } int main() { int n,x,root; scanf("%d",&n); idx=0; root=-1; for(int i=0;i<n;++i) { scanf("%d",&x); root=insertNode(root,x); //printf("start\n");//测试 //dfs(root); //printf("\n"); } //dfs(root); printf("%d\n",node[root].value); return 0; }