实现BST的最有效方法是什么？find（value）函数针对x86上树中的随机值进行优化？[关闭]
假设我们有一个深度$N$的二叉搜索树，其中每一层都是满的，我们提前知道树会有多大，我们会大量运行find（value）函数。我们想要找到的值（整数）将在可以存储在此bst树中的可接受值上是一致随机的。在x86架构上实现具有此特性的BST的最有效方法是什么？
请按所写的回答问题。任何答案的效果，有更好的数据结构或方式来执行这个任务将不会对我有用。
想到的唯一想法是将树实现为数组，并按如下方式存储节点：
a n=1
/ \
b c n=2
/ \ / \
d e f g n=3
节点的内存布局是线性的，所以一级是第一个元素，然后是二级的所有元素，按从小到大的顺序排列，每个级别依此类推。
[a,b,c,d,e,f,G]
但是，我不确定如何说服自己这是最好的，或者即使它是最好的。如有任何帮助，我们将不胜感激。
共有1个答案
使用固定大小、完整的BST，您可以正确地认为，按照您所描述的顺序排列的数组将工作得最好，使用公式2*x+1=左子项的索引和2*x+2=右子项的索引，其中x是父节点的索引。例如，在存储为数组[a,b,c,d,e,f,g]的树中，c=2的索引，因此左子级为2*2+1=5(f)，右子级为2*2+2=6(g)。这仅适用于除最后一层外的每一层都已满的情况，因为最后一层必须完全向左加权
所以是的，如果树不改变大小，并且每个级别都是满的，那么数组就是完美的，因为它不需要任何额外的内存，而且您仍然可以利用BST属性。
如果您一般知道大小，但可能很少添加或删除节点，那么一个自平衡BST将是一种方法。AVL树最适合使用很多find（）操作和很少的insert（）和delete（）操作的树。
-
问题内容： 我有一个相当大的数据集和一个需要两个联接的查询，因此查询的效率对我来说非常重要。我需要根据联接的结果从数据库中检索3个满足条件的随机行。这里指出最明显的解决方案效率低下，因为 [这些解决方案]需要对所有表进行顺序扫描（因为需要计算与每一行关联的随机值-以便可以确定最小的行），即使对于中等大小的表也可能相当慢。 但是，那里的作者建议的方法（其中num_value是ID）对我不起作用，因为
-
什么是树上随机游走？我们可以假设给定一棵树，树的某个结点上有一个硬币，在某一时刻硬币会等概率地移动到邻接结点上，问硬币移动到邻接结点上的期望距离。 1. 树上随机游走用到的定义： ● 所讨论的树 ● 结点的度数 ● 结点与 v 结点之间的边的边权 ● 结点的父结点 ● 结点的子结点集合 ● 结点的兄弟结点集合 2. 向父结点走的期望距离 设代表 u 结点走到其父结点的期望距离，则有： 分
-
问题内容： 假设您有一个存储有序树层次结构的平面表： 这是一个图，我们在这里。根节点0是虚构的。 您将使用哪种简约方法将其作为正确排序，正确缩进的树输出到HTML（就此而言，还是文本）？ 进一步假设您只有基本的数据结构（数组和哈希图），没有带有父/子引用的奇特对象，没有ORM，没有框架，只有两只手。该表表示为结果集，可以随机访问。 可以使用伪代码或简单的英语，这纯粹是一个概念性问题。 额外的问题：
-
给定一个
-
我看到的替换优先级队列比较器的公认答案是在新的比较类中重载操作符。 然而，我想为队列实现几个（10）不同的比较函数，并在运行时在main（）中创建pq时选择一个。我必须做10个不同的比较类还是有更简单的方法来做到这一点？
-
问题内容： 我有一个非常大的NumPy数组 我想检查数组的第一列中是否存在一个值。我有很多本地方法（例如遍历每一行并进行检查），但是鉴于数组的大小，我想找到最有效的方法。 谢谢！ 问题答案： 怎么样 编辑：我认为以与@detly版本相同的方式实现