Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
balanced_structures::skiplist Namespace Reference

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 Documentation


Variable Documentation

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

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.

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines