treap.cpp File Reference

A balanced binary search tree (BST) on the basis of binary search tree and heap: the Treap algorithm implementation. More...

#include <array>
#include <cassert>
#include <iostream>

Include dependency graph for treap.cpp:

Classes
struct	data_structures::treap::Treap
	Struct representation of the treap. More...

Namespaces
namespace	data_structures
	for IO operations

Functions
static void	test ()
	Self-test implementations.
int	main ()
	Main function.

Variables
const int	data_structures::treap::maxNode = 1e5 + 5
	maximum number of nodes

Detailed Description

A balanced binary search tree (BST) on the basis of binary search tree and heap: the Treap algorithm implementation.

Implementation of the treap data structre

Support operations including insert, erase, and query (the rank of specified element or the element ranked x) as the same as BST

But these operations take O(log N) time, since treap keeps property of heap using rotate operation, and the desired depth of the tree is O(log N). There's very little chance that it will degenerate into a chain like BST

Author

Kairao ZHENG

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

           {
    test();  // run self-test implementations
    return 0;
}

Here is the call graph for this function:

test()

static void test ( )

static

Self-test implementations.

Returns

void

< Treap object instance

                   {
    data_structures::treap::Treap mTreap;  ///< Treap object instance
 
    mTreap.insert(1);
    mTreap.insert(2);
    mTreap.insert(3);
    assert(mTreap.get_k_th(2) == 2);
    mTreap.insert(4);
    mTreap.insert(5);
    mTreap.insert(6);
    assert(mTreap.get_next(4) == 5);
    mTreap.insert(7);
    assert(mTreap.get_predecessor(7) == 6);
    mTreap.erase(4);
    assert(mTreap.get_k_th(4) == 5);
    assert(mTreap.get_rank(5) == 4);
    mTreap.insert(10);
    assert(mTreap.get_rank(10) == 7);
    assert(mTreap.get_predecessor(10) == 7);
 
    std::cout << "All tests have successfully passed!\n";
}

Here is the call graph for this function: