Indexed binary tree

I have a task of the following type. It is necessary to implement a data storage container that provides the following functionality:

• insert a new element
• delete an element by its index
• retrieve an element by its index
• data is stored in a sorted manner

Data is constantly added and removed, and the structure must ensure quick operation. Initially, I tried to implement this using standard containers from std. This approach did not succeed, leading to the realization that something needed to be implemented from scratch. The only idea that came to mind was to use a binary search tree, as it meets the requirements for fast insertion, deletion, and maintaining data in sorted order. The only thing left was to figure out how to index all elements and recalculate their indexes when the tree changes.

struct node_s {    
    data_t data;

    uint64_t weight; // weight of the node

    node_t *left;
    node_t *right;

    node_t *parent;
};

The article will contain more images and theory than code. The code can be viewed through the link at the bottom.

Weight

To achieve this, the tree underwent a slight modification, adding additional information about the weight of the node. The weight of the node is the number of descendants of this node + 1 (weight of a single element).

Function to get the weight of a node:

uint64_t bntree::get_child_weight(node_t *node) {
    if (node) {
        return node->weight;
    }

    return 0;
}

For a leaf, accordingly, the weight is 0.

Next, we will move on to a visual representation of such a tree. In black the key of the node will be shown (the value will not be displayed as it is unnecessary), in red — the weight of the node, in green — the index of the node.

When the tree is empty, its weight is 0. Let's add the root element to it:

The weight of the tree becomes 1, and the weight of the root element is 1. The weight of the root element is the weight of the tree.

Let's add a few more elements:

Each time a new element is added, we move down through the nodes and increment the weight counter of each node we pass. When creating a new node, its weight is set 1. If a node with this key already exists, we will overwrite the value and go back up to the root, canceling the weight changes of all nodes we've passed.
If a node is being deleted, we move down and decrement the weights of the nodes we pass.

Indexes

Now let's move on to how to index the nodes. Nodes do not explicitly store their index; it is computed based on the weights of the nodes. If they stored their index, it would require O(n) time to update the indices of all nodes after each change in the tree.
Let's move to a visual representation. Our tree is empty, let's add the first node:

The first node has an index 0, and now there are 2 possible cases. In the first case, the index of the root element will change, in the second it will not change.

The root has a left subtree that weighs 1.

Second case:

The index of the root has not changed since the weight of its left subtree remains 0.

The index of a node is calculated as the weight of its left subtree plus the number passed from the parent. What is this number? It is the index counter, initially it is 0, since the root has no parent. From there, everything depends on whether we go down to the left child or the right one. If we go to the left, nothing is added to the counter. If to the right, we add the index of the current node.

For example, how the index of the element with the key 8 (the right child of the root) is calculated. It is "Index of the root" + "weight of the left subtree of the node with key 8" + "1" == 3 + 2 + 1 == 6
The index of the element with the key 6 will be "Index of the root" + 1 == 3 + 1 == 4

Accordingly, to obtain or delete an element by index requires time O(log n), since to access the desired element we first need to find it (descend from the root to that element).

Depth

Based on weight, we can also calculate the depth of the tree. Necessary for balancing.
To do this, you need to round the weight of the current node to the first power of 2 that is greater than or equal to the given weight and take the binary logarithm of it. Thus, we will obtain the depth of the tree, provided it is balanced. The tree is balanced after inserting a new element. I won’t mention the theory on how to balance trees. The balancing function is presented in the source code.

Code for converting weight to depth.

/*
 * Возвращает первое число в степени 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));
}

Summary

• Inserting a new element takes O(log n)
• Deleting an element by its order number takes O(log n)
• Getting an element by its order number takes O(log n)

Speed O(log n) we pay for the fact that all data is stored in a sorted manner.

I don't know where such a structure might be useful. It's just a task to better understand how trees work. Thank you for your attention.

Links

• Source code of the tree

The project contains test data for speed checks. The tree is populated 1000000 with elements. And sequential deletion, insertion, and retrieval of elements occurs 1000000 times. That is, 3000000 operations. The result turned out to be quite good ~ 8 seconds.

Source: habr.com