确定一个自平衡二叉树的高度公式，知道它的节点数
Determine a self-balanced binary tree height formula knowing its number of node
我一直致力于确定自平衡二叉树的高度，知道它的节点数 (N)，我得出了公式：
height = ceilling[log2(N+1)], where ceilling[x] is the smallest integer not less than x.
问题是我在互联网上找不到这个公式，它看起来很准确。
有自平衡二叉树这个公式会失效的情况吗？
那么确定树高的一般公式是什么？
维基百科的 Self-balancing binary search tree 文章中有一个公式。
h >= ceilling(log2(n+1) - 1) >= floor(log2(n))
最低身高为floor(log2(n))。然而，值得注意的是，
the simplest algorithms for BST item insertion may yield a tree with height n in rather common situations. For example, when the items are inserted in sorted key order, the tree degenerates into a linked list with n nodes.
因此，您的公式与 "good approximation" 公式相差不远（仅相差 1），但 n 和 log2(n) 之间的范围可能很宽考虑在内。
我一直致力于确定自平衡二叉树的高度，知道它的节点数 (N)，我得出了公式：
height = ceilling[log2(N+1)], where ceilling[x] is the smallest integer not less than x.
问题是我在互联网上找不到这个公式，它看起来很准确。
有自平衡二叉树这个公式会失效的情况吗？
那么确定树高的一般公式是什么？
维基百科的 Self-balancing binary search tree 文章中有一个公式。
h >= ceilling(log2(n+1) - 1) >= floor(log2(n))
最低身高为floor(log2(n))。然而，值得注意的是，
the simplest algorithms for BST item insertion may yield a tree with height n in rather common situations. For example, when the items are inserted in sorted key order, the tree degenerates into a linked list with n nodes.
因此，您的公式与 "good approximation" 公式相差不远（仅相差 1），但 n 和 log2(n) 之间的范围可能很宽考虑在内。