04-树5 Root of AVL Tree (25 分)
2024-09-05 22:41:41
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 (≤) 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 the 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<algorithm>
using namespace std; struct Node
{
int v;
int height;
Node *lchild, *rchild;
}*root; void Insert(Node* &root,int v);
Node* NewNode(int v);
void updateHeight(Node *root);
int getHeight(Node* root);
int getBalanceFactor(Node* root);
Node* R(Node* &root);
Node* L(Node* &root); int main()
{
int n;
int v;
scanf("%d",&n);
for (int i = ; i < n; i++)
{
scanf("%d",&v);
Insert(root,v);
}
printf("%d",root->v);
return ;
} void Insert(Node* &root, int v)
{
if (NULL == root)
{
root = NewNode(v);
return ;
} if (root->v > v)
{
Insert(root->lchild,v);
updateHeight(root);
if ( == getBalanceFactor(root))
{
if ( == getBalanceFactor(root->lchild))
{
R(root);
}
else if(- == getBalanceFactor(root->lchild))
{
L(root->lchild);
R(root);
}
}
}
else
{
Insert(root->rchild,v);
updateHeight(root);
if (- == getBalanceFactor(root))
{
if (- == getBalanceFactor(root->rchild))
{
L(root);
}
else if( == getBalanceFactor(root->rchild))
{
R(root->rchild);
L(root);
}
}
}
} Node* NewNode(int v)
{
Node* node = new Node;
node->lchild = node->rchild = NULL;
node->v = v;
node->height = ;
return node;
} void updateHeight(Node *root)
{
root->height = max(getHeight(root->lchild),getHeight(root->rchild)) + ; } int getHeight(Node* root)
{
if (NULL == root)
{
return ;
}
else
{
return root->height;
}
} int getBalanceFactor(Node* root)
{
return getHeight(root->lchild) - getHeight(root->rchild);
} Node* R(Node* &root)
{
Node *tmp = root->lchild;
root->lchild = tmp->rchild;
tmp->rchild = root;
updateHeight(root);
updateHeight(tmp);
root = tmp;
} Node* L(Node* &root)
{
Node *tmp = root->rchild;
root->rchild = tmp->lchild;
tmp->lchild = root;
updateHeight(root);
updateHeight(tmp);
root = tmp;
}
最新文章
- android 生成验证码图片
- Java并发包中Lock的实现原理
- uva133-S.B.S.
- EBS R12中重新enable失效用户之后,丢失职责
- 必须会的SQL语句(八)数据库的完整性约束
- 【转载】c/c++在windows下获取时间和计算时间差的几种方法总结
- 212. Word Search II
- Linq to Sql 总生成 where ID is null 的解决办法
- android笔试题集2
- kvm中运行kvm
- Ajax 生成流文件下载 以及复选框的实现
- Spring MVC DispatcherServlet绑定多种URL
- C++中const的实现机制深入分析
- python之psutil模块(获取系统性能信息(CPU,内存,磁盘,网络)
- python_str 字符串的所有方法
- 关卡得分(if 嵌套for)与(for嵌套if)
- SpringBoot鸡汤(注解集合二)
- nginx配置client_body_temp_path
- 开源 java CMS - FreeCMS2.2 菜单管理
- EDK_II环境搭建与测试