全局平衡二叉树 时间复杂度的证明

· · 算法·理论

零、前言

这是一个争论已久的问题，网上有很多不同的答案，本文将给出严格的证明。

一、问题概述

全局平衡二叉树的原理就不在此解释了，见 oi-wiki ，网上还有很多优质教程。

时间复杂度的计算的核心在于证明重新建出的新的二叉树的树高不超过 \log_2 n 。

本文是在讨论只有两条重链，这是最劣情况，正确性证明如下。

首先，我们不妨设两条重链的点为集合 A 和 B （原树的根节点在 A 里 ），为了获得最大树高，这条轻链一定连在二叉树 A 的最后一层，P1-2就是一个例子。

同时，只设两条重链可以增大树高，P1-3就是一个例子。

总上，P1-1就是最劣的，也是我们需要讨论的情况。

（实线为重边，虚线为轻边）。

二、数学表达

现在，我们设集合 A 有 a个节点，树高为 \log_2 a ；所以集合 B 有 n-a个节点，树高为 \log_2 (n-a)。而总时间复杂度为 \log_2 a + \log_2 (n-a)。

然后理想时间复杂度为 \log_2 n。

三、数学推导（一）

首先，我们先来探究一下 \log_2 a + \log_2 (n-a) 和 \log_2 n 的关系。

我们先设 a 为定值， n 为 x 轴，所以： Desmos2D

我们注意到，无论 a 为何值，一定会有 \log_2 a + \log_2 (n-a) > \log_2 n 。

我们再拓展到3D：

Desmos3D

会有一段近似三角形的区域有 \log_2 a + \log_2 (n-a) > \log_2 n 。

这种方法无法精确计算 \log_2 a + \log_2 (n-a) - \log_2 n 的最值。

这种方法行不通。

四、数学推导（二）

上一章节我们设 a 为定值，行不通，所以我们再设 n 为定值，有趣的事情发生了：

Desmos2D

注意到，这是一个对称函数，当 a=n/2 时， \log_2 a + \log_2 (n-a) - \log_2 n 有最大值 \log_2 n/2。

好像完结了！！！。

五、严格证明

在第四章我们发现，当 a = \frac{n}{2} 时，表达式

f(a) = \log_2 a + \log_2 (n-a) - \log_2 n

取得最大值。

下面严格计算这个最大值，并证明在全局平衡二叉树的两条重链情况下，高度增量是有限的。

5.1 求最大值

令 x = a，则

f(x) = \log_2 x + \log_2 (n-x) - \log_2 n

利用对数性质合并：

f(x) = \log_2\left( \frac{x(n-x)}{n} \right)

由于 \log_2 单调递增，最大值出现在 \frac{x(n-x)}{n} 最大时。

令 g(x) = x(n-x)，这是开口向下的二次函数，对称轴在 x = \frac{n}{2} 处。

因此当 x = \frac{n}{2} 时：

f\left( \frac{n}{2} \right) = \log_2\left( \frac{\frac{n}{2} \cdot \frac{n}{2}}{n} \right) = \log_2\left( \frac{n}{4} \right)

5.2 代入树高比较

原二叉搜索树理想高度为 \log_2 n 。
在两条重链最劣分配 a = \frac{n}{2} 时，全局平衡二叉树的高度为：

H_{\max} = \log_2 a + \log_2 (n-a) = \log_2\left( \frac{n}{2} \right) + \log_2\left( \frac{n}{2} \right) = 2\log_2\left( \frac{n}{2} \right)

即：

H_{\max} = 2\log_2 n - 2

它与理想高度的差为：

\Delta H = H_{\max} - \log_2 n = \log_2 n - 2

（这正是前面算出的 f\left( \frac{n}{2} \right) = \log_2 n - 2。）

5.3 结论

对于全局平衡二叉树，即使在最差的两条重链平分节点数的情况下，总高度

H_{\max} = \log_2\left( \frac{n}{2} \right) + \log_2\left( \frac{n}{2} \right) \le 2\log_2 n - 2

仍然保持在 O(\log n) 级别，且比理想高度仅多出常数项 -2（当 n 足够大时，该差相对于 \log_2 n 可忽略）。

这证明了全局平衡二叉树的时间复杂度为 O(\log n)，尽管在两条重链情况下高度比严格平衡的 BST 略高，但仍在对数范围内，不影响渐近复杂度。

因此，全局平衡二叉树的复杂度得证。