Extended treap (a special type of randomized binary search tree) which manages selection and splitting for inorder position. More...
#include <tpl_treapRk.H>
Public Types | |
| using | Base = Gen_Treap_Rk< Treap_Rk_NodeVtl, Key, Compare > |
 Public Types inherited from Aleph::Gen_Treap_Rk< NodeType, Key, Compare > | |
| using | Node = NodeType< Key > |
Additional Inherited Members | |
| Public Member Functions inherited from Aleph::Gen_Treap_Rk< NodeType, Key, Compare > | |
| void | set_seed (const unsigned long seed) noexcept |
| Set the random number generator seed. | |
| Compare & | key_comp () noexcept |
| return the comparison criteria | |
| Compare & | get_compare () noexcept |
| Gen_Treap_Rk (const unsigned long seed, Compare __cmp=Compare()) | |
Initialize a treap with random seed and comparison criteria __cmp | |
| Gen_Treap_Rk (Compare __cmp=Compare()) | |
| ~Gen_Treap_Rk () | |
| void | swap (Gen_Treap_Rk &tree) noexcept |
Swap in constant time all the nodes of this with tree | |
| Node *& | getRoot () noexcept |
| Return the tree's root. | |
| Node * | getRoot () const noexcept |
| Node * | search (const Key &key) const noexcept |
| Search a key in a treap. | |
| Node * | insert (Node *p) noexcept |
| Insert a node in a treap. | |
| Node * | insert_dup (Node *p) noexcept |
| Insert a node in the tree. | |
| Node * | search_or_insert (Node *p) noexcept |
| Search or insert a key. | |
| bool | verify () const |
Return true if the treap is consistent. | |
| Node * | remove (const Key &key) noexcept |
| Remove a key from the tree. | |
| Node * | remove (const size_t beg, const size_t end) |
Remove from the treap all the keys between inorder position beg and end. | |
| Node * | remove_pos (const size_t pos) |
| Remove the node at the inorder position pos. | |
| Node * | select (const size_t i) const |
| Return the i-th node in order sense. | |
| size_t | size () const noexcept |
| Return the number of nodes contained in the tree. | |
| bool | is_empty () const noexcept |
Return true if tree is empty. | |
| std::pair< int, Node * > | position (const Key &key) const noexcept |
| Compute the inorder position of a key. | |
| std::pair< int, Node * > | find_position (const Key &key) const noexcept |
| Find the inorder position of a key in the tree. | |
| bool | split_key (const Key &key, Gen_Treap_Rk &t1, Gen_Treap_Rk &t2) noexcept |
| Split the tree according to a key. | |
| void | split_key_dup (const Key &key, Gen_Treap_Rk &t1, Gen_Treap_Rk &t2) noexcept |
| Split the tree according to a key that could be in the tree. | |
| void | split_pos (size_t pos, Gen_Treap_Rk &t1, Gen_Treap_Rk &t2) |
| Split the tree at the inorder position pos. | |
| void | join (Gen_Treap_Rk &t, Gen_Treap_Rk &dup) noexcept |
Join this with t filtering the duplicated keys. | |
| void | join_dup (Gen_Treap_Rk &t) noexcept |
Join this with t independently of the presence of duplicated keys. | |
| void | join_exclusive (Gen_Treap_Rk &t) noexcept |
Join exclusive of this with t | |
Detailed Description
Extended treap (a special type of randomized binary search tree) which manages selection and splitting for inorder position.
The treap is a binary search tree whose very high performance is achieved by randomization. The basic idea is to store a priority value in each node which is randomly chosen. By the side of keys, the tree a binary search, but by the side of priorities, the tree is a heap. It is shown that this class of tree has an expected performance of \(O(\lg n)\) for the majority of its operations. In addition, this extended tree uses and second integer for storing subtrees sizes.
The treap is faster than the randomized tree by a constant time (both approaches are logarithmic). Since the priority is chosen just one time and the adjustments are done in a botton-top way (by contrast with the randomized which is top-bottom), the treap takes less time.
Although this approach trends to be faster than the randomized trees, takes in account that this treap is more space consuming because each node requires 2 additional integers to the data (priority and counter) in contrast with the randomized which only requires one integer (the counter).
For splitting and join of independent and large data sets the randomized option trends to be faster. The split is equivalent, but the join is definitively faster. The join of two trees of n and m keys respectively takes \(O(n \lg m)\) with treaps, while it takes \(O(\max(\lg n, \lg m))\) with randomized trees. In addition,
The class internally uses the gsl random number generator of GSL - GNU Scientific Library. By default, the Mersenne twister is used and the seed is taken from system time.
- See also
- Treap Treap_Vtl Treap_Rk Treap_Rk_Vtl Rand_Tree
Definition at line 1122 of file tpl_treapRk.H.
Member Typedef Documentation
◆ Base
| using Aleph::Treap_Rk_Vtl< Key, Compare >::Base = Gen_Treap_Rk<Treap_Rk_NodeVtl, Key, Compare> |
Definition at line 1124 of file tpl_treapRk.H.
The documentation for this struct was generated from the following file:
