Treap (a special type of randomized binary search tree) using nodes without virtual destructor. More...
#include <tpl_treap.H>
Public Types | |
| using | Base = Gen_Treap< TreapNode, Key, Compare > |
 Public Types inherited from Aleph::Gen_Treap< NodeType, Key, Compare > | |
| using | Node = NodeType< Key > |
Additional Inherited Members | |
| Public Member Functions inherited from Aleph::Gen_Treap< NodeType, Key, Compare > | |
| void | set_seed (const unsigned long seed) noexcept |
| Set the random number generator seed. | |
| void | swap (Gen_Treap &tree) noexcept |
Swap in constant time all the nodes of this with tree | |
| Compare & | key_comp () noexcept |
| return the comparison criteria | |
| Compare & | get_compare () noexcept |
| Gen_Treap (const unsigned long seed, const Compare &__cmp=Compare()) | |
Initialize a treap with random seed and comparison criteria __cmp | |
| Gen_Treap (const Compare &cmp=Compare()) | |
Initialize a treap with random seed from system time and comparison criteria cmp | |
| ~Gen_Treap () | |
| gsl_rng * | gsl_rng_object () noexcept |
| Get a pointer to gsl random number generator. | |
| Node *& | getRoot () noexcept |
| Return the tree's root. | |
| 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 * | search_or_insert (Node *p) noexcept |
| Search or insert a key. | |
| Node * | insert_dup (Node *p) noexcept |
| Insert a node in the tree. | |
| bool | verify () const noexcept |
Return true if this is a consistent treap. | |
| Node * | remove (const Key &key) noexcept |
| Remove a key from the tree. | |
| void | join (Gen_Treap &t, Gen_Treap &dup) noexcept |
Join this with t filtering the duplicated keys. | |
| void | join_dup (Gen_Treap &t) noexcept |
Join this with t independently of the presence of duplicated keys. | |
| void | join_exclusive (Gen_Treap &t) noexcept |
Join exclusive of this with t | |
| bool | split_key (const Key &key, Gen_Treap &t1, Gen_Treap &t2) |
| Split the tree according to a key. | |
| void | split_key_dup (const Key &key, Gen_Treap &t1, Gen_Treap &t2) |
| Split the tree according to a key that could be in the tree. | |
Detailed Description
Treap (a special type of randomized binary search tree) using nodes without virtual destructor.
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 perfomance of \(O(\lg n)\) for the majority of its operations.
The treap is faster than the randomized tree by a constant time (both approaches are logarithmic). However, since the priority is chosen just one time and the adjustements are done in a botton-top way (by contrast with the randomized which is top-bottom), the treap takes less time.
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 610 of file tpl_treap.H.
Member Typedef Documentation
◆ Base
| using Aleph::Treap< Key, Compare >::Base = Gen_Treap<TreapNode, Key, Compare> |
Definition at line 612 of file tpl_treap.H.
The documentation for this struct was generated from the following file:
