logo标签列表

平衡树中节点数

pythonc++algorithmtree
5

我想到了一个有趣的问题，想知道是否有一种有效的方法来解决。所以基本上有一个平衡的二叉树，其中保存了id号码（它不是bst，因此没有正式的排列）。您有限定数量的查询来找出有多少个节点。保证对于每个节点E，左子树将具有与该节点E相同或更多的节点。询问程序查找有多少个节点的最佳方法是什么？ 例如，给定这样的树：

          1
      4      2
  3

该程序将输出以下内容：
 Query: 1
 Response: 4 2
 Query: 4
 Response 3
 Query: 3
 Response: 0 0 
 Query: 2
 Response: 0 0
 Answer: 4
实际的方法当然是在节点插入树中时进行计数，但我不认为这是你要寻找的答案。 - Wintermute
树已经建好了。我只是在查询节点数量。 - user3188300
据我理解，这个问题是关于在已知树是平衡的情况下，是否有比访问所有节点更有效的方法。 - Wintermute
例如，对于一个拥有10^100个节点的树，我只需最多使用70,000个查询。 - user3188300
我感到有必要指出，一棵拥有10^100个节点的树需要一个333位的地址空间来存储，假设每个节点只占用一个字节。 - Wintermute
显示剩余13条评论
2个回答
1

我终于把它想通了。

从条件

保证每个节点E的左子树将具有与该节点E上的右子树相同或多一个节点。

可以得出以下结论：

  1. 非叶子节点的数量可以从树的深度计算出来；它是2的深度-1次方。因此，有趣的事情是计算叶子节点的数量。
  2. 考虑到平衡条件，新节点只能插入或删除现有节点的唯一位置。（这意味着给定叶子节点的数量意味着只有一种叶子节点的模式。）
  3. 如果我们知道节点的左子树中叶子节点的数量，则我们知道右子树中的叶子节点（和节点）的数量要么相同，要么比其少一个。
  4. 由2和3可知，在右子树中只有一个叶子节点槽位我们无法在检查树的情况下确定它是否被填充。找到它是此算法的关键。
所以，利用3：假设我们有一棵（子）树T。我们知道其左子树中叶节点的数量为nleft。因此，我们知道其右子树中叶节点的数量为nleft或nleft-1，并且特别地，它最多为nleft。
我们进入右子树。知道这个子树中叶节点的最大数量，并知道它们平均分布在两侧的子树中，我们可以推断出两件事：
- 如果这个子树中叶节点的最大数量是奇数，则可疑插槽位于左侧，因为右侧不能比左侧更重。如果是偶数，则插槽位于右侧。 - 每个子子树中叶节点的最大数量是该子树中叶节点数量的一半，在左侧向上取整，在右侧向下取整。
这解决了问题的核心；其余部分是简单的递归。在C++中：
#include <cstddef>

// I'm using a simple node structure, you'd use query functions. The
// algorithm is not meaningfully altered by this.
struct node {
  node *left = nullptr, *right = nullptr;
};

struct node_counter {
  std::size_t leaf;      // number of leaf nodes,
  std::size_t trunk;     // number of trunk nodes,
  std::size_t depth;     // and depth of the inspected subtree.
};

// Interesting function #1: Given a right subtree and the leaf-count and
// depth of its left sibling, find the node that might or might not be there
node const *find_leaf(node const *branch, std::size_t leaf_count, std::size_t depth) {
  // We've gone down, found the slot. Return it.
  if(depth == 0) { return branch; }

  // The heart of the matter: Step into the subtree that contains the
  // questionable slot, with its maximum leaf node count and depth.
  return find_leaf(leaf_count % 2 ? branch->left : branch->right,
                   (leaf_count + 1) / 2, // int division
                   depth - 1);
}

// Recursive counter. This steps down on the left side, then infers the
// number of leaf and trunk nodes on the right side for each level.
node_counter count_nodes_aux(node const *root) {
  // leftmost leaf node is reached. Return info for it.
  if(!root->left) {
    return { 1, 0, 0 };
  }

  // We're in the middle of the tree. Get the counts for the left side,
  auto ctr_left   = count_nodes_aux(root->left);

  // then find the questionable slot on the right
  auto leaf_right = find_leaf(root->right, ctr_left.leaf, ctr_left.depth);

  return {
    // the number of leaf nodes in this tree is double that of the left
    // subtree if the node is there, one less otherwise.
    ctr_left.leaf * 2 - (leaf_right ? 0 : 1),

    // And this is just an easy way to keep count of the number of non-leaf
    // nodes and the depth of the inspected subtree.
    ctr_left.trunk * 2 + 1,
    ctr_left.depth + 1
  };
}

// Frontend function to make the whole thing easily usable.
std::size_t count_nodes(node const *root) {
  auto ctr = count_nodes_aux(root);
  return ctr.leaf + ctr.trunk;
}

