应用对数导航树

Question

我曾经知道一种使用对数从树的一片叶子移动到树的下一个"有序"叶子的方法.我认为它涉及获取"当前"叶子的位置值(等级？)并将其用作从根到新目标叶子的新遍历的种子 - 一直使用日志函数测试来确定是否按照右侧或左侧节点向下到叶子.

我不再记得如何运用这种技术.任何人都可以重新介绍我吗？

我也不记得该技术是否要求树平衡,或者它是否在n树或二叉树上工作.任何信息,将不胜感激.

Answer 1

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

假设树节点已编号，从 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 <=加倍 .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

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