algorithm - 加权快速联合树高度

Question

我无法理解树高部分。高度不能大于 lg N，其中 N 是项目数。

lg 10 = 1

因此，一组 10 个项目的高度不能大于 1。但我能够快速合并值 0-9（十个项目）并且高度可达 3。

有人可以澄清吗？

Answer 1

对数作为函数有两个参数，第一个是底数，第二个是数。所以：

logarithm(base, number) = power

意思是如果你取底为base并将其提高到 的次方power，那么你的结果将是number。对数回答你的问题：

我应该提高基数以获得结果的数字。

如果您的所有节点都有 n 个子节点，那么您的分支具有以 n 为底的指数，因此 k 个节点需要的高度不小于log(n, k). 或者您也可以以自己的方式定义高度。

如果你有一棵二叉树，那么 n = 2。