二叉树：获取元素的自签字路径 [英] Binary trees: Getting the path of an element from its signature

问题描述

假设你有一个二进制树，分类图像。每个节点是一个不同的二进制测试。当图像被馈送到树中，生成通过树的唯一路径。

Assume you have a binary tree which classifies images. Each node is a different binary test. When an image is fed to the tree, a unique path through the tree is generated.

一个路径被描述为一个二进制字是只要树的深度

A path is described as a binary word which is as long as the depth of the tree.

例如，对于一个2级的二进制树中，路径的例子将是（0,1）（（左，右），因此在树的从左侧的第二叶结束）。

For instance, for a 2-stage binary tree, an example of path would be (0,1) ((left,right) thus ending in the second leaf of the tree from the left).

我们还假设为任何图像被馈送到树中，所有节点测试是可执行的。因此，我们可以定义为任何图像的签名。这个签名是一个二进制字，长度是节点的数量

We also assume that for any image being fed to the tree, all node tests are executable. Thus, we can define a signature for any image: this signature is a binary word which length is the number of nodes.

例如，对于一个2级的二进制树中，签名的一个例子是 S = {0,1,1}

For instance, for a 2-stage binary tree, an example of signature would be s = {0,1,1}

S [I] 是第i个节点的测试二进制结果。

s[i] is the binary result from the test of the ith node.

我要寻找一种方式来自签字获得图像的路径。

I am looking for a way to get the path of an image from its signature.

做的幼稚的方法是从指数跳转到适当降低飞跃长签名的索引。

A naive way of doing it would be to jump from index to index of the signature with appropriate decreasing leap length.

不过，我不知道是否有可能是一个按位计算可能产生的结果（在签名中的索引可以在必要时重组）。

However, I wonder if there could be a bitwise calculation which could yield the result (The indexes in the signature can be reorganized if necessary).

这可能吗？如果是的话，怎么样？

Is this possible? If yes, how?

推荐答案

通过1阶段有1个测试。

With 1 stage there is 1 test.

通过2个阶段有1 + 2的测试。

With 2 stages there are 1+2 tests.

通过3个阶段有1 + 2 + 4测试。

With 3 stages there are 1+2+4 tests.

通过4个阶段有1 + 2 + 4 + 8的测试。

With 4 stages there are 1+2+4+8 tests.

通过5个阶段有1 + 2 + 4 + 8 + 16 = 31的测试。

With 5 stages there are 1+2+4+8+16=31 tests.

一种方法计算的路径更快是测试的第一比特，然后提取相应组映射到在接下来的4阶段15bits的。只有2 ** 15 = 32768不同的选择，这样的路径可以在表中查找。

One approach to computing the path faster is to test the first bit, and then extract the corresponding set of 15bits that map to the next 4 stages. There are only 2**15=32768 different choices so the path can be looked up in a table.

伪code：

 if (x&(1<<30))
    x >>= 15;
 path = lookup[x & 0x7fff];

查找是2 ** 15长数组，你可以precalculate。

lookup is a 2**15 length array that you can precalculate.

这篇关于二叉树：获取元素的自签字路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！