Que*_*ger 5 height binary-search-tree data-structures
我正在阅读算法设计手册.作者指出,树的高度是:
h = log n,
where
h is height
n = number of leaf nodes
log is log to base d, where d is the maximum number of children allowed per node.
然后他接着说,一个完美平衡的二叉搜索树的高度将是:
h = log n
我想知道n在第二个语句中是否表示" 叶子节点总数"或" 节点总数".
这提出了一个更大的问题,节点总数和完美平衡的二叉搜索树的高度之间是否存在数学关系？
当然,n = 2^h这里h, n分别表示树的高度和节点的数量.
证明草图:
一个完美平衡的二叉树
关于完美平衡二叉树中的叶节点:
由于叶子的数量是节点的数量减去高度递减1的完美平衡二叉树中的节点数量,叶子的数量是所有节点的数量的一半(确切地说,是一半n+1).
所以h只是1,这通常不会在复杂性考虑方面产生任何实际差异.该声明可以通过记住它与将单个节点树的高度定义为0(标准)或1(异常,但在将其与空树区分时可能很方便)相同的变化来说明.