应用对数来导航树

Question

我曾经知道一种使用对数从树的一片叶子移动到树的下一个“有序”叶子的方法。我认为它涉及获取“当前”叶子的位置值（排名？）并将其用作从根向下到新目标叶子的新遍历的种子 - 一直使用对数函数测试来确定是否沿着右或左节点向下到达叶子。

我已经不记得如何运用这项技术了。有谁可以重新介绍一下我吗？

我也不记得该技术是否要求树是平衡的，或者它是否适用于 n 树或仅适用于二叉树。任何信息将不胜感激。

Answer 1

既然您提到了向左还是向右，我假设您正在专门讨论二叉树。在这种情况下，我认为你是对的，有办法。如果您的节点从左到右、从上到下编号，从 1 开始，那么您可以通过取节点编号的 log2 来找到排名（树中的深度）。要从根再次找到该节点，可以使用数字的二进制表示形式，其中 0 = 左，1 = 右。

例如：

• n = 11

• 二进制中的 11 是 1011

• 我们总是忽略第一个 1，因为它每次都会出现number（第n级的所有节点都是n+1位的二进制数，第一位为1）。我们剩下 011，这意味着从根开始向左，然后向右，然后向右。

如果要找到下一个有序叶子，请获取当前叶子的编号并加一，然后使用此方法从根开始遍历。

我相信这只适用于平衡二叉树。

Answer 2

好的，这个提案需要的字符数超出了我在评论框中所能容纳的字符数。 Steven 不认为了解树中节点的深度是有用的。我认为是的。我过去错了，而且我确信我将来也会错，所以我将尝试解释这个想法是如何运作的，试图在现在不犯错。如果是的话，我会提前道歉。我几乎可以肯定我是从我的一门算法和数据结构课程中使用 CLR 书获得的。请原谅任何符号或术语的错误，我已经有一段时间没有研究这些东西了。

引用维基百科，“完全二叉树是一个二叉树，其中每个级别，除了可能的最后一个，都被完全填满，并且所有节点都尽可能远离左侧。”

我们正在考虑具有任意分支度的完整树（其中二叉树的分支度为二）。此外，我们正在考虑我们的节点有一个“位置值”，它是节点位置值的排序（从上到下，从左到右）。

现在，如果给定一个位置值，我们可以通过以下方式找到节点。取我们正在寻找的元素的位置值的log_base_n（这个元素的下限，我们想要一个整数）。从根向下遍历那么多次，减一。现在，开始查看该级别节点的所有子节点。您正在搜索的节点将在此集合中。

这是解释维基百科定义的附加部分的尝试：

"This depth is equal to the integer part of log2(n) where n 
 is the number of nodes on  the balanced tree. 

 Example 1: balanced tree with 1 node, log2(1) = 0 (depth = 0). 

 Example 2: balanced tree with 3 nodes, log2(3) = 1.59 (depth=1). 

 Example 3: balanced tree with 5 nodes, log2(5) = 2.32 
 (depth of tree is 2 nodes)."

这很有用，因为您可以简单地遍历到此级别，然后开始环顾四周。了解节点所在的深度非常有用且重要，因此您可以从那里开始查找，而不是从头开始查找。除非您知道自己位于树的哪一层，否则您将开始按顺序查看所有节点。

这就是为什么我认为了解我们正在搜索的节点的深度是有帮助的。

这有点奇怪，因为我们通常不关心树中的“位置值”。我可以理解为什么 Steve 会从数组的角度来考虑这个问题，因为位置值是数组所固有的。

-布莱恩·J·斯蒂纳尔-

Answer 3

至少类似于您的描述的是 二进制堆，在优先级队列中使用 ao 。

Answer 4

我想我已经找到了答案，或者至少是一份传真。

假设树节点已编号，从 1 开始，从上到下、从左到右。假设遍历从根开始，并在找到节点 X 时停止（这意味着父节点链接到其子节点）。另外，为了快速参考，节点 1 到 12 的以 2 为底的对数值为：

log2(1) = 0.0
log2(2) = 1
log2(3) = 1.58
log2(4) = 2
log2(5) = 2.32     
log2(6) = 2.58     
log2(7) = 2.807
log2(8) = 3
log2(9) = 3.16
log2(10) = 3.32
log2(11) = 3.459
log2(12) = 3.58

小数部分表示唯一的对角位置（注意节点 3、6 和 12 的小数部分都是 0.58）。另请注意，每个节点属于树的左侧或右侧，具体取决于对数小数部分是否小于或大于 0.5。抛开轶事不谈，查找节点的算法如下：

• 检查小数部分，如果小于 0.5，则向左转。否则右转。
• 从日志的整数部分减一，如果值达到零则停止。
• 将小数部分加倍，然后重新开始。

因此，举例来说，如果节点 11 是您要查找的节点，那么您首先计算对数 3.459。然后...

1. 3-459 <= 小于 0.5 的分数：左转并将整数减至 2。
2. 2-918 <= 大于 0.5 的双倍分数：右转并将整数减至 1。
3. 1-836 <=加倍 0.918 得到 1.836：但只有小数部分计数：右转并将先前的整数除以 0。完成！

通过适当的调整，相同的技术似乎适用于任何平衡的 n 叉树。例如，给定平衡三叉树，以下左、中或右边缘的选择再次基于日志的小数部分，如下所示：

between 0.5-0.832: turn left  (a one-third fraction range)
between 0.17-0.49: turn right  (another one-third fraction range)
otherwise go down the middle.  (the last one-third range)

通过将小数部分乘以 3 而不是 2 来调整算法。 ，对于那些想要测试最后一个陈述的人来说，这是一个快速参考：

log3(1) = 0.0
log3(2) = 0.63          
log3(3) = 1             
log3(4) = 1.26          
log3(5) = 1.46
log3(6) = 1.63
log3(7) = 1.77
log3(8) = 1.89          
log3(9) = 2

此时我想知道是否有一种更简洁的方法来表达整个“基于日志的自上而下的节点选择”。我很感兴趣，如果有人知道的话...

Answer 5

情况 1：节点有指向其父节点的指针

从节点开始，向上遍历parent指针，直到具有非空right_child的节点找到了。转到right_child并遍历left_child，只要它们不为空。

情况 2：节点没有指向父节点的指针

从根开始，查找到节点的路径（包括根 和节点）。然后找到路径中具有非空right_child的最新顶点（即节点）。转到 right_child 并遍历 left_child，只要它们不为 null。

在这两种情况下，我们都会从根向上或向下遍历到其中一个节点。这种遍历的最大值是树的深度的顺序，因此如果树是平衡的，则节点的大小是对数的。