random-tree

Treat Tree class as a standard self-balancing binary search tree with each node bearing a value:

struct NodeValue {
    std::string nextValue;
    unsigned long left, count, right;
};

This struct has the following constraints:

NodeValue.left = Node.left.left + Node.left.count + Node.left.right;
NodeValue.right = Node.right.left + Node.right.count + Node.right.right;

Pick a random leaf as:

Node Tree::randomNode() {
    double p = rand();
    return root.randomNode(p);
}

Node Node::randomNode(double p) {
    double left_p, my_p, right_p;
    left_p = NodeValue.left / SUM(NodeValue.left, NodeValue.count, NodeValue.right);
    my_p = NodeValue.count / SUM(NodeValue.left, NodeValue.count, NodeValue.right);
    right_p = NodeValue.right / SUM(NodeValue.left, NodeValue.count, NodeValue.right);
    if (p < left_p) {
        return left.randomNode(p / left_p);
    } else if (p >= left_p + my_p) {
        return right.randomNode(p / right_p);
    } else {
        return self;
    }
}

Node::incrementNode() {
    NodeValue.count++;
    fixParent();
}

Node::fixLeft(left) {
    NodeValue.left = left;
    fixParent();
}

Node::fixRight(right) {
    NodeValue.right = right;
    fixParent();
}

Node::fixParent() {
    SUM = NodeValue.left + NodeValue.count + NodeValue.right;
    if (self == parent->left) {
        parent->fixLeft(SUM);
    } else {
        parent->fixRight(SUM);
    }
}

Insertion like self-balancing binary tree [O(log n)], fixing left/right counts of ALL ancestors.  Collision detection (find) remains O(log n), as the balancing should be done relative to NodeValue.value, rather than left, count, or right.