algorithm - 具有n = 2 ^ k-1个节点的完整二叉树。描述一种用O(lg n)最坏情况下的时间复杂度执行此操作的算法

Question

你能帮我解决这个问题吗？
假设有一个计算机网络，它的拓扑结构是一个完整的二叉树，n=2^k-1
节点，其中k 1。假设数据包从一个节点传输到
它的孩子（如果有的话）在树上需要一个恒定的时间，即O（1）时间。另外，假设没有数据包丢失鉴于此，您需要从根中向网络中的每个节点发送一个数据包，其中O（LG n）的最坏情况下的时间复杂度。两个节点
在树中，如果使用不同的边，则可以同时传输数据包在收到来自父方的数据包后，左、右子方拥有该数据包的单独副本。而且，正如我之前所说的，在任意一对父母和孩子之间有一个单独的通信链接。
如何编写算法，用O（LG n）最坏情况下的时间复杂度来完成这一算法
如何证明算法的最坏时间复杂度是O（LG n）？
我已经尝试了一个在线发现算法，但是它给出了O（n）的复杂度。
因为名声不好，我不能把我为解决问题而制作的图片发给你们。
假设：
数据包从一个节点传输到树中它的一个子节点（如果有的话）需要恒定的时间，即o（1）时间。在上图中，根节点向其子节点发送数据包所需的时间o（1）是恒定的。拓扑中的所有父子组合都将相同。
没有数据包丢失。鉴于此，您需要从根中向网络中的每个节点发送一个数据包，其中O（LG n）的最坏情况下的时间复杂度。在上图中，从根节点到网络中其他节点的所有节点都获取了根节点发送的数据包。拓扑中没有数据包丢失

/* Given a binary tree, return true if the tree is complete
   else false */
bool isCompleteBT(struct node* root)
{
  // Base Case: An empty tree is complete Binary Tree
  if (root == NULL)
    return true;

  // Create an empty queue
  int rear, front;
  struct node **queue = createQueue(&front, &rear);

  // Create a flag variable which will be set true
  // when a non full node is seen
  bool flag = false;

  // Do level order traversal using queue.
  enQueue(queue, &rear, root);
  while(!isQueueEmpty(&front, &rear))
  {
    struct node *temp_node = deQueue(queue, &front);

    /* Ceck if left child is present*/
    if(temp_node->left)
    {
       // If we have seen a non full node, and we see a node with non-empty left child, then the                                                
       // given tree is not a complete Binary Tree
       if (flag == true)
         return false;

       enQueue(queue, &rear, temp_node->left);  // Enqueue Left Child
    }
    else // If this a non-full node, set the flag as true
       flag = true;

    /* Ceck if right child is present*/
    if(temp_node->right)
    {
       // If we have seen a non full node, and we see a node with non-empty left child, then the   
       // given tree is not a complete Binary Tree
       if(flag == true)
         return false;

       enQueue(queue, &rear, temp_node->right);  // Enqueue Right Child
    }
    else // If this a non-full node, set the flag as true
       flag = true;
  }

  // If we reach here, then the tree is complete Bianry Tree
  return true;
}

我们使用上述算法来检验它是否满足完全二叉树的要求。如果算法返回真，那么我们的拓扑结构是完全二叉树，并且传输数据的假设是真的。
时间复杂度：O（n），其中n是给定二进制树中节点的数目

Answer 1

回答这个问题的关键是要明白这个问题是关于一个计算机网络，而不仅仅是关于一台计算机根节点不需要跟踪到网络中所有节点的传递；它只需要将足够的工作委托给其子节点，以确保传递最终到达网络中的所有节点。
在这种情况下，根节点应该只向其直接子节点发送数据包。当每个非根节点从其直接父节点接收数据包时，应将数据包重新传输到其直接子节点这允许每个级别的节点并行工作，从而实现所需的总交付时间的日志（n）缩放。