问题标签 [binary-search-tree]

我正在做这个让我感到困惑的家庭作业...

我提供了以下 BinarySearchTree 类

==================================================== ===============================

现在我有另一个班级学生......我想创建一个学生对象的二叉搜索树......

但是，当我这样做时，我收到以下错误：

有界不匹配：Student 类型不是 BinarySearchTree 类型的有界参数 > 的有效替代品

任何想法这里发生了什么......我无法弄清楚。

如何合并两个保持 BST 属性的二叉搜索树？

如果我们决定从一棵树中取出每个元素并将其插入另一个元素，则此方法的复杂O(n1 * log(n2))性为另一棵树（比如）。在这个操作之后，只有一个 BST 有节点。n1T1n2T2n1 + n2

我的问题是：我们能比 O(n1 * log(n2)) 做得更好吗？

我想对 BST 叶子中的所有值求和。显然，如果不遍历整棵树，我就无法到达树叶。这是真的？我可以在不花费 O(N) 时间的情况下到达树叶吗？

Im trying to put to an array the deepest path on a BST using a recursive algorithm, and im getting several difficulties... because the only thing that i get is the size of the longest path(equivalent to the height), and i cant put in the array the values regarding to the height of the BST...

Any help?

Sorry, I didn't expose the problem in the entire way. The only thing that I know to do this algorithm is this signature:

(I can use aux methods)

我有一段地狱般的时间试图弄清楚这一点。在我所见的任何地方，我似乎都只是在解释如何以非递归方式实际遍历列表（我真正理解的部分）。那里的任何人都可以敲定我最初如何准确地浏览列表并找到实际的前任/后继节点，以便我可以在节点类中标记它们吗？我需要能够创建一个简单的二叉搜索树并浏览列表并将空链接重新路由到前任/继任者。我有一些类似于以下的解决方案的运气：

有谁知道我如何在我的 rails config/environment.rb 文件中将 BST 用于 config.time_zone？

目前我已将其保留为 UTC，我正在考虑将 BST 添加到支持的时区列表中，然后扩展 Time 类以尊重这一点（> X 月的最后一个星期日 + 1 小时）

我在哪里可以找到支持的时区列表？

环顾四周，我发现了很多抱怨，但没有很多答案。这将尽快出现在guthub上。

干杯，道尔

我的 bst 必须能够处理重复的条目。有没有人有任何不需要过多代码的策略来解决这个问题？我想一直在右侧添加重复项，但这会弄乱 bst 顺序。例如，当副本有两个孩子又有两个孩子时会发生什么？插入副本很容易，但是如何处理它替换的节点？

我有一个关于如何从节点（根）中删除子节点的问题？由于我不能调用remove，如果我让孩子为空，那个孩子的孩子会向上移动吗？就像，我会把它初始化为空吗？还是我会指向孩子的孩子？

如果 T 是具有 n 个元素的平衡 BST，L 是左子树，R 是右子树，我如何证明它的深度小于或等于 2log(n) + 1？

我有一个归纳证明，但我不明白。

（我知道stackoverflow主要是面向编程的，但是我发现了一些关于二叉搜索树的问题并决定试一试，希望我没有做不好的事情。:)）

给定一个整数数组arr = [5, 6, 1]。当我们用这个输入以相同的顺序构造一个 BST 时，我们将“5”作为根，“6”作为右孩子，“1”作为左孩子。

现在，如果我们的输入更改为 [5,1,6]，我们的 BST 结构仍然是相同的。

那么给定一个整数数组，如何找到输入数组的不同排列的数量，从而产生与原始数组顺序上形成的 BST 相同的 BST？