algorithm - 非二叉树搜索和插入

Question

我搜索了一下，但没有找到这个问题的答案..

我构建了一个非二叉树，所以每个节点可以有任意数量的 child (我认为称为 n-ary 树)

为了帮助搜索，我在构建树时给每个节点一个编号，这样每个节点的子节点都会变大，它右边的所有节点也会变大。

像这样:

这样我就可以得到搜索的登录时间

当我想插入节点时，问题就来了。如果我想在末尾以外的任何地方插入节点，这个模型将不起作用。

我想了几个办法，

1. 在所需位置插入新节点，然后更新其“后面”的所有节点数。

2. 不要使用单个数字来表示每个节点，而是使用数字数组。数组中的数字将代表它在该特定级别上的位置。例如，节点 1 将为 {0}。节点 9 将为 {0,2}。节点 7 将为 {0, 0, 1, 2}。现在插入时，我只需要更改该级别的数字即可。

3. 忘记所有编号，只比较每个节点，直到找到正确的节点。插入也不需要关心数字。

我的问题是，哪种方式会更好？我不确定使用整数数组来表示每个节点是否非常快..也许它仍然比第一种方式快？还有其他方法吗？

提前谢谢你。

Answer 1

我了解到您遇到的问题是为每个节点分配一个唯一标识符，以便您可以在亚线性时间内找到给定其唯一 ID 的节点。

这对于 transient (内存中)数据结构通常不是问题，因为典型的树实现从不移动内存中的节点(直到它被删除)。这使您可以将节点的地址用作唯一标识符，从而提供 O(1) 访问。 C 以外的语言将其包装在一个对象中，例如树迭代器或节点引用，但在底层原理是相同的。

但是，有时您确实需要能够将一个固定的标识符附加到树节点，以一种具有弹性的方式，例如，将树持久化到永久存储和然后在不同的可执行镜像中重新序列化它。

一个众所周知的技巧是使用 float id。当插入一个新节点时，它的 id 被分配为其直接邻居的平均值。出于此计算的目的，我们假设树的左侧有一个 ID 为 0.0 的节点，右侧有一个 ID 为 1.0 的节点，因此每个节点有两个邻居，即使它是新的最左边或最右边的节点。特别是，根节点的 ID 为 0.5，这是 0.0 和 1.0 虚边界节点的平均值。

不幸的是，浮点精度不是无限的，如果插入总是在树中的随机位置，则此技巧最有效。如果将所有节点都插入到最后，浮点精度将很快耗尽。您可以定期对所有节点重新编号，但这违背了拥有永久不变的唯一节点 ID 的目的。 (不过，对于某些问题领域，这是可以接受的。)

当然，您不必真的使用 float 。标准架构上的 double 具有 53 位精度，如果您的插入是随机的，这就足够了；如果您总是在同一位置插入，则精度非常低；您可以通过(概念上)在高位之前定位一个固定的二进制小数点来使用无符号 64 位整数的所有 64 位。平均计算的工作原理相同，只是您需要使用 1.0 值对计算进行特殊计算。

这与您使用索引向量标记节点的想法基本相同。该方案的优点是永远不会超出精度，缺点是向量可能会变得很长。您还可以使用混合解决方案，只有当您用完当前关卡的精度时，您才开始一个新的关卡。