将链表转换为二叉搜索树，做东西和 return 树作为列表

Question

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

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

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

正确工作的例子：输入：3 1 2 3 Output: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

您可以使用 std::set 实现为二叉树。它的构造函数允许从迭代器构造，因此将列表转换为集合应该没有问题。

Answer 2

首先重新定义操作，将大部分（但不是全部）工作放入容器对象：我们希望容器对象支持4个操作：
1) 从 [first,limit) 对输入随机访问迭代器构造
2) insert(K) 在位置K找到值X，在其后插入一个X-1和returns X
3) remove(K) 在位置K找到值X，将其删除并returns 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 函数的包装器，除了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你需要重新平衡。重新平衡是两种基本的树旋转之一，你 select 哪一个基于是否 child[s]->cweight(s)<child[s]->cweight(1-s)。 rebalance for remove 是相同的想法，但细节不同。

这个系统比红黑树或 AVL 树做了更多的最坏情况重新平衡。但仍然完全是logN。也许有更好的权重半平衡树算法。但是我通过一些 google 搜索找不到它，甚至找不到关于我随意称为 "weight-semi-balanced tree".

的东西的真实姓名或其他详细信息。

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

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

我还没有测试过这些，但我认为以下是 remove 所需的所有代码以及插入和删除所需的重新平衡。采用 node*& 的函数是 tree 的 static 成员函数，不采用 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;
       }
   }
}

将链表转换为二叉搜索树，做东西和 return 树作为列表

Convert linked list into binary search tree, do stuff and return tree as list

c++

binary-tree

linked-list

data-structures