c++ - 将链表转换为二叉搜索树，执行操作并将树作为列表返回

Question

我有以下问题: 我有一行数字，我必须阅读。该行的第一个数字是我必须对序列的其余部分执行的操作量。 我必须执行两种类型的操作:

• 删除 - 我们删除当前数字之后的数字，然后我们在序列中向前移动 X 步，其中 X = 删除元素的值)
• 插入——我们在当前数字之后插入一个值为(当前元素的值-1)的新数字，然后我们在序列中向前移动 X 步，其中 X = 当前元素的值(即不是新元素)

如果当前数字的值为偶数，我们执行“删除”，如果值为奇数，则执行“插入”。 在操作数量之后，我们必须打印整个序列，从我们结束操作的数字开始。

正确工作的例子: 输入:3 1 2 3 输出:0 0 3 1

3 是第一个数字，它成为 OperCount 值。

• 第一次操作:

序列:1 2 3，第一个元素:1

1 是奇数，所以我们插入 0(currNum 的值-1)

我们向前移动 1(currNum 的值)

输出序列:1 0 2 3，当前位置:0

• 第二个操作:

0 是偶数，所以我们删除下一个值 (2)

向前移动删除元素的值(2):

• 从 0 到 3
• 从 3 到 1

输出序列:1 0 3，当前位置:1

• 第三个操作:

1 是偶数，所以我们再次插入值为 0 的新元素

按当前元素的值 (1) 移动到创建的 0。

输出序列:1 0 0 3，当前位置:第一个0

现在是交易，我们已经达到了最终条件，现在我们必须打印整个序列，但从当前位置开始。 最终输出: 0 0 3 1

我有工作版本，但它使用链表，因此，它没有通过所有测试。链表遍历太长，这就是为什么我需要使用二叉树，但我有点不知道如何开始。如果有任何帮助，我将不胜感激。

Answer 1

首先重新定义操作，把大部分(但不是全部)的工作放到一个容器对象中:我们要容器对象支持4个操作:
1) 从 [first,limit) 构建一对输入随机访问迭代器
2) insert(K) 在位置K找到值X，在其后插入一个X-1并返回X
3) remove(K) 在位置K找到值X，删除它并返回X
4) size() 报告内容的大小

容器外的工作只会跟踪对 K 的增量更改:
K += insert(K); K %= size(); 或者
K += remove(K); K %= size(); 在阅读 size() 之前请注意序列点的重要性

容器数据只是一个root指向一个节点。

struct node {
  unsigned weight;
  unsigned value;
  node* child[2];
  unsigned cweight(unsigned s)
    { return child[s] ? child[s]->weight : 0; }
};

容器成员函数insert和 remove将是递归静态的包装器 insert和 remove每个函数都采用 node*&除了K.
每个递归的第一件事 insert或 remove必须做的是:
if (K<cweight(0))递归传递 (child[0], K) ;
else if ((K-=cweight(0))>0)递归传递 (child[1], K-1) ;
否则执行基本操作(读取结果，创建或销毁节点)
这样做之后，您可以在递归调用堆栈的每个级别上固定权重(从您为插入工作所做的工作开始或在该级别之上进行删除工作的位置开始)。

在当前级别增加或减少权重后，您可能需要重新平衡，记住您递归更改了哪一侧。插入更简单:如果 child[s]->weight*4 >= This->weight*3你需要重新平衡。重新平衡是两种基本的树旋转之一，您可以根据是否 child[s]->cweight(s)<child[s]->cweight(1-s) 选择哪一个。 . rebalance for remove 是相同的想法，但细节不同。

这个系统比红黑树或 AVL 树做了更多的最坏情况再平衡。但仍然完全是logN。也许有更好的权重半平衡树算法。但是我通过一些谷歌搜索找不到它，甚至找不到我随意称之为“重量半平衡树”的真实姓名或其他细节。

奇怪地将读取操作混合到插入和删除操作中获得近 2 倍的速度，这意味着您将需要另一个插入的递归版本，它不混合在读取中，并且用于路径的一部分低于您阅读的点(因此它会执行相同的递归权重更改和重新平衡，但输入和输出不同)。

给定随机访问输入迭代器，构造是一个更简单的递归函数。从迭代器的范围中取出中间项，并用整个范围的总权重将其作为一个节点，然后将中间项前后的子范围递归传递给相同的递归函数以创建子树。

我还没有测试过这些，但我认为以下是 remove 所需的全部代码以及插入和删除所需的重新平衡。采取的功能 node*&是 static tree 的成员函数和那些不参加 node*& 的人是非静态的。

unsigned tree::remove(unsigned K)
{
    node* removed = remove(root, K);
    unsigned result = removed->value;
    delete removed;
    return result;
}

// static
node* tree::remove( node*& There, unsigned K) // Find, unlink and return the K'th node
{
   node* result;
   node* This = There;
   unsigned s=0;  // Guess at child NOT removed from
   This->weight -= 1;
   if ( K < This->cweight(0) )
   {
      s = 1;
      result = remove( This->child[0], K );
   }
   else
   {
      K -= This->cweight(0);
      if ( K > 0 )
      {
         result = remove( This->child[1], K-1 );
      }
      else if ( ! This->child[1] )
      {
     // remove This replacing it with child[0]
         There = This->child[0];
         return This;  // Nothing here/below needs a re-balance check
      }
      else
      {
     // remove This replacing it with the leftmost descendent of child[1]
         result = This;
         There = This = remove( This->child[1], 0 );
         This->child[0] = Result->child[0];
         This->child[1] = Result->child[1];
         This->weight = Result->weight;
      }
   }
   rebalance( There, s );
   return result;
}

// static
void tree::rebalance( node*& There, unsigned s)
{
   node* This = There;
   node* c = This->child[s];
   if ( c && c->weight*4 >= This->weight*3 )
   {
       node* b = c->child[s];
       node* d = c->child[1-s];
       unsigned bweight = b ? b->weight : 0;
       if ( d && bweight < d->weight )
       {
        // inner rotate:  d becomes top of subtree
        This->child[s] = d->child[1-s];
        c->child[1-s] = d->child[s];
        There = d;
        d->child[s] = c;
        d->child[1-s] = This;
        d->weight = This->weight;
        c->weight = bweight + c->cweight(1-s) + 1;
        This->weight -= c->weight + 1;
       }
       else
       {
        // outer rotate:  c becomes top of subtree
        There = c;
        c->child[1-s] = This;
        c->weight = This->weight;
        This->child[s] = d;
        This->weight -= bweight+1;
       }
   }
}