重新平衡一个任意的BST？
问题：修改一个BST，使它变得尽可能平衡。不用说，你应该尽可能有效率地做这件事。
提示：面试官说这是一个合乎逻辑的问题，如果你换位思考就会得到答案。没有困难的编码涉及。
-->话虽如此，但我不认为他希望我指向AVL/RB树。
我的解决方案是：我提出，我将对树进行顺序遍历，将中间元素作为新树的根（我们称之为新根）。然后到中间元素的左边，取它的中间元素作为树的左子树的根，生成新根。同样地，正确的部分也要这样做。递归地这样做将给出最优的平衡BST。
共有1个答案
您可能需要研究一下Day-Stout-Warren算法，它是一种O(n)时间、O(1)空间算法，用于将任意二叉搜索树重新成形为完整的二叉树。直观地看，该算法的工作原理如下：
- 使用树旋转，将树转换为退化链表。
- 通过对链表应用选择性旋转，将链表转换回完全平衡的树。
这种算法的美妙之处在于，它在线性时间内运行，只需要恒定的内存开销；实际上，它只是重塑底层树，而不是创建一个新树并复制旧数据。编写代码也相对简单。
-
我想使用来并行化处理一组远程存储的数量未知的JSON文件（文件的数量不是预先知道的）。这些文件的大小可以有很大的不同，从每个文件1条JSON记录到其他文件中的100,000条记录不等。在本例中，JSON记录意味着在文件中表示为一行的自包含JSON对象。 我真的想要使用流来实现这一点，所以我实现了这个: 我遇到的问题是，虽然一开始流的并行化效果很好，但最终最大的文件仍留在一个线程中处理。我相信最近的
-
我们有一个相对简单的分片MongoDB设置：4个分片，每个分片是一个副本集，至少有3个成员。每个集合都由从大量文件加载的数据组成;每个文件都被赋予一个单调递增的ID，并且根据ID的哈希完成分片。 我们的大部分产品都在按预期工作。然而，我有一个集合似乎没有正确地将块分布到各个碎片上。在创建索引之前，集合加载了大约30GB的数据，并且进行了分片，但是据我所知，这并不重要。以下是该集合的统计数据: 这个
-
本文向大家介绍负载平衡的意义什么？相关面试题，主要包含被问及负载平衡的意义什么？时的应答技巧和注意事项，需要的朋友参考一下 在计算中，负载平衡可以改善跨计算机，计算机集群，网络链接，中央处理单元或磁盘驱动器等多种计算资源的工作负载分布。负载平衡旨在优化资源使用，最大化吞吐量，最小化响应时间并避免任何单一资源的过载。使用多个组件进行负载平衡而不是单个组件可能会通过冗余来提高可靠性和可用性。负载平衡通
-
这是我读完后想到的一个问题：Storm并行中的“任务”是什么 如果我需要在bolt的内部状态中保留一些信息，例如，在经典的单词计数用例中，在一个hashmap中保留在bolt中看到的每个单词的计数。执行“rebalance”命令后，将bolt的任务移到另一个执行器，该执行器可能在另一个JVM中，甚至可能在另一台机器中。bolt的内部状态（本例中的字数hashmap）是否会转移到新环境（instan
-
在Kubernetes中创建负载平衡器类型的服务时，它是创建一个全新的外部负载平衡器，还是只为负载平衡器类型的第一个服务创建一个负载平衡器，并将该负载平衡器重新用于负载平衡器类型的所有后续服务？ 这个问题特别重要，因为为每个服务构建一个单独的负载平衡器对我来说成本太高。 如果它特定于云提供商，我使用Azure，但我很想知道其他云提供商是否不同。
-
我正在尝试重新平衡正在运行的Apache Storm(0.9.5)拓扑中的bolt执行程序的数量。当我对Nimbus节点执行命令时，它接受命令行输入，但当我在Storm UI中查看时，执行者的数量不会改变。 是不是有一个限制，我没有意识到，就像再平衡不能增加执行者的总数，只能把他们从一个螺栓移动到另一个螺栓？