主持人 > 博客 > 管理 > 索引二叉树

索引二叉树

索引二叉树

我遇到了以下类型的问题。 有必要实现一个提供以下功能的数据存储容器：

  • 插入新元素
  • 按序列号删除元素
  • 按序号获取元素
  • 数据以排序形式存储

数据不断地被添加和删除，结构必须保证快速的运算速度。 起初我尝试使用标准容器来实现这样的事情 STD。 这条道路并没有取得成功，我意识到我需要自己实现一些东西。 唯一想到的是使用二叉搜索树。 因为它满足了数据以排序形式快速插入、删除和存储的要求。 剩下的就是弄清楚如何对所有元素建立索引并在树发生变化时重新计算索引。

struct node_s {    
    data_t data;

    uint64_t weight; // вес узла

    node_t *left;
    node_t *right;

    node_t *parent;
};

这篇文章将包含更多的图片和理论而不是代码。 代码可以在下面的链接中查看。

一件（箱）重量

为了实现这一点，该树进行了轻微的修改，添加了有关 重量 节点。 节点权重为 该节点的后代数量 + 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，现在有两种情况是可能的。 在第一个中，根元素的索引将改变，在第二个中它不会改变。

索引二叉树

在根处，左子树的权重为 1。

第二种情况：

索引二叉树

根的索引没有改变，因为它的左子树的权重仍然是0。

节点的索引计算为其左子树的权重+从父节点传递的数字。 这个数字是多少？，这是索引计数器，最初它等于 0， 因为根没有父级。 然后这一切都取决于我们到哪里去寻找左边的孩子或右边的孩子。 如果在左侧，则不会向计数器添加任何内容。 如果我们将当前节点的索引添加到右侧节点。

索引二叉树

例如，如何计算键为 8（根的右子元素）的元素的索引。 这是“根索引”+“键为8的节点的左子树的权重”+“1”== 3 + 2 + 1 == 6
键为 6 的元素的索引将为“Root Index”+ 1 == 3 + 1 == 4

因此，通过索引获取和删除元素需要时间 O（log n），因为为了获得所需的元素，我们必须首先找到它（从根向下到该元素）。

Глубина

根据权重，您还可以计算树的深度。 平衡所必需的。
为此，当前节点的权重必须四舍五入到第一个大于或等于给定权重的 2 次方数字，并从中取二进制对数。 假设树是平衡的，这将为我们提供树的深度。 插入新元素后，树就达到了平衡。 我不会给出有关如何平衡树木的理论。 源代码提供了平衡功能。

将重量转换为深度的代码。

/*
 * Возвращает первое число в степени 2, которое больше или ровно x
 */
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（log n）

速度 O（log n） 我们为所有数据都以排序形式存储这一事实付出了代价。

我不知道这样的结构有什么用处。 只是一个再次了解树木如何运作的谜题。 感谢您的关注。

引用

该项目包含用于检查运行速度的测试数据。 树已经填满了 1000000 元素。 并且有顺序删除、插入和检索元素 1000000 一次。 那是 3000000 运营。 结果结果相当不错~8秒。

来源： habr.com

添加评论