algorithm - 如何有效检查大型偏斜二叉搜索树的高度是否平衡？

Question

我读到了关于如何检查BST是否高度平衡的文章，并且真的被这个额外的问题吸引住了：
假设树是严重不平衡的就像，一边有一百万个节点，另一边有三个节点有没有这种算法破坏堆栈的场景你能修复这个实现使它永远不会破坏堆栈吗，即使给定了一个非常不平衡的树？
这里有什么好的策略？
我正在考虑做一个水平顺序遍历并跟踪深度，如果发现一个叶，并且当前节点深度大于叶节点深度+2，那么它是不平衡的但如何将此与高度检查结合起来呢？
编辑：下面是链接答案中的实现

IsHeightBalanced(tree)
    return (tree is empty) or 
           (IsHeightBalanced(tree.left) and
           IsHeightBalanced(tree.right) and
           abs(Height(tree.left) - Height(tree.right)) <= 1)

Answer 1

简要回顾：树被定义为空或带有指针的根节点。从左到左的子节点和从右到右的子节点，其中每个子节点依次是树，根节点出现在两个子节点中，并且没有节点出现在两个子节点中节点的深度是从根节点到达该节点所必须遵循的指针数树的高度为-1，如果它为null，否则出现在其上的节点的最大深度。叶是其子节点为空的节点。
首先，让我注意到两个不同的定义“平衡”提出的答案的联系问题。
EL balanced树是EL balanced当且仅当对于每个节点v，| height（v.left）-height（v.right）|<=1。
这是avl树的平衡条件。
当且仅当对于每对叶v，w，我们有|深度（v）-深度（w）<=1时，树是DF平衡的正如df指出的，一个节点的df balance意味着它的所有后代的df balance。
虽然二进制堆的平衡条件非常相似，但DF balance并没有用于我所知的算法，另外还需要尽可能地保持较深的叶。
我将概述三种测试平衡的方法。
平衡树的大小界限
展开递归函数以获得一个额外的参数maxdepth。对于每个递归调用，传递maxdepth-1，以便maxdepth大致跟踪还剩多少堆栈空间。如果maxDepth达到0，则将树报告为不平衡（例如，通过返回“无穷大”作为高度），因为适合主内存的平衡树可能没有那么高。
这种方法依赖于主存储器上的先验大小，如果不是在所有的理论模型中都是可用的，并且没有子树是共享的（protip：除非你非常小心，否则你的子树将在开发过程中的某个时刻共享。）我们还需要在最大给定大小的平衡树上设置高度界限。
通过相互归纳，我们证明了一个给定高度h的el平衡树的节点数的下界l（h）。
基本情况是

L(-1) = 0
L(0) = 1,

根据定义或多或少。归纳的情况更棘手高度h>0的EL平衡树是具有高度h-1的EL平衡子节点和另一个高度h-1或h-2的EL平衡子节点这意味着

L(h) = 1 + L(h - 1) + min(L(h - 2), L(h - 1)).

两边各加1，重新排列。

L(h) + 1 = L(h - 1) + 1 + min(L(h - 2) + 1, L(h - 1) + 1).

过了一会儿（ spoiler），我们发现

L(h) <= phi^(h + 2)/sqrt(5),
where phi = (1 + sqrt(5))/2 ~ 1.618.

然后将Max深度设为基数最大的基数对数节点，再加上一个小的常数，这取决于从属事物。
DF平衡，而不是写出归纳证明，我将呼吁你的直觉，最坏的情况是一个完整的二叉树底部有一个额外的叶子然后，对于Max深度的适当设置是节点的最大数目的基础-2对数，再加上一个小的常数。
迭代深化深度优先搜索
这是理论家对上述答案的解释。因为，由于某些原因，我们不知道我们的计算机有多少RAM（并且使用对数空间，这并不是说我们需要一个紧界），我们再次包含maxDepth参数，但是这次，我们使用它来隐式地将树截断到指定深度以下。如果树的高度回到界限以下，我们就知道算法运行成功了。或者，如果被截断的树是不平衡的，那么整棵树也是不平衡的。问题在于截断树是平衡的，但高度等于maxDepth然后增加maxdepth并重试。
最简单的重试策略是每次将maxdepth增加1。由于具有n个节点的平衡树具有高度O（logn），因此运行时间为O（logn）事实上，对于df平衡树，运行时间也是o（n），因为除了最后几次遍历外，截断树的大小每次都会增加2倍，从而产生一个几何级数。
另一种策略，每次使Max深度加倍，给出了EL平衡树的O（n）运行时间，因为最大H树，具有2 ^（H+ 1）-1个节点，远小于最小高度2H树，具有近似（φ^ 2）^ H节点。加倍的缺点是我们可能会使用两倍的堆栈空间。然而，当增量为1时，在定义l（h）时隐式构造的最小尺寸el平衡树族中，高度h树中h-k深度处的节点数是k次多项式，因此，最后几次扫描将产生一些超线性项。
临时改变指针
如果有父指针，那么很容易首先遍历深度，因为父指针可以有效地用于派生堆栈上的相关信息。如果我们没有父指针，但是可以临时改变树，那么，为了下降到子节点，我们可以将指向该子节点的指针分割为临时存储节点的父节点。问题是在上山的路上，我们是来自一个左孩子还是一个右孩子如果我们可以偷偷摸摸（比如说指针是2字节对齐的，或者因为平衡因子中有一个备用位，或者因为我们正在复制树以进行停止和复制垃圾收集，并且可以确定我们在哪个竞技场），那么这是一种方法。另一个测试假设树是二进制搜索树。事实证明，我们不需要额外的假设，但是： Explain Morris inorder tree traversal without using stacks or recursion。
有一点值得庆幸的是，据我所知，这种方法只适用于df平衡，因为堆栈上没有空间放置el平衡的部分结果。