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 <cstdint>
#include <iostream>

Include dependency graph for treap.cpp:

Go to the source code of this file.

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

Namespaces
namespace	data_structures
	for IO operations
namespace	data_structures::treap
	Functions for the Treap algorithm implementation.

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

Definition in file treap.cpp.

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 255 of file treap.cpp.

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

test()

static void test ( )

static

Self-test implementations.

Returns

void

< Treap object instance

Definition at line 229 of file treap.cpp.

                   {
    data_structures::treap::Treap mTreap;  
 
    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";
}