问题标签 [data-structures]

上图来自“维基百科关于 AVL 树的条目”，维基百科指出它是不平衡的。这棵树怎么还不平衡？这是文章的引述：

节点的平衡因子是其右子树的高度减去其左子树的高度，平衡因子为 1、0 或 -1 的节点被认为是平衡的。具有任何其他平衡因子的节点被认为是不平衡的，需要重新平衡树。平衡因子要么直接存储在每个节点上，要么根据子树的高度计算。

左子树和右子树的高度均为 4。左树的右子树的高度为 3，但仍然比 4 小 1。有人可以解释我缺少什么吗？

我想知道这里是否有人曾经使用过跳过列表。它看起来与平衡二叉树具有大致相同的优势，但实现起来更简单。如果有，您是自己编写的，还是使用预先编写的库（如果有，它的名称是什么）？

我想知道处理大量移动对象（球体、三角形、框、点等）的最佳数据结构是什么？我试图回答两个问题，最近邻和碰撞检测。

我确实意识到，传统上，像 R 树这样的数据结构用于最近邻查询，而 Oct/Kd/BSP 用于处理静态对象或很少移动对象的碰撞检测问题。

我只是希望那里有其他更好的东西。

我感谢所有的帮助。

对于不需要随机访问列表元素的简单链表，使用std::list而不是有任何显着优势（性能或其他方面）std::vector吗？如果需要向后遍历，在迭代其元素之前使用std::slist和列表会更有效吗？reverse()

有没有内置的方法在 C++ 中对 CArray 进行排序？

因此，如果我必须在哈希表或前缀树之间进行选择，那么导致我选择其中一个的区别因素是什么。从我自己幼稚的角度来看，似乎使用 trie 有一些额外的开销，因为它没有存储为数组，但就运行时间而言（假设最长的键是最长的英文单词）它本质上可以是 O (1) (关于上限)。也许最长的英文单词是50个字符？

一旦获得索引，哈希表就会立即查找。然而，散列密钥以获取索引似乎可以轻松完成近 50 个步骤。

有人可以为我提供一个更有经验的观点吗？谢谢！

我最近读到在 C 中使用灵活的数组成员是糟糕的软件工程实践。但是，该声明没有得到任何论据的支持。这是公认的事实吗？

（灵活的数组成员是 C99 中引入的一项 C 功能，可以将最后一个元素声明为未指定大小的数组。例如：）

我试图想出一个命名约定来准确地传达我正在设计的课程中发生的事情。在第二点上，我试图在两个几乎等效的用户 API 之间做出决定。

情况如下：

我正在构建一个科学应用程序，其中一个中央数据结构具有三个阶段：1）积累、2）分析和 3）查询执行。

在我的例子中，它是一种空间建模结构，在内部使用 KDTree 来划分 3 维空间中的点集合。每个点都描述了周围环境的一个或多个属性，对测量本身具有一定的置信度。

在向集合添加（可能大量）测量后，对象的所有者将查询它以获取适用字段内某处新数据点处的插值测量。

API 看起来像这样（代码是用 Java 编写的，但这并不重要；为清楚起见，代码分为三个部分）：

对于我的特定问题域，可以在第 2 节期间执行少量增量工作（将点划分为平衡的 KDTree）。

在第 3 节期间可能会发生少量工作（执行一些线性插值）。

但是在第 2 节和第 3 节之间必须执行大量工作（构建核密度估计器并执行快速高斯变换，使用泰勒级数和 Hermite 函数，但这完全是题外话） 。

有时在过去，我只是使用惰性求值来构造数据结构（在这种情况下，它会在第一次调用“interpolateAt”方法时），但是如果用户调用“field.add ()" 方法，我必须完全丢弃那些数据结构并从头开始。

在其他项目中，我要求用户显式调用“object.flip()”方法，从“附加模式”切换到“查询模式”。这样的设计的好处是用户可以更好地控制核心计算开始的确切时刻。但是对于 API 使用者来说，跟踪对象的当前模式可能会很麻烦。此外，在标准用例中，调用者在开始发出查询后永远不会向集合添加另一个值；数据聚合几乎总是完全在查询准备之前。

你们是如何设计这样的数据结构的？

您是否更喜欢让对象懒惰地执行其繁重的分析，当新数据进入集合时丢弃中间数据结构？或者您是否需要程序员显式地将数据结构从附加模式转换为查询模式？

你知道像这样的对象有什么命名约定吗？有没有我没有想到的模式？

编辑：

我在示例中使用的名为“ContinuousScalarField”的类似乎有些困惑和好奇。

通过阅读这些维基百科页面，您可以很好地了解我在说什么：

• http://en.wikipedia.org/wiki/Scalar_field

• http://en.wikipedia.org/wiki/Vector_field

假设您想创建一个地形图（这不是我的确切问题，但在概念上非常相似）。因此，您在一平方英里的区域内进行了一千次高度测量，但您的测量设备在高度上的误差范围为正负 10 米。

一旦你收集了所有的数据点，你就可以将它们输入一个模型，该模型不仅可以插值，还可以考虑每次测量的误差。

要绘制地形图，您需要在模型中查询要绘制像素的每个点的高程。

至于单个类是否应该同时负责追加和处理查询的问题，我不是 100% 肯定，但我认为是的。

这是一个类似的示例：HashMap 和 TreeMap 类允许添加和查询对象。没有用于添加和查询的单独接口。

这两个类也与我的示例相似，因为必须持续维护内部数据结构以支持查询机制。HashMap 类必须定期分配新内存，重新散列所有对象，并将对象从旧内存移动到新内存。TreeMap 必须使用红黑树数据结构持续保持树平衡。

唯一的区别是，如果我的班级一旦知道数据集已关闭，它就可以执行所有计算，那么它将表现最佳。

在我的数据库中，我有定义类型的表，例如

表：出版物类型

它通过 ID 键与具有字段TypeID的发布表相关联。

然后，我在我的 .NET 应用程序中创建了一个 PublicationTable 数据表，我想根据发布类型对其进行过滤。例如，以下函数为我提供了特定作者和出版物类型的出版物数量。

要调用此函数以获取特定类型作者的文章计数，我可以

1. 用两个整数调用函数

   countPublications(作者ID, 1)

2. 设置一个枚举，以便我可以编写

   countPublications(authorID, pubType.Article)

   或者

3. 以某种方式使用发布类型表来过滤发布数据集，但我不知道如何做到这一点。

我应该考虑哪些其他方法。

谢谢

append()列表方法和列表方法有什么区别extend()？