treapcpp/treap.hpp at main · vasatodorovic/treapcpp · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#ifndef TREAP_HPP
#define TREAP_HPP

#include <iostream>
#include <random>
#include <limits>
#include <climits>
#include <utility>

using namespace std;

struct TreapNode {

    int key;
    int priority;
    TreapNode* left;
    TreapNode* right;


    TreapNode(){}
    TreapNode(int k,int p):key(k),priority(p),left(nullptr),right(nullptr){}
};

TreapNode* insert(TreapNode* treap, int k, int p);
TreapNode* remove(TreapNode* treap, int k);
TreapNode* search(TreapNode* treap, int k);

pair<TreapNode*,TreapNode*> split(TreapNode* treap, int a);
TreapNode* merge(TreapNode*,TreapNode*);

int depth(TreapNode* treap);

void rotateRight(TreapNode* &treap);
void rotateLeft(TreapNode* &treap);

void printTreap(TreapNode* root,int depth=0);
void freeTreap(TreapNode* root);

#endif