为了尝试这个算法，我使用了下面这个非常丑陋的main函数。它只是构建一个有许多节点的树，在正确的位置插入新节点，并检查计数器是否按照正确的方式移动。它并不漂亮，也没有遵循最佳实践，如果您在生产中编写这样的代码，您应该被解雇。它是这样的，因为本答案的重点是上面的算法，我认为使其漂亮没有任何意义。
void fill_node(node *n) {
  n->left  = new node;
  n->right = new node;
}

int main() {
  node *root = new node;

  fill_node(root);

  fill_node(root->left);
  fill_node(root->right);

  fill_node(root->left->left);
  fill_node(root->left->right);
  fill_node(root->right->left);
  fill_node(root->right->right);

  fill_node(root->left->left->left);
  fill_node(root->left->left->right);
  fill_node(root->left->right->left);
  fill_node(root->left->right->right);
  fill_node(root->right->left->left);
  fill_node(root->right->left->right);
  fill_node(root->right->right->left);
  fill_node(root->right->right->right);

  std::cout << count_nodes(root) << std::endl;

  root->left ->left ->left ->left ->left  = new node;  std::cout << count_nodes(root) << std::endl;
  root->right->left ->left ->left ->left  = new node;  std::cout << count_nodes(root) << std::endl;
  root->left ->right->left ->left ->left  = new node;  std::cout << count_nodes(root) << std::endl;
  root->right->right->left ->left ->left  = new node;  std::cout << count_nodes(root) << std::endl;
  root->left ->left ->right->left ->left  = new node;  std::cout << count_nodes(root) << std::endl;
  root->right->left ->right->left ->left  = new node;  std::cout << count_nodes(root) << std::endl;
  root->left ->right->right->left ->left  = new node;  std::cout << count_nodes(root) << std::endl;
  root->right->right->right->left ->left  = new node;  std::cout << count_nodes(root) << std::endl;
  root->left ->left ->left ->right->left  = new node;  std::cout << count_nodes(root) << std::endl;
  root->right->left ->left ->right->left  = new node;  std::cout << count_nodes(root) << std::endl;
  root->left ->right->left ->right->left  = new node;  std::cout << count_nodes(root) << std::endl;
  root->right->right->left ->right->left  = new node;  std::cout << count_nodes(root) << std::endl;
  root->left ->left ->right->right->left  = new node;  std::cout << count_nodes(root) << std::endl;
  root->right->left ->right->right->left  = new node;  std::cout << count_nodes(root) << std::endl;
  root->left ->right->right->right->left  = new node;  std::cout << count_nodes(root) << std::endl;
  root->right->right->right->right->left  = new node;  std::cout << count_nodes(root) << std::endl;
  root->left ->left ->left ->left ->right = new node;  std::cout << count_nodes(root) << std::endl;
  root->right->left ->left ->left ->right = new node;  std::cout << count_nodes(root) << std::endl;
  root->left ->right->left ->left ->right = new node;  std::cout << count_nodes(root) << std::endl;
  root->right->right->left ->left ->right = new node;  std::cout << count_nodes(root) << std::endl;
  root->left ->left ->right->left ->right = new node;  std::cout << count_nodes(root) << std::endl;
  root->right->left ->right->left ->right = new node;  std::cout << count_nodes(root) << std::endl;
  root->left ->right->right->left ->right = new node;  std::cout << count_nodes(root) << std::endl;
  root->right->right->right->left ->right = new node;  std::cout << count_nodes(root) << std::endl;
  root->left ->left ->left ->right->right = new node;  std::cout << count_nodes(root) << std::endl;
  root->right->left ->left ->right->right = new node;  std::cout << count_nodes(root) << std::endl;
  root->left ->right->left ->right->right = new node;  std::cout << count_nodes(root) << std::endl;
  root->right->right->left ->right->right = new node;  std::cout << count_nodes(root) << std::endl;
  root->left ->left ->right->right->right = new node;  std::cout << count_nodes(root) << std::endl;
  root->right->left ->right->right->right = new node;  std::cout << count_nodes(root) << std::endl;
  root->left ->right->right->right->right = new node;  std::cout << count_nodes(root) << std::endl;
  root->right->right->right->right->right = new node;  std::cout << count_nodes(root) << std::endl;
}
“总是只有一个位置可以插入新节点或删除现有节点。”→你似乎有一个非标准的“平衡树”的定义。请参阅https://dev59.com/6Gsz5IYBdhLWcg3wQFi2 - Veedrac
@Veedrac 这个问题在问一个特定（左重）的平衡树排序。 - Wintermute
-1
int countnodes(ele,count)
{
 if(ele.right != null)
   {
      count += countnodes(ele.right,0);
   }
  if(ele.left != null)
  {
     count += countnodes(ele.left,0);
  }
  return count++; //got to count this node
}
我没有显式访问元素的权限。我只能查询左右，因为可能的节点数量非常大，所以我无法存储树。我不认为这个解决方案会起作用。 - user3188300
你可能需要检查一下你的代码，因为即使 OP 有访问树元素的权限，它也不会返回正确的值。 - SleuthEye
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接