我已经从排序数组创建了一个平衡 BST，我的问题是如何测试它。简单地测试一棵树是否平衡无济于事，因为即使是二叉树（注意 - 提到二叉树，而不是 BST）也可以平衡。测试一棵树是否是 BST 也不是 enof。我现在唯一的答案是检查它是否是balanced' &&bst`。现在这是一个复杂的两步测试过程。任何简单/更智能的解决方案？
问问题
132 次
2 回答
1
如果它是平衡的，它的深度最多为 log(n)+1，其中 n 是树/数组中的节点数。
检查树是否确实是 BST 可以简单地通过“按顺序”遍历节点并确保它们确实按顺序来完成。
顺便说一句，如果你有一个排序的数组，有一个非常简单的方法可以从中构建一个平衡的 BST，你运行的方式与二进制搜索相同 - 只是使用“插入”并应用“两侧”搜索。例如，假设您有：
1,2,3,4,5,6,7,8,9
您首先插入5，然后是3and 7，然后是其余的。
于 2013-09-19T03:37:49.763 回答
0
要回答您的问题：
您可以阅读一篇非常好的文章，特别是关于 BST 和排序数组之间的关系。
还是简单回答一下，一个 BST 可以显示出各种各样的麻烦，如果你不明智地选择构建它，如果数组没有排序，那么平衡 BST 的最佳保证就是构建它随机。观看 Eric Domaine 的视频（随机构建的 BST）
既然您已经从排序数组中构建了一个 BST，那么 alfasin [ depth is at most log(n) + 1] 中的建议是一个很好的检查......但我不同意，因为当你谈论 max深度就像检查每个节点并将其存储到某个空间中，因为你不会知道最深的节点，所以当你有一棵巨大的树时我觉得很难。
我建议找到根的高度。如果根的高度是 log(n) + 1，则它是平衡的。
让程序在堆栈中完成所有计算值的存储。
于 2013-09-19T03:56:42.920 回答