data_structures::treap::Treap Struct Reference

Struct representation of the treap. More...

Collaboration diagram for data_structures::treap::Treap:

Public Member Functions
	Treap ()
	Initialization.
void	update (int x)
	Update the subtree size of the node.
void	rotate (int &x, int t)
	Rotate without breaking the property of BST.
void	_insert (int &x, int k)
	Insert a value into the specified subtree (internal method)
void	_erase (int &x, int k)
	Erase a value from the specified subtree (internal method)
int	_get_k_th (int &x, int k)
	Find the KTH largest value (internal method)
int	_get_rank (int x, int k)
	Query the rank of specified element (internal method)
int	get_predecessor (int k)
	Get the predecessor node of element k.
int	get_next (int k)
	Get the successor node of element k.
void	insert (int k)
	Insert element (External method)
void	erase (int k)
	Erase element (External method)
int	get_k_th (int k)
	Get the KTH largest value (External method)
int	get_rank (int k)
	Get the rank of specified element (External method)

Public Attributes
int	root = 0
	root of the treap
int	treapCnt = 0
	Total number of current nodes in the treap.
std::array< int, maxNode >	key = {}
	Node identifier.
std::array< int, maxNode >	priority = {}
	Random priority.
std::array< std::array< int, 2 >, maxNode >	childs
std::array< int, maxNode >	cnt
	Maintains the subtree size for ranking query.
std::array< int, maxNode >	size = {}
	The number of copies per node.

Detailed Description

Struct representation of the treap.

Definition at line 40 of file treap.cpp.

Constructor & Destructor Documentation

Treap()

data_structures::treap::Treap::Treap ( )

inline

Initialization.

Definition at line 55 of file treap.cpp.

            : treapCnt(1) {
        priority[0] = INT32_MAX;
        size[0] = 0;
    }

Member Function Documentation

_erase()

void data_structures::treap::Treap::_erase ( int & x, int k )

inline

Erase a value from the specified subtree (internal method)

Parameters

x	Erase from the subtree of node x (Usually x=root)
k	Key to erase

Definition at line 112 of file treap.cpp.

                               {
        if (key[x] == k) {
            if (cnt[x] > 1) {
                cnt[x]--;
            }  // If the node has more than one copy, the number of copies --
            else {
                if (childs[x][0] == 0 && childs[x][1] == 0) {
                    x = 0;
                    return;
                }  // If there are no children, delete and return
                // Otherwise, we need to rotate the sons and delete them
                // recursively
                int t = (priority[childs[x][0]] > priority[childs[x][1]]);
                rotate(x, t);
                _erase(x, k);
            }
        } else {  // Find the target value based on BST properties
            _erase(childs[x][key[x] < k], k);
        }
        update(x);
    }

_get_k_th()

int data_structures::treap::Treap::_get_k_th ( int & x, int k )

inline

Find the KTH largest value (internal method)

Parameters

x	Query the subtree of node x (Usually x=root)
k	The queried rank

Returns

The element ranked number k

Definition at line 139 of file treap.cpp.

                                 {
        if (k <= size[childs[x][0]]) {
            return _get_k_th(childs[x][0], k);
        }
        k -= size[childs[x][0]] + cnt[x];
        if (k <= 0) {
            return key[x];
        }
        return _get_k_th(childs[x][1], k);
    }

_get_rank()

int data_structures::treap::Treap::_get_rank ( int x, int k )

inline

Query the rank of specified element (internal method)

Parameters

x	Query the subtree of node x (Usually x=root)
k	The queried element

Returns

The rank of element k

Definition at line 155 of file treap.cpp.

                                {
        if (!x) {
            return 0;
        }
        if (k == key[x]) {
            return size[childs[x][0]] + 1;
        } else if (k < key[x]) {
            return _get_rank(childs[x][0], k);
        } else {
            return size[childs[x][0]] + cnt[x] + _get_rank(childs[x][1], k);
        }
    }

_insert()

void data_structures::treap::Treap::_insert ( int & x, int k )

inline

Insert a value into the specified subtree (internal method)

Parameters

x	Insert into the subtree of node x (Usually x=root)
k	Key to insert

