首页 > 代码库 > 04-1. Root of AVL Tree (25)
04-1. Root of AVL Tree (25)
04-1. Root of AVL Tree (25)
An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.
Now given a sequence of insertions, you are supposed to tell the root of the resulting AVL tree.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (<=20) which is the total number of keys to be inserted. Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print ythe root of the resulting AVL tree in one line.
Sample Input 1:5 88 70 61 96 120Sample Output 1:
70Sample Input 2:
7 88 70 61 96 120 90 65Sample Output 2:
88
提交代码
题意:给你n个数 输出以他们建立的平衡查找树的根结点
参考:http://www.cppblog.com/cxiaojia/archive/2013/07/22/187776.html
http://blog.csdn.net/realxuejin/article/details/12872035 两篇博文
#include <iostream> #include <algorithm> #include <string> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <vector> #include<queue> #include<stack> #include<map> #include<set> using namespace std; //#define lson rt<<1,l,MID //#define rson rt<<1|1,MID+1,r //#define lson root<<1 //#define rson root<<1|1 //#define MID ((l+r)>>1) typedef long long ll; typedef pair<int,int> P; const int maxn=50005; const int base=1000; const int inf=999999; const double eps=1e-5; struct node//树的结点 { int data;//数据域 int high;///树的高度 node *lson,*rson;//左右儿子 node(){lson=rson=NULL;high=0;}//构造函数 初始化的作用 }; int getHigh(node *t)//取高度函数 { if(t!=NULL) return t->high; return -1; } node *LL(node *k2)//左左单旋 { node *k1; k1=k2->lson; k2->lson=k1->rson; k1->rson=k2; k2->high=max(getHigh(k2->lson),getHigh(k2->rson))+1; k1->high=max(getHigh(k1->lson),getHigh(k1->rson))+1; return k1; } node *RR(node *k2)//右右单旋 { node *k1; k1=k2->rson; k2->rson=k1->lson; k1->lson=k2; k2->high=max(getHigh(k2->lson),getHigh(k2->rson))+1; k1->high=max(getHigh(k1->lson),getHigh(k1->rson))+1; return k1; } node* LR(node *k3)//左右双旋 { k3->lson=RR(k3->lson); return LL(k3); } node* RL(node * k3)//右左双旋 { k3->rson=LL(k3->rson); return RR(k3); } bool isbalanced(node *a,node *b)//判定左右子树高度差 { return abs(getHigh(a)-getHigh(b))<2; } node* insert(node *root,int v)//建立树的过程 { if(root==NULL) { root=new node(); root->data=http://www.mamicode.com/v;>
04-1. Root of AVL Tree (25)