非二叉树搜索和插入

Question

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

我构建了一个非二叉树，因此每个节点可以有任意数量的子节点（我认为称为n元树）

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

像这样的东西：

这样我就有更多的时间进行搜索

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

我想了几种方法可以做到这一点，

>

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

不要用一个数字来表示每个节点，而是用一个数字数组。数组中的数字将表示它在该特定级别上的位置。例如，节点1将是{0}。节点9将为{0，2}。节点7将是{0，0，1，2}。现在当插入时，我只需要改变那一层的数字。

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

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

提前感谢。

Answer 1

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

对于瞬态（内存中）数据结构，这通常不是一个问题，因为典型的树实现从不在内存中移动节点（直到它被删除）。这允许您将节点的地址用作唯一标识符，从而提供O（1）访问。C以外的语言将其打扮成一个类似于树迭代器或节点引用的对象，但实际上原理是一样的。

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

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

不幸的是，浮点精度不是无限的，如果插入总是在树中的随机位置，这种方法效果最好。如果在末尾插入所有节点，将快速耗尽浮点精度。您可以定期对所有节点进行重新编号，但这与拥有永久不变的唯一节点id的目的背道而驰。（但对于某些问题域，这是可以接受的。）

当然，你不必真的使用浮点。标准架构的双精度有53位，如果你的插入是随机的，这个精度就足够了，如果你总是在同一个地方插入，这个精度就很少了。你可以通过（概念上）在高阶位之前定位一个固定的二进制点来使用无符号64位整数的所有64位。平均计算的工作原理是一样的，只是你需要用1.0值来特殊处理计算。

这与您用索引向量标记节点的想法基本相同。这种方案的优点是永远不会超出精度，缺点是向量会变得很长。您也可以使用混合解决方案，仅当当前级别的精度用完时，才开始新的级别。