Treap learning notes 2020.8.12

If the insertion order of nodes in a binary sort tree is random, the binary sort tree established in this way is balanced in most cases. It can be proved that its high expectation value is \ (O (\ log_2 n) \). Even if there are some extreme cases, the probability of this happening is very small. Moreover, the operation of the binary sort tree established in this way is very convenient. It is not necessary to maintain the balance of numbers through extension operation like the extension tree, nor to carry out various complex rotation operations in order to achieve balance like AVL tree, red black tree and other structures. When the complexity is low, the accuracy is high, which is very important for the limited competition time and tight competition examination room.

Treap is a binary sort tree that satisfies the nature of heap. While keeping the basic properties of the binary sort tree unchanged, set a random weight for each node. The weight meets the properties of the heap. Its structure and effect are equivalent to the binary sort tree established by inserting nodes in random order. It is simple to implement, supports most operations of stretching tree, and its efficiency is higher than that of stretching tree.

The word "Tree" comes from "Tree" and "Heap". The Tree itself is a binary sort Tree, and its left subtree and right subtree are also a Tree respectively.

Different from the general binary sort tree, the tree records an additional data field - priority. While forming a binary sort tree with keywords, the priority of the tree also meets the nature of the heap (this essay assumes a small root heap). However, there is one difference between a heap and a heap: a heap must be a complete binary tree, while a heap does not necessarily require a binary tree.

As shown in the figure, it is a tree structure. The result of traversal in the order of keywords is: ABEGHIK, and the priority meets the small root heap.

1. Basic operation of tree

The specific way to make the tree satisfy two properties at the same time is to first satisfy the properties of the binary sort tree, and then satisfy the properties of the heap without destroying the properties of the binary sort tree through the rotation operation (left or right rotation). The tree rotation operation mainly operates a parent node and one of its child nodes to make the child node go up and the parent node go down.

The following figure is a schematic diagram of left-hand and right-hand operation of Treap:


Left hand operation of Treap


Right hand operation of Treap

(one question: why is Splay's left rotation called Zag and right rotation called Zig, while Treap's left rotation called zig and right rotation called Zag?)

In Zig and Zag operations, it can be seen that the size relationship between \ (a,b,c,x,y \) has not changed.

Because it is a binary search tree, it meets the left subtree of the keyword \ (\ gt \) of the root node\ (\ lt \) right subtree, so

For the Zig operation in the figure above, before turning

\[A \lt y \lt B \lt x \lt C \]

(where \ (a, B, C \) respectively represents all elements in the subtree with \ (a, B, C \) as the root node)

This property is still satisfied after flipping.

For the Zag operation of China in the figure above, before turning

\[A \lt x \lt B \lt y \lt C \]

This property is still satisfied after flipping.

Through left rotation and right rotation, a node can move up and down freely in the tree, and the up and down movement of the node can easily correspond to the up and down adjustment of the heap node. Here are some basic operations of Treap.

1. Find, maximize and minimize

These three operations are the same as the binary sort tree. However, due to the randomization structure of Treap, it can be proved that the time complexity of finding, maximizing and minimizing in Treap is \ (O(h) \), where \ (h \) represents the height of the tree.

2. Insert

First assign a priority to the node randomly, and then insert the node to be inserted into a leaf like the node insertion of the binary sort tree, and then maintain the nature of the heap, that is, rotate if the priority of the current node is lower than the root (rotate right if the current node is the left second child of the root, and rotate left if the current node is the right son of the root).

Assuming that the number to be inserted is \ (1,2,3,4,5,6 \), and the priority obtained by random function is \ (10,22,5,80,37,45 \), the process of inserting nodes in turn is as follows:

Inserting \ (1 \) and \ (2 \) does not affect the nature of the heap, so rotation maintenance is not required.
\((3:5) \) after insertion, because \ (5 \) is smaller than \ (22 \) and \ (10 \), it needs to rotate twice to adjust \ ((3:5) \) to the top to ensure that the priority conforms to the nature of the heap.

No rotation is required to insert \ (4 \).

After inserting \ (5 \), perform a left-hand rotation.

No rotation is required after inserting \ (6 \).

Then the insertion of the whole tree is completed.

Through observation, it is not difficult to find that if each element is inserted into the binary sort tree in the order of priority (in the above example, that is, in the order of \ (3,1,2,5,4,6 \), the tree formed is completely consistent with the result after the above insertion adjustment. This is the function of Treap, which makes the data insertion realize the randomness of the data itself, and its effect is exactly the same as the insertion after disturbing the data, which makes it applicable to almost all places where the balanced tree needs to be used.

If the insertion process is written in recursive form, it is very easy to realize as long as you judge whether the nature of the heap is satisfied after the recursive call is completed. If not, continue to rotate. Since the time complexity of the rotation operation is \ (O(1) \) and only \ (h \) rotations are performed at most (\ (h \) is the height of the tree), the total time complexity is \ (O(h) \).

3. Delete

With the rotation operation, the deletion of the tree is simpler than the binary sort tree. Because the heap nature of the heap is satisfied, we only need to rotate the node to be deleted into a leaf node, and then delete it directly. The specific method is to find the child with low priority each time, rotate it in the opposite direction until the node is rotated into a leaf node, and then delete it directly.

For example, to delete the node \ ((B:7) \) in the following figure (left figure), the rotation result is shown in the following figure (right figure), and then delete the node \ ((B:7) \). The deletion can rotate up to \ (h \) times, so the time complexity of deletion is \ (O(h) \).

4. Separation

To divide a Treap into two treaps by size, you only need to forcibly add a virtual node at the separate position (set the priority), then rotate it to the root node according to the priority, and then delete it. The left and right subtrees are two treaps. According to the nature of binary sort tree, all nodes of the left subtree are smaller than those of the right subtree. The time complexity of separation is equivalent to the time complexity of an insertion operation, which is also \ (O(h) \).

5. Consolidation

Merging refers to merging two balance trees into one balance tree. All nodes of the first tree must be less than or equal to all nodes of the second tree, which is also the condition satisfied by the result of the above separation operation. The process of merging the tree is opposite to the separation process. As long as sister Zeng has a virtual root, take the two trees as the left and right subtrees respectively, and then delete the root. The time complexity of merging is the same as that of deleting, which is also \ (O(h) \).

Algorithm implementation of tree

First, define some required data, that is, declare the function of the structure:

int val[maxn],          // keyword
    priority[maxn],     // priority
    lson[maxn],         // Left second child number
    rson[maxn],         // Right son number
    p[maxn],            // Parent node number
    sz;                 // Number of elements
struct Treap {
    int rt;     // Root node number
    void zig(int x);    // Sinistral
    void zag(int x);    // Dextral
    void func_rotate(int x); // Rotation (left + right)
    void add(int v);    // Insert a value v
    int func_find(int v);   // Find element with value v
    void del(int v);    // Delete an element with a value of v
    int getMin();   // Get minimum value
    int getMax();   // Get maximum
    int getPre(int v);  // Obtain the leading trend (the maximum element with value < = V)
    int getSuc(int v);  // Get successor (minimum element with value > = V)
} tree;

Then define the functions of left and right rotation:

// Sinistral
void Treap::zig(int x) {
    int y = p[x], z = p[y];
    assert(y && rson[y] == x);
    if (rt == y) rt = x;    // Update rt
    int b = lson[x];
    rson[y] = b;
    p[b] = y;
    lson[x] = y;
    p[y] = x;
    p[x] = z;
    if (z) {
        if (lson[z] == y) lson[z] = x;
        else rson[z] = x;
    }
}

// Dextral
void Treap::zag(int x) {
    int y = p[x], z = p[y];
    assert(y && lson[y] == x);
    if (rt == y) rt = x;    // Update rt
    int b = rson[x];
    lson[y] = b;
    p[b] = y;
    rson[x] = y;
    p[y] = x;
    p[x] = z;
    if (z) {
        if (lson[z] == y) lson[z] = x;
        else rson[z] = x;
    }
}

The realization of left-hand rotation and right-hand rotation needs to pay attention to the following problems:

  1. It can target the child node \ (x \) or the parent node \ (y \) (in my implementation, it is targeted at the child node \ (x \);
  2. The premise of rotation is that \ (x \) must have a parent node, that is, the root node cannot be raised upward through rotation;
  3. Note that some subtrees may not exist, and the nonexistent nodes can be defined as \ (0 \);
  4. If the node has a parent node and the child node points to the new parent node, the child node information of the original parent node must also be changed, and the adjustment of the parent-child relationship is two-way - I am not your son, then you are not my father at the same time.

Since the purpose of left rotation and right rotation is to adjust the child node \ (x \) up one layer, we can encapsulate a func_ The rotate function is used to unify left and right rotation operations:

// Rotation (left + right)
void Treap::func_rotate(int x) {
    assert(p[x]);
    if (x == rson[p[x]]) zig(x);
    else zag(x);
}

Insert:

// Insert a value v
void Treap::add(int v) {
    val[++sz] = v;
    priority[sz] = rand();
    if (!rt) rt = sz;
    else {
        int x = rt;
        while (true) {
            if (val[x] >= v) {
                if (lson[x]) x = lson[x];
                else {
                    lson[x] = sz;
                    p[sz] = x;
                    break;
                }
            }
            else {
                if (rson[x]) x = rson[x];
                else {
                    rson[x] = sz;
                    p[sz] = x;
                    break;
                }
            }
        }
        x = sz;
        while (p[x] && priority[x] < priority[p[x]]) func_rotate(x);
    }
}

Query:

// Find element with value v
int Treap::func_find(int v) {
    if (!rt) return 0;
    int x = rt;
    while (true) {
        if (val[x] == v) return x;
        else if (val[x] > v) {
            if (lson[x]) x = lson[x];
            else return 0;
        }
        else {  // val[x] < v
            if (rson[x]) x = rson[x];
            else return 0;
        }
    }
}

Delete:

// Delete an element with a value of v
void Treap::del(int v) {
    int x = func_find(v);
    if (!x) return;
    while (lson[x] || rson[x]) {
        if (!rson[x]) func_rotate(lson[x]);
        else if (!lson[x]) func_rotate(rson[x]);
        else if (priority[lson[x]] < priority[rson[x]]) func_rotate(lson[x]);
        else func_rotate(rson[x]);
    }
    // When the loop exits, x becomes a leaf node. Delete it
    if (x == rt) {  // Leaf node = = root node -- > only 1 node
        rt = 0;
        return;
    }
    int y = p[x];
    if (y) {
        if (lson[y] == x) lson[y] = 0;
        else rson[y] = 0;
    }
    p[x] = 0;   // It doesn't matter if you don't write this sentence
}

Minimum value:

// Get minimum value
int Treap::getMin() {
    int x = rt;
    while (lson[x]) x = lson[x];
    return x;
}

Maximum value:

// Get maximum
int Treap::getMax() {
    int x = rt;
    while (rson[x]) x = rson[x];
    return x;
}

Forward trend:

// Obtain the leading trend (the maximum element with value < = V)
int Treap::getPre(int v) {
    if (!rt) return 0;
    int ans = 0, x = rt;
    while (x) {
        if (val[x] <= v) {
            if (ans == 0 || val[ans] < val[x]) ans = x;
            x = rson[x];
        }
        else x = lson[x];
    }
    return ans;
}

Follow up:

// Get successor (minimum element with value > = V)
int Treap::getSuc(int v) {
    if (!rt) return 0;
    int ans = 0, x = rt;
    while (x) {
        if (val[x] >= v) {
            if (ans == 0 || val[ans] > val[x]) ans = x;
            x = lson[x];
        }
        else x = rson[x];
    }
    return ans;
}

The complete code is as follows (corresponding to monster warehouse keeper (II):

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000010;
int val[maxn],          // keyword
    priority[maxn],     // priority
    lson[maxn],         // Left second child number
    rson[maxn],         // Right son number
    p[maxn],            // Parent node number
    sz;                 // Number of elements
struct Treap {
    int rt;     // Root node number
    void zig(int x);    // Sinistral
    void zag(int x);    // Dextral
    void func_rotate(int x); // Rotation (left + right)
    void add(int v);    // Insert a value v
    int func_find(int v);   // Find element with value v
    void del(int v);    // Delete an element with a value of v
    int getMin();   // Get minimum value
    int getMax();   // Get maximum
    int getPre(int v);  // Obtain the leading trend (the maximum element with value < = V)
    int getSuc(int v);  // Get successor (minimum element with value > = V)
} tree;

// Sinistral
void Treap::zig(int x) {
    int y = p[x], z = p[y];
    assert(y && rson[y] == x);
    if (rt == y) rt = x;    // Update rt
    int b = lson[x];
    rson[y] = b;
    p[b] = y;
    lson[x] = y;
    p[y] = x;
    p[x] = z;
    if (z) {
        if (lson[z] == y) lson[z] = x;
        else rson[z] = x;
    }
}

// Dextral
void Treap::zag(int x) {
    int y = p[x], z = p[y];
    assert(y && lson[y] == x);
    if (rt == y) rt = x;    // Update rt
    int b = rson[x];
    lson[y] = b;
    p[b] = y;
    rson[x] = y;
    p[y] = x;
    p[x] = z;
    if (z) {
        if (lson[z] == y) lson[z] = x;
        else rson[z] = x;
    }
}

// Rotation (left + right)
void Treap::func_rotate(int x) {
    assert(p[x]);
    if (x == rson[p[x]]) zig(x);
    else zag(x);
}

// Insert a value v
void Treap::add(int v) {
    val[++sz] = v;
    priority[sz] = rand();
    if (!rt) rt = sz;
    else {
        int x = rt;
        while (true) {
            if (val[x] >= v) {
                if (lson[x]) x = lson[x];
                else {
                    lson[x] = sz;
                    p[sz] = x;
                    break;
                }
            }
            else {
                if (rson[x]) x = rson[x];
                else {
                    rson[x] = sz;
                    p[sz] = x;
                    break;
                }
            }
        }
        x = sz;
        while (p[x] && priority[x] < priority[p[x]]) func_rotate(x);
    }
}

// Find element with value v
int Treap::func_find(int v) {
    if (!rt) return 0;
    int x = rt;
    while (true) {
        if (val[x] == v) return x;
        else if (val[x] > v) {
            if (lson[x]) x = lson[x];
            else return 0;
        }
        else {  // val[x] < v
            if (rson[x]) x = rson[x];
            else return 0;
        }
    }
}

// Delete an element with a value of v
void Treap::del(int v) {
    int x = func_find(v);
    if (!x) return;
    while (lson[x] || rson[x]) {
        if (!rson[x]) func_rotate(lson[x]);
        else if (!lson[x]) func_rotate(rson[x]);
        else if (priority[lson[x]] < priority[rson[x]]) func_rotate(lson[x]);
        else func_rotate(rson[x]);
    }
    // When the loop exits, x becomes a leaf node. Delete it
    if (x == rt) {  // Leaf node = = root node -- > only 1 node
        rt = 0;
        return;
    }
    int y = p[x];
    if (y) {
        if (lson[y] == x) lson[y] = 0;
        else rson[y] = 0;
    }
    p[x] = 0;   // It doesn't matter if you don't write this sentence
}

// Get minimum value
int Treap::getMin() {
    int x = rt;
    while (lson[x]) x = lson[x];
    return x;
}

// Get maximum
int Treap::getMax() {
    int x = rt;
    while (rson[x]) x = rson[x];
    return x;
}

// Obtain the leading trend (the maximum element with value < = V)
int Treap::getPre(int v) {
    if (!rt) return 0;
    int ans = 0, x = rt;
    while (x) {
        if (val[x] <= v) {
            if (ans == 0 || val[ans] < val[x]) ans = x;
            x = rson[x];
        }
        else x = lson[x];
    }
    return ans;
}

// Get successor (minimum element with value > = V)
int Treap::getSuc(int v) {
    if (!rt) return 0;
    int ans = 0, x = rt;
    while (x) {
        if (val[x] >= v) {
            if (ans == 0 || val[ans] > val[x]) ans = x;
            x = lson[x];
        }
        else x = rson[x];
    }
    return ans;
}

int n, op, x;

int main() {
    scanf("%d", &n);
    while (n --) {
        scanf("%d", &op);
        if (op != 3 && op != 4) scanf("%d", &x);
        if (op == 1) tree.add(x);
        else if (op == 2) tree.del(x);
        else if (op == 3) printf("%d\n", val[tree.getMin()]);
        else if (op == 4) printf("%d\n", val[tree.getMax()]);
        else if (op == 5) printf("%d\n", val[tree.getPre(x)]);
        else printf("%d\n", val[tree.getSuc(x)]);
    }
    return 0;
}

Tags: data structure

Posted by robindean on Mon, 23 May 2022 05:59:12 +0300