非二叉树搜索和插入

Question

非二叉树搜索和插入

algorithmsearchdata-structurestreeinsertion

3

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

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

为了帮助搜索，我在构建树时给每个节点赋予了一个数字，以便每个节点的子节点都比它大，并且它右侧的所有节点也都比它大。

类似于这样：

这样我就可以在搜索中得到较长的时间。

问题出现在我想要插入节点时。如果我要将节点插入到任意位置，那么这个模型就行不通了。

我想了几种方法：

将新节点插入到所需位置，然后更新其后面所有节点的数量。
不使用单个数字来表示每个节点，而是使用数字数组。数组中的数字表示该特定级别上其位置。例如，节点1将是{0}。节点9将是{0,2}。节点7将是{0,0,1,2}。现在在插入时，只需要改变该级别上的数字即可。
忘记所有编号，只是比较每个节点，直到找到正确的节点。插入也不需要关心数字。

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

提前感谢您。

- user1610613

你在寻找什么——是展示的数字还是存储在节点中的未指定数据？如果是后者，我不明白节点编号如何让你对数据进行对数时间的搜索。数据和数字之间有什么联系呢？ - John Coleman

你为什么需要再次使用可变数量的子元素？ - Adrian Colomitchi

我正在搜索这个数字。它们只是为了帮助我搜索而创建的，没有其他联系。 - user1610613

如何从这个结构中获得log(n)的搜索时间？如果我正在搜索节点13，那么被搜索的节点序列是什么，为什么？ - Jim Mischel

它将跳过节点2以下的所有内容，具体方法是通过比较目标节点编号与搜索节点编号以及下一个节点来确定是否应该进入当前节点。例如，程序查看2，然后查看下一个节点8，并发现13大于8。因此，它转移到8，查看下一个节点9。13也大于9，所以它继续移动到9，没有下一个节点，因此它进入9的子节点。最后，我选择了选项2。 - user1610613

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rici · Accepted Answer

我了解你的问题是需要为每个节点分配一个唯一标识符，以便在子线性时间内查找给定其唯一ID的节点。对于瞬态（内存中）数据结构来说，通常不是问题，因为典型的树实现从不移动内存中的节点（直到节点被删除）。这使您可以使用节点的地址作为唯一标识符，从而提供O（1）访问。除C语言外的其他语言会将此装饰成类似于树迭代器或节点引用的对象，但在幕后原理是相同的。

然而，有时您确实需要能够以一种方式将固定的全时标识符附加到树节点上，以便对抗例如将树保留到永久存储并在不同的可执行图像中重新序列化的情况。

其中一个众所周知的技巧是使用浮点标识符。插入新节点时，将其ID指定为其直接邻居的平均值。为了进行此计算，我们假设左边有一个具有ID 0.0 的树节点，右边有一个具有ID 1.0 的节点，因此即使它是最新的左或右节点，每个节点也有两个邻居。特别地，根节点被赋予ID 0.5，这是虚拟边界节点0.0和1.0的平均值。

不幸的是，浮点精度并不是无限的，而且如果插入始终在树的随机位置，则此技巧效果最佳。如果您将所有节点插入到末尾，则会迅速耗尽浮点精度。您可以定期重新编号所有节点，但这违背了拥有永久不变唯一节点ID的目的。（对于某些问题域，这是可以接受的。）

当然，您实际上不必使用浮点数。在标准架构上，双倍精度有53位精度，如果您的插入是随机的，则足够了，如果总是在相同的位置插入，则很少；您可以通过（概念上）在高阶位之前定位固定的二进制点来使用64位无符号整数的所有64位。平均计算方式相同，只是需要特殊处理带有1.0值的计算。

这本质上与您将节点用索引向量标记的想法相同。该方案的优点是永远不会耗尽精度，缺点是向量可能会变得非常长。您还可以使用混合解决方案，其中仅在当前级别的精度不足时才启动新级别。