我遇到以下问题。 有必要实现一个提供以下功能的数据存储容器：
- 插入新项目
- 按序列号删除项目
- 通过序列号获取商品
- 数据以排序形式存储
数据不断地被添加和删除，该结构应提供快速的速度。 最初，我尝试使用std中的标准容器来实现这样的事情。 这条路径是不成功的，并且了解到您需要自己实现一些东西。 唯一想到的就是使用二进制搜索树。 由于它满足快速插入，删除和以排序形式存储数据的要求。 剩下的只是弄清楚如何在树更改时索引所有元素并重新计算索引。
struct node_s { data_t data; uint64_t weight;
本文将提供比图片更多的图片和理论。 可以在下面的链接中查看代码。
机重
为此，对树进行了少许修改，添加了有关节点权重的其他信息。 节点的权重是该节点的后代数量 + 1 （单个元素的权重）。
获取节点权重的函数
uint64_t bntree::get_child_weight(node_t *node) { if (node) { return node->weight; } return 0; }
纸张的权重分别为0 。
接下来，我们转向这种树的示例的视觉表示。 节点密钥将在其中显示为黑色 （由于不需要此值，因此将不会显示该值）， 红色是节点权重， 绿色是节点索引。
当树为空时，其权重为0。向其中添加根元素：
树的权重变为1，根元素的权重为1。根元素的权重为树的权重。
添加更多元素：
每次添加新项目时，我们将节点向下移动到底部，并增加传递的每个节点的权重计数器。 创建新节点时，将其设置为权重1 。 如果已经存在带有此类密钥的节点，则重写该值并返回到根目录，以取消我们传递的所有节点的权重更改。
如果要删除该节点，那么我们将降低传递的节点的权重。
指标
现在让我们继续如何索引节点。 节点未明确存储其索引；该索引是根据节点的权重计算的。 如果他们存储了索引，则在每次更改树后需要O（n）时间来更新所有节点的索引。
让我们继续进行视觉表示。 我们的树是空的，在其中添加第一个节点：
第一个节点的索引为0 ，现在有2种情况。 在第一个中，根元素的索引将更改；在第二个中，它不会更改。
在根目录下，左子树的权重为1。
第二种情况：
根索引未更改，因为其左子树的权重保持为0。
考虑节点索引时，这是其左子树的权重+从父级传递的数字。 这个数字是什么？，这是一个索引计数器，最初是0 ，因为 根没有父母。 然后，这一切都取决于我们走到左孩子还是右孩子的位置。 如果在左侧，则不添加任何内容。 如果在右侧，则添加当前节点的索引。
例如，如何使用键8（根的右子元素）计算元素的索引。 这是“根索引” +“具有键8的节点的左子树的权重” +“ 1” == 3 + 2 + 1 == 6
键6的项目的索引为“根索引” +1 == 3 +1 == 4
因此，通过索引获取和删除元素将花费O（log n）时间，因为要获取该元素，我们需要首先找到它（从根到该元素）。
深度
根据重量，您还可以计算树的深度。 平衡所必需。
为此，必须将当前节点的权重舍入为2级的第一个数字，该数字应大于或等于给定的权重，并从中取二进制对数。 因此，只要树是平衡的，我们就可以得到树的深度。 插入新元素后，树是平衡的。 关于如何平衡树木的理论将不起作用。 源代码提供平衡功能。
编码以使重量更深。
uint64_t bntree::cpl2(uint64_t x) { x = x - 1; x = x | (x >> 1); x = x | (x >> 2); x = x | (x >> 4); x = x | (x >> 8); x = x | (x >> 16); x = x | (x >> 32); return x + 1; } long bntree::ilog2(long d) { int result; std::frexp(d, &result); return result - 1; } uint64_t bntree::weight_to_depth(node_t *p) { if (p == NULL) { return 0; } if (p->weight == 1) { return 1; } else if (p->weight == 2) { return 2; } return this->ilog2(this->cpl2(p->weight)); }
总结
- 新元素的插入发生在O中（log n）
- 按序号删除元素在O中发生（log n）
- 通过序列号获取元素出现在O中（日志n）
以O（log n）的速度， 我们支付了所有数据都以排序形式存储的事实。
我不知道这种结构可以派上用场的地方。 只需再次了解树的工作原理即可。 谢谢您的关注。
参考文献
该项目包含测试数据以验证工作速度。 树上充满了1,000,000个元素。 并依次删除，插入和接收1,000,000次元素。 那是3,000,000次操作。 结果是相当好的〜8秒。