多数树评估

Question

考虑一个深度为 h 的完整三元树，它由一个根连接到三个深度为 h - 1 的完整三元树组成。有 n = 3^h 个叶子，每个叶子都有一个与之关联的布尔值。每个内部节点，包括根节点，都等于其大多数子节点的值。

下面是深度为 2 的树的示例：

给定叶子输入向量 [0, 0, 1, 0, 1, 0, 1, 1, 1]，我们想找到树的根。为了找到根，我们可以评估所有叶子和内部节点（即 3^h 操作）。但是我们也许能够评估更少的节点。在上面的示例中，我们可以看到第一个内部节点（最左边）的值可以在检查其前两个子节点后进行评估。同样在depth = 1时，前两个节点足以找到树的根。

我一直在思考这个问题，但我找不到解决问题的好方法。

import numpy as np
import random

class node:
def __init__(self):
    self.low = None
    self.mid = None
    self.high = None

def put(self, low, mid, high):
    self.low = low
    self.mid = mid
    self.high = high
    return self

class ternary_tree:

def __init__(self, leaves, count= 0):
    self.leaves = leaves
    self.root = node()
    self.value = None
    self.count = count

def get_root(self):
    self.root.put(self.leaves[0], self.leaves[1], self.leaves[2])
    self.value = majority(self.root)
    return self.value

def majority(node):
    global ops_count
    r1, r2, r3 = random.sample([node.low, node.mid, node.high], 3)
    if r1 > 0:
        ops_count += 1
        if r2 > 0:
            ops_count += 1
            return 1;
        elif r3 > 0:
            ops_count += 1
            return 1;
        else:
            return 0;
    else:
        ops_count += 1
        if r2 == 0:
            ops_count += 1
            return 0;
        elif r3 == 0:
            ops_count += 1
            return 0;
        else:
            return 1;

if __name__ == "__main__":
    h = 2 # depth of the tree
    my_leaves = [random.randint(0,1) for i in range(0, 3**h)] #input vector
    ops_count = 0 #Counting the number of steps
    nb_trees = len(my_leaves) // 3
    my_trees = [ternary_tree(leaves=my_leaves[i:i+3]) for i in range(0, nb_trees)]
    new_leaves = []
    t1, t2, t3 = random.sample(my_trees, 3)
    new_leaves.append(t1.get_root())
    new_leaves.append(t2.get_root())
    if new_leaves[0] == new_leaves[1]:
        new_leaves.append(new_leaves[0])
    else:
        new_leaves.append(t3.get_root())
    ternary_tree(leaves=new_leaves).get_root()

我认为代码可以完成工作，但就它仍然检查所有内部节点并且不跳过冗余节点而言，它不是最佳的。我认为正确的方法是使用像二叉搜索树这样的递归算法，但我无法在 BST 和多数树评估之间做出 link。

如果您能告诉我如何解决这个问题，我将不胜感激。谢谢！

插图来自这里：http://www.math.ucsd.edu/~gptesler/188/MajTree/majtree.html。

Answer 1

确实，递归将是找到根值的方法。我真的没有看到创建树 数据结构 的必要：当所有叶值的值都作为列表输入时，我们就真正拥有了合适格式的所有信息。

下面是 majority 函数在只给定叶值列表时的样子：

import random

def majority(leaves):
    counter = 0

    def recur(start, size):
        nonlocal counter
        if size == 1:
            counter += 1  # about to access a leaf's value
            return leaves[start]
        size //= 3
        # Randomly choose which child we will leave as "plan B" in case
        #  two others give opposite values
        last = random.randint(0, 2)
        # Get the values of the two other children, using recursion
        val1 = recur(start + ((last+1)%3)*size, size)
        val2 = recur(start + ((last+2)%3)*size, size)
        # If equal, we do not need to retrieve the remaining child's value
        if val1 == val2:
            return val1
        # Too bad,... we need the value of the third child to break the tie
        return recur(start + last*size, size)
    
    rootval = recur(0, len(leaves))
    return rootval, counter

你可以这样称呼它：

h = 2
leaves = [random.randint(0,1) for i in range(0, 3**h)]

rootval, counter = majority(leaves)

print("The leaves are {}".format(leaves))
print("Accessed {} leaves to find that root's value is {}".format(counter, rootval))

多数树评估

Majority tree evaluation

algorithm

tree

ternary-tree