Randomized binary search tree. More...
#include <tpl_rand_tree.H>
Public Types | |
| using | Base = Gen_Rand_Tree< RandNode, Key, Compare > |
 Public Types inherited from Aleph::Gen_Rand_Tree< NodeType, Key, Compare > | |
| using | Node = NodeType< Key > |
Additional Inherited Members | |
| Public Member Functions inherited from Aleph::Gen_Rand_Tree< NodeType, Key, Compare > | |
| Gen_Rand_Tree (const Gen_Rand_Tree &)=delete | |
| Gen_Rand_Tree & | operator= (const Gen_Rand_Tree &)=delete |
| Compare & | key_comp () noexcept |
| return the comparison criteria | |
| const Compare & | key_comp () const noexcept |
| Compare & | get_compare () noexcept |
| const Compare & | get_compare () const noexcept |
| gsl_rng * | gsl_rng_object () noexcept |
| Get a pointer to gsl random number generator. | |
| void | set_seed (const unsigned long seed) noexcept |
| Set the random number generator seed. | |
| Gen_Rand_Tree (const unsigned int seed, const Compare &__cmp=Compare()) | |
Initialize a random tree with random seed and comparison criteria __cmp | |
| Gen_Rand_Tree (const Compare &cmp=Compare()) noexcept | |
Initialize a random tree with random seed from system time and comparison criteria cmp | |
| void | swap (Gen_Rand_Tree &tree) noexcept |
Swap in constant time all the nodes of this with tree | |
| Gen_Rand_Tree (Gen_Rand_Tree &&other) noexcept | |
| Move constructor - transfers ownership of tree and RNG. | |
| Gen_Rand_Tree & | operator= (Gen_Rand_Tree &&other) noexcept |
| Move assignment - transfers ownership of tree and RNG. | |
| virtual | ~Gen_Rand_Tree () noexcept |
| Node * | insert (Node *p) noexcept |
| Insert a node in the tree. | |
| Node * | insert_dup (Node *p) noexcept |
| Insert a node in the tree. | |
| Node * | remove (const Key &key) noexcept |
| Remove a key from the tree. | |
| Node * | search (const Key &key) const noexcept |
| Search a key. | |
| Node * | search_or_insert (Node *p) noexcept |
| Search or insert a key. | |
| bool | verify () const |
Return true if this is a consistent randomized tree. | |
| Node *& | getRoot () noexcept |
| Return the tree's root. | |
| Node * | select (const size_t i) const |
| Return the i-th node in inorder sense. | |
| size_t | size () const noexcept |
| Return the number of nodes that have the tree. | |
| bool | is_empty () const noexcept |
| Return true if the tree is empty. | |
| std::pair< long, Node * > | position (const Key &key) const noexcept |
| Compute the inorder position of a key. | |
| std::pair< long, Node * > | find_position (const Key &key) const noexcept |
| Find the inorder position of a key in the tree. | |
| Node * | remove_pos (const size_t i) |
Remove the key at inorder position i | |
| bool | split_key (const Key &key, Gen_Rand_Tree &t1, Gen_Rand_Tree &t2) noexcept |
| Split the tree according to a key. | |
| void | split_key_dup (const Key &key, Gen_Rand_Tree &t1, Gen_Rand_Tree &t2) noexcept |
| Split the tree according to a key that could be in the tree. | |
| void | split_pos (size_t pos, Gen_Rand_Tree &t1, Gen_Rand_Tree &t2) noexcept |
| Split a extended binary tree according to a position. | |
| void | join (Gen_Rand_Tree &t, Gen_Rand_Tree &dup) noexcept |
Join this with t filtering the duplicated keys. | |
| void | join_dup (Gen_Rand_Tree &t) noexcept |
Join this with t independently of the presence of duplicated keys. | |
| void | join_exclusive (Gen_Rand_Tree &t) noexcept |
Join exclusive of this with t | |
Detailed Description
Randomized binary search tree.
This class implements a randomized binary search tree. It is shown that this type of tree always is equivalent to a classic binary search tree built from a random insertion sequence. Consequently, all the operations of this tree are \(O(\lg n)\) expected case, independently of insertion order and of removals are interleaved with insertions.
The principle of this tree is balancing by taking random decisions whose probabilities guarantee that each node will have a chance of \(1/n\) for becoming the root of the tree.
In addition, these trees support select() and position() operations. That is, their keys can be accessed according to their inorder position and logarithmic time. This allows to treat the tree as if it was an array.
This tree type is unbeatable when there are splits and and especially joins operations on very large and independent data sets. Other tree types perform the join of independent data sets in \(O(n \lg m)\), where \(n\) and \(m\) are the size of two data sets, while the randomized approach takes \(O(\max(\lg n, \lg m))\).
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.
Definition at line 842 of file tpl_rand_tree.H.
Member Typedef Documentation
◆ Base
| using Aleph::Rand_Tree< Key, Compare >::Base = Gen_Rand_Tree<RandNode, Key, Compare> |
Definition at line 844 of file tpl_rand_tree.H.
The documentation for this struct was generated from the following file:
