首页 > ACM题库 > HDU-杭电 > hdu 2193 AVL Tree-二叉树-[解题报告]C++
2013
12-30

hdu 2193 AVL Tree-二叉树-[解题报告]C++

AVL Tree

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

1
2
0

样例输出:

0
1

题目大意:n个点的AVL树最多有几层。

递推公式:   a[i]=a[i-1]+a[i-2]+1;

自己画一下图就知道了

我的代码:

#include <stdio.h>
int main ()
{
int n,i,a[100];
a[0]=1;a[1]=2;
for (i=2;i<44;i++)
   a[i]=a[i-1]+a[i-2]+1;
while (scanf("%d",&n)!=EOF)
{
   if (n==0) return 0;
   i=0;
   while (a[i]<=n)
    i++;
   printf ("%d\n",--i);
}
return 0;
}

 


  1. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

  2. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

  3. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }