Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
Namespaces | |
namespace | node_utils |
namespace | trail |
Classes | |
class | Skiplist |
struct | ConstIterator |
class | Node |
Typedefs | |
typedef short | LevelType |
Variables | |
static const int | LEVELUP_PROB = 100 / 4 |
static const LevelType | MAXLEVEL = 15 |
typedef short balanced_structures::skiplist::LevelType |
const int balanced_structures::skiplist::LEVELUP_PROB = 100 / 4 [static] |
LEVELUP_PROB is probability of "increasing" level of a node in the percent. Thus, node of level L is created with probability LEVELUP_PROB^(L - 1) (1 - LEVELUP_PROB) . The average level of nodes in skiplist will be 1 / 0LEVELUP_PROB
const LevelType balanced_structures::skiplist::MAXLEVEL = 15 [static] |
Maximum allowed level of a node.
Note: current value of 15 is pretty good upper bound if you are using LEVELUP_PROB = 4 and less than 10^8 nodes.