Feng Chengcheng is 13 years old. Thank you very much for your contribution.

When it comes to balancing binary search trees, the first thing that comes to mind must be red-black trees or AVL trees.

In fact, there are many kinds of binary trees that can be balanced, and Treap ** is one of them.

What is Treap?

Treap=Tree+Heap =Tree+Heap

So Treap must be a combination of tree and heap.

Congratulations, you’ve mastered the essence of Treap

So how does Treap combine the best of trees and heaps?

The characteristics of Treap

Treap is a binary search tree (BST), which is essentially the same as AVL, red-black and other balanced trees. But to be a balanced tree, it must have a function to maintain tree balance (to avoid becoming a chain). It also has a randomly generated priority for each node, which satisfies heap properties to keep the tree relatively balanced.

Like this one

Is a Treap tree (essentially the same as a BST)

The problem is that tweaking the Treap tree (inserting and removing elements) can make the priority of each node inconsistent with the heap nature, so we need to tweak the tree

Modeling of Treap

We consider building a tree in the form of Pointers, and the model of a node is as follows:

typedef struct Node { Node(int v) { val = v, cnt = size = 1, fac = rand(); lson = rson = NULL; } // Subtree size priority int val, CNT, size, fac; Node *lson, *rson; Node *lson, *rson; Inline void push_UP () {size = CNT; inline void push_up() {size = CNT; if (lson ! = NULL) size += lson->size; if (rson ! = NULL) size += rson->size; } }* Tree; inline int size(Tree t) { return t == NULL ? 0 : t->size; } inline Tree init() { Tree rt = new Node(Inf); rt->lson = new Node(-Inf); rt->fac = -Inf, rt->lson->fac = -Inf; rt->push_up(); return rt; }Copy the code

The operation of the Treap

In order to ensure that the Treap tree can still meet the nature of the heap after changing its priority, we need to rotate it to form a heap on the premise that it meets the binary search tree. The nice thing about Treap is that there are only two rotations.

Right hand

We assume that this tree already satisfies the binary search tree property, D<B<E<A<C, and we can rotate it like this

Step 1: Hang the A-C edges under B

Step 2: Hang point E below A

By doing this rotation, we still make sure that the subtree satisfies D<B<E<A<C, and we adjust the tree. We summarize dextral rotation as:

The hub (B) is lifted up, the father (A) and brother (C) are hung below, and the right child (E) is given to the father (A).

Note: D, C, and E can all represent a subtree and not just a node

The code is as follows:

inline void right_rotate(Tree &a) {
    Tree b = a->lson;
    a->lson = b->rson, b->rson = a, a = b;
    a->rson->push_up(), a->push_up();
}
Copy the code

left-handed

Left-handedness is almost the same as right-handedness, and if you reverse the whole process of right-handedness you get left-handedness. Also in two steps:

The first step:

The second step:

The code is as follows:

inline void right_rotate(Tree &a) {
    Tree b = a->lson;
    a->lson = b->rson, b->rson = a, a = b;
    a->rson->push_up(), a->push_up();
}
Copy the code

There are also blogs on the web that write lson and rson as an array son, and then write left and right as a function:

inline void rotate(Tree &a, int f) {
    Tree b = a->son[f^1];
    a->son[f^1] = b->son[f], b->son[f] = a, a = b;
    a->rson->push_up(), b->push_up();
}
Copy the code

Note that left-handed and right-handed codes need to pass a reference to the argument A, because eventually a will also be updated

Insert the node

Treap is also a kind of BST, so we should first follow the insertion rules of BST during insertion, and then determine whether rotation is needed according to the priority after insertion. Let’s take the tree (the small green text is the priority of the node) and insert an 8 into the tree.

The current goal is to insert a node of value 8 into a subtree rooted with value 2.

And we find that 8 is greater than 2,8 must be on the right subtree of the root.

Thus, the problem becomes inserting a node of value 8 into a subtree rooted with the node of value 6.

And what we find is that 8 is greater than 6,8 must be on the right subtree of the root.

The problem becomes inserting a node of value 8 into a subtree rooted in the node of value 9.

And what we find is that 8 is less than 9, 8 must be on the left subtree of the root, and 9 is already a leaf, and you can just plug it in.

Suppose this node has a priority of 5 (randomly chosen) :

Obviously, the two red priorities do not satisfy the characteristics of the big top heap (i.e., the son has more priority than the father), and the two nodes are slanted to the left, so we should rotate the node to the right. Since neither node has any additional sons, this is done in one step:

Obviously, this still satisfies the BST property after the rotation. However, we can double 叒 yi to find that the two red priority does not meet the characteristics of the heap, and the two nodes are slanted to the right, we can left-handed twist the subtree:

One insertion is done!

So let’s conclude by going down and finding the right place for the BST, and then going up and rotating to satisfy the characteristics of the heap.

Obviously, we can do this recursively. The part that goes down uses recursion, and the part that goes up uses return.

Let’s write some code. This might be a little hard to understand, but take a look at the comments:

inline void ins(Tree &rt, int val) { if (rt == NULL) {rt = new Node(val); return; } if (rt->val == val) rt->cnt++; Else if (rt->val >val) {if (rt->val) {ins(rt->lson, val); If (rt->fac < rt->lson->fac) right_rotate(rt); if (rt->fac < rt->lson->fac) right_rotate(rt); } else {ins(rt->rson, val); if (rt->fac < rt->rson->fac) left_rotate(rt); } rt->push_up(); }Copy the code

Remove nodes

Nodes are deleted in the same order as nodes are inserted. It’s all down and up.

For example, if we want to delete a node with a value of 6:

The current goal is to remove the node of value 6 from the subtree rooted with the node of value 2

Since 6 is greater than 2, the target node must be on the right subtree of the root, and the question becomes,

Removes the node of value 6 from the subtree rooted with the node of value 6

Very good! We’ve located the target node. The emperor is dead, the great emperor!

We can rotate the tree so that the higher priority son replaces the father (target node)

So in this case, we’re going to left-handed rotate the 6 subtree

But the node we want to delete is gone, and we need to keep chasing it!

We chased the left sub-tree, holding a gun to it, it is kind of dedicated, to let their other son take over before they die.

As a kind person, we have to answer its request, and then it turns!

At this time, 6 has no excuse to delay time, we directly wish it a happy Qingming Festival, delete it!

Obviously, this tree still satisfies the Treap tree characteristics.

Without further ado, go directly to the code:

inline void del(Tree &rt, int val) { if (rt == NULL) return; / / couldn't find the if (rt - > val = = val) {/ / find the node if (rt - > > 1) CNT {rt - > CNT - rt - > push_up (); return; } // It has children if (rt->lson! = NULL || rt->rson ! = NULL) {/ / key if (rt - > rson = = NULL | | rt - > lson! = NULL && rt->lson->fac > rt->rson->fac) right_rotate(rt), del(rt->rson, val); else left_rotate(rt), del(rt->lson, val); } else {delete rt; rt = NULL; return; } else if (rt->val >val) del(rt->lson, val); else del(rt->rson, val); rt->push_up(); }Copy the code

The query

There are several types of queries, and since Treap works like a normal BST, the code is directly pasted

Query ranking

Inline int qry_rank(Tree p, int val) {inline int qry_rank(Tree p, int val) {inline int qry_rank(Tree p, int val) { while (p ! = NULL) if (p->val == val) return size(p->lson) + rank; else if (p->val > val) p = p->lson; else rank += size(p->lson) + p->cnt, p = p->rson; return rank; }Copy the code

or

inline int qry_rank(Tree p, int val) {
    if (p->val == val) return size(p->lson);
    if (p->val > val) return qry_rank(p->lson, val);
    return qry_rank(p->rson, val) + size(p->lson) + p->cnt;
}
Copy the code

The query value

inline int qry_value(Tree p, int rank) { while (p ! = NULL && rank) if (size(p->lson) > rank) p = p->lson; else if (size(p->lson)+p->cnt >= rank) return p->val; else rank -= size(p->lson)+p->cnt, p = p->rson; }Copy the code

or

inline int qry_value(Tree p, int rank) {
    if (size(p->lson) >= rank) return qry_value(p->rson, rank);
    if (size(p->lson)+p->cnt >= rank) return p->val;
    return qry_value(p->lson, rank-size(p->lson)-p->cnt);
}
Copy the code

Query precursor

inline int qry_pre(Tree p, int val) { int pre = 0; while (p ! = NULL) if (p->val < val) pre = p->val, p = p->rson; else p = p->lson; return pre; }Copy the code

Qry_rank (p, val)-1)

Query the subsequent

inline int qry_suf(Tree p, int val) { int suf = 0; while (p ! = NULL) if (p->val > val) suf = p->val, p = p->lson; else p = p->rson; return suf; }Copy the code

Qry_rank (p, val)+1

conclusion

Treap is not a standard balanced tree. However, because it perfectly combines the characteristics of tree and heap, its constant is smaller than AVL, and it has good effect both in competition and in development applications, so it is often used to replace AVL tree.

At the same time, we can also learn a lesson: two different algorithms can complement each other in a clever way to achieve better results. If we can use this method in the actual development, we can certainly get no small effect.

Like this article friends, welcome to pay attention to the public number programmer xiao Grey, watch more exciting content