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 120
Sample Output 1:
70
Sample Input 2:
7
88 70 61 96 120 90 65
Sample Output 2:
88
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef struct NODE{
struct NODE* lchild, *rchild;
int key;
int height;
}node;
int getHeight(node* root){
if(root == NULL)
return ;
else return root->height;
}
void updateHeight(node *root){
root->height = max(getHeight(root->lchild), getHeight(root->rchild)) + ;
}
void L(node* &root){
node* temp = root;
root = root->rchild;
updateHeight(root);
temp->rchild = root->lchild;
root->lchild = temp;
updateHeight(temp);
}
void R(node* &root){
node *temp = root;
root = root->lchild;
updateHeight(root);
temp->lchild = root->rchild;
root->rchild = temp;
updateHeight(temp);
}
void insert(node* &root, int key){
if(root == NULL){ //此处可获得插入节点的信息
node* temp = new node;
temp->lchild = NULL;
temp->rchild = NULL;
temp->key = key;
temp->height = ;
root = temp;
return;
}
if(key < root->key){ //此处可获得距离插入节点最近得父节点得信息
insert(root->lchild, key);
updateHeight(root);
if(abs(getHeight(root->lchild) - getHeight(root->rchild)) == ){
if(getHeight(root->lchild->lchild) > getHeight(root->lchild->rchild)){
R(root);
}else{
L(root->lchild);
R(root);
}
}
}else{
insert(root->rchild, key);
updateHeight(root);
if(abs(getHeight(root->lchild) - getHeight(root->rchild)) == ){
if(getHeight(root->rchild->rchild) > getHeight(root->rchild->lchild)){
L(root);
}else{
R(root->rchild);
L(root);
}
}
}
}
int main(){
int N, key;
scanf("%d", &N);
node* root = NULL;
for(int i = ; i < N; i++){
scanf("%d", &key);
insert(root, key);
}
printf("%d", root->key);
cin >> N;
return ;
}
总结：
1、题意：按照题目给出的key的顺序，建立一个平衡二叉搜索树。
2、二叉搜索树的几个关键地方：
- 每个节点使用height来记录自己的高度，叶节点高度为1;
- 获得某个节点高度的函数，主要是由于在获取平衡因子时，有些树的子树是空的，需要返回0，为避免访问空指针，获取节点高度都要通过该函数而非height字段。
- 更新当前节点的高度，应更新为左右子树的最大高度+1。
- 左旋与右旋：一定是三步操作而不是两步（不要忘记新的root的原子树）。注意更新节点高度的先后顺序。
- 插入与建树：插入操作基于二叉搜索树的插入。在root = NULL时进行新建节点并插入，在此处可以获得插入节点的信息。而在递归插入语句处，可以获取插入A节点之后距离A节点最近的父节点。因此在递归插入结束后就要对该节点进行更新高度，并在此处更新完之后检查平衡因子，并做LL、LR、RR、RL旋转。
3、对rootA的左子树做插入，导致rootA的左子树与右子树高度差为2，则对以rootA为根的树旋转。
4、调试的时候，可以取很少的几个节点，然后画出调试过程中树的形状。