应用对数导航树

既然你提到是向左走还是向右走,我就假设你说的是一棵二叉树。那样的话,我想你是对的,有办法。如果节点从左到右、从上到下编号,从1开始,则可以通过获取节点编号的log2来查找排名(在树中的深度)。要从根中再次找到该节点,可以使用数字的二进制表示,其中0=左,1=右。

例如:

• 二进制中的11是1011

• 我们总是忽略第一个1,因为它对于每个数字都存在(秩n的所有节点都是具有n+1个数字的二进制数,第一个数字是1)。我们左边是011,意思是从根开始向左,然后向右,然后向右。

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

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

好的,这个提议需要的字符比我在评论框中所能容纳的要多。Steven不相信知道节点在树中的深度是有用的。我想是的。我过去是错的,将来肯定是错的,所以我会努力解释这个想法是怎么起作用的,以期在现在不会错。如果我是,我会提前道歉。我几乎可以肯定,我是从我的算法和数据结构课程,使用CLR的书中得到的。请原谅在符号或术语上的任何错误,我已经有一段时间没有研究过这些东西了。

引用 wikipedia "

我们正在考虑一个具有任意分支度的完全树(其中二叉树的分支度为2)。此外,我们认为我们的节点有一个“位置值”,它是节点的位置值(从上到下,从左到右)的顺序。

现在,如果给我们一个位置值,我们可以按以下方式找到节点。取我们要查找的元素的位置值的log\u 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会从数组的角度来考虑这个问题,因为位置值是数组固有的。

至少与你的描述相似的是 Binary Heap

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

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

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

因此,例如,如果节点11是您所寻找的,那么您首先计算3.459的日志。然后。。。

2. 2-918<=大于0.5的分数加倍:右转并将整数减为1。
3. 1-836<=doubling.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)

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

在这一点上,我想知道是否有更简洁的方式来表达整个“基于日志的自上而下的节点选择”。。。

案例1:节点 有 指向其父级的指针

从 node parent 指向非空的指针 right_child 右\u儿童 和横移 left_child 只要它们不为空。

没有 指向父级的指针

从 root ,找到 节点 (包括 根 ). 然后在路径中找到非空的最新顶点(即节点) 右\u儿童 右\u儿童 和横移 左\u子项

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