2019-04-19 08:34

# AVL数据结构上的平衡树的高度的计算方式，怎么采用C语言的办法对这个问题的实现？

Problem 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.

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.

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

• 点赞
• 写回答
• 关注问题
• 收藏
• 邀请回答