C - 万恶的二叉树
Crawling in process... Crawling failed Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Description
An AVL tree is a kind of balanced binary search tree. Named after their inventors, Adelson-Velskii and Landis, they were the first dynamically balanced trees to be proposed. Like red-black trees, they are not perfectly balanced, but pairs of sub-trees differ in height by at most 1, maintaining an O(logn) search time. Addition and deletion operations also take O(logn) time.
Definition of an AVL tree
An AVL tree is a binary search tree which has the following properties:
1. The sub-trees of every node differ in height by at most one.
2. Every sub-tree is an AVL tree.
Balance requirement for an AVL tree: the left and right sub-trees differ by at most 1 in height.An AVL tree of n nodes can have different height.
For example, n = 7:
So the maximal height of the AVL Tree with 7 nodes is 3.
Given n,the number of vertices, you are to calculate the maximal hight of the AVL tree with n nodes.
Definition of an AVL tree
An AVL tree is a binary search tree which has the following properties:
1. The sub-trees of every node differ in height by at most one.
2. Every sub-tree is an AVL tree.
Balance requirement for an AVL tree: the left and right sub-trees differ by at most 1 in height.An AVL tree of n nodes can have different height.
For example, n = 7:
So the maximal height of the AVL Tree with 7 nodes is 3.
Given n,the number of vertices, you are to calculate the maximal hight of the AVL tree with n nodes.
Input
Input file contains multiple test cases. Each line of the input is an integer n(0<n<=10^9).
A line with a zero ends the input.
A line with a zero ends the input.
Output
An integer each line representing the maximal height of the AVL tree with n nodes.
Sample Input
1
2
0
Sample Output
0
1
题目大意：AVL树（又称高度平衡树）简介戳这里：http://baike.baidu.com/link?url=OUs8h211wSvjifeFg5cYzyUYmE8_WegNVk9MISMatdeLNDjMl1ypSn1CPUEnKIp1RQcFLFiuFfj4JwVOeOS0Sa
思路分析：本题只用到了AVL树的一个简单结论
高度为h的AVL树，节点数N最多为2^h-1,最少为N(h)=N(h-1)+N(h-2)+1
初始化N(0)=1,N(1)=2,以此类推
代码：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
const int maxn=50;;
char m[maxn][maxn];
__int64 a[maxn];
int main()
{
a[0]=1;
a[1]=2;
__int64 n;
for(int i=2;i<maxn;i++) a[i]=a[i-1]+a[i-2]+1;
while(scanf("%I64d",&n)&&n)
{
int k=0;
while(a[k]<=n) k++;
cout<<--k<<endl;
}
return 0;
}
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
const int maxn=50;;
char m[maxn][maxn];
__int64 a[maxn];
int main()
{
a[0]=1;
a[1]=2;
__int64 n;
for(int i=2;i<maxn;i++) a[i]=a[i-1]+a[i-2]+1;
while(scanf("%I64d",&n)&&n)
{
int k=0;
while(a[k]<=n) k++;
cout<<--k<<endl;
}
return 0;
}