Definition at line 85 of file treap.cpp.

                                {
        if (x) {
            if (key[x] == k) {
                cnt[x]++;
            }  // If the node already exists, the number of copies is ++
            else {
                int t = (key[x] < k);  // Insert according to BST properties
                _insert(childs[x][t], k);
                // After insertion, the heap properties are retained by rotation
                if (priority[childs[x][t]] < priority[x]) {
                    rotate(x, t);
                }
            }
        } else {  // Create a new node
            x = treapCnt++;
            key[x] = k;
            cnt[x] = 1;
            priority[x] = rand();  // Random priority
            childs[x][0] = childs[x][1] = 0;
        }
        update(x);
    }

erase()

void data_structures::treap::Treap::erase ( int k )

inline

Erase element (External method)

Parameters

k	Key to erase

Definition at line 208 of file treap.cpp.

{ _erase(root, k); }

get_k_th()

int data_structures::treap::Treap::get_k_th ( int k )

inline

Get the KTH largest value (External method)

Parameters

k	The queried rank

Returns

The element ranked number x

Definition at line 214 of file treap.cpp.

{ return _get_k_th(root, k); }

get_next()

int data_structures::treap::Treap::get_next ( int k )

inline

Get the successor node of element k.

Parameters

k	The queried element

Returns

The successor

Definition at line 188 of file treap.cpp.

                        {
        int x = root, next = -1;
        while (x) {
            if (key[x] > k) {
                next = key[x], x = childs[x][0];
            } else {
                x = childs[x][1];
            }
        }
        return next;
    }

get_predecessor()

int data_structures::treap::Treap::get_predecessor ( int k )

inline

Get the predecessor node of element k.

Parameters

k	The queried element

Returns

The predecessor

Definition at line 172 of file treap.cpp.

                               {
        int x = root, pre = -1;
        while (x) {
            if (key[x] < k) {
                pre = key[x], x = childs[x][1];
            } else {
                x = childs[x][0];
            }
        }
        return pre;
    }

get_rank()

int data_structures::treap::Treap::get_rank ( int k )

inline

Get the rank of specified element (External method)

Parameters

k	The queried element

Returns

The rank of element k

Definition at line 220 of file treap.cpp.

{ return _get_rank(root, k); }

insert()

void data_structures::treap::Treap::insert ( int k )

inline

Insert element (External method)

Parameters

k	Key to insert

Definition at line 203 of file treap.cpp.

{ _insert(root, k); }

rotate()

void data_structures::treap::Treap::rotate ( int & x, int t )

inline

Rotate without breaking the property of BST.

Parameters

x	The node to rotate
t	0 represent left hand, while 1 right hand

Definition at line 71 of file treap.cpp.

                               {
        int y = childs[x][t];
        childs[x][t] = childs[y][1 - t];
        childs[y][1 - t] = x;
        // The rotation will only change itself and its son nodes
        update(x);
        update(y);
        x = y;
    }

update()

void data_structures::treap::Treap::update ( int x )

inline

Update the subtree size of the node.

Parameters

x	The node to update

Definition at line 63 of file treap.cpp.

                       {
        size[x] = size[childs[x][0]] + cnt[x] + size[childs[x][1]];
    }

Member Data Documentation

childs

std::array<std::array<int, 2>, maxNode> data_structures::treap::Treap::childs

Initial value:

= {
        {}}

[i][0] represents the left child of node i, and [i][1] represents the right

Definition at line 45 of file treap.cpp.

                                                 {
        {}};  

cnt

std::array<int, maxNode> data_structures::treap::Treap::cnt

Initial value:

=
        {}

Maintains the subtree size for ranking query.

Definition at line 49 of file treap.cpp.

        {};  

key

std::array<int, maxNode> data_structures::treap::Treap::key = {}

Node identifier.

Definition at line 43 of file treap.cpp.

{};       

priority

std::array<int, maxNode> data_structures::treap::Treap::priority = {}

Random priority.

Definition at line 44 of file treap.cpp.

{};  

root

int data_structures::treap::Treap::root = 0

root of the treap

Definition at line 41 of file treap.cpp.

size

std::array<int, maxNode> data_structures::treap::Treap::size = {}

The number of copies per node.

Definition at line 51 of file treap.cpp.

{};  

treapCnt

int data_structures::treap::Treap::treapCnt = 0

Total number of current nodes in the treap.

Definition at line 42 of file treap.cpp.

---

The documentation for this struct was generated from the following file:

• data_structures/treap.cpp