1066 Root of AVL Tree (25)
2024-08-22 02:30:01
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 Ndistinct 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,height;
Node* lchild,*rchild;
}*root; Node* newNode(int v){
Node* node = new Node;
node -> v = v;
node -> lchild = node -> rchild = NULL;
node -> height = ;
return node;
} int getHeight(Node* root){
if(root == NULL) return ;
return root -> height;
} void updateHeight(Node* root){
root -> height = max(getHeight(root -> lchild),getHeight(root -> rchild))+;
} int getBalanceFactor(Node* root){
return getHeight(root -> lchild) - getHeight(root -> rchild);
} void R(Node* &root){
Node* temp = root -> lchild;
root -> lchild = temp -> rchild;
temp -> rchild = root;
updateHeight(root);
updateHeight(temp);
root = temp;
}
void L(Node* &root){
Node* temp = root -> rchild;
root -> rchild = temp -> lchild;
temp -> lchild = root;
updateHeight(root); //先更新root(子树)的高度
updateHeight(temp);
root = temp;
} void insert(Node* &root, int v){
if(root == NULL){
root = newNode(v);
return;
}
if(v < root -> 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); }
}
}
} int main(){
int n,v;
scanf("%d",&n);
for(int i = ; i < n; i++){
scanf("%d",&v);
insert(root,v);
}
printf("%d",root -> v);
return ;
}
最新文章
- hibernate(六)一对一映射
- C# WinForm 技巧八:界面开发之“WeifenLuo.WinFormsUI.Docking+OutLookBar” 使用
- 解决Ext.form.DateField在浏览器中显示可能有问题
- XCODE真机调试设备连接一直忙碌如何处理
- Flash Builder 4.6 界面显示一半中文一半英文?
- 从 Java 代码逆向工程生成 UML 类图和序列图
- 获取IP所在地
- word-wrap: break-word 和 word-break: break-all 到底有啥区别?
- python2.7_1.2_打印设备名和IPv4地址
- Linux Kernel(Android) 加密算法汇总(四)-应用程序调用OpenSSL加密演算法
- 永洪BI配置测试及遇到的一些问题
- Python爬虫01——第一个小爬虫
- Sql Server合并多行询数据到一行:使用自连接、FOR XML PATH(&#39;&#39;)、STUFF或REPLACE函数
- [转]查询sqlserver 正在执行的sql语句的详细信息
- 百度地图的Icon
- SPOJ 694 DISUBSTR - Distinct Substrings
- net core 获取网站目录
- 如何使用git 提交作业 收作业
- 【Spring实战-2】Spring4.0.4整合Hibernate4.3.6
- keras做DNN