Class JacobsonTree

• Defined in File JacobsonTree.h

Class Documentation

class JacobsonTree

a binary tree in 2n + 1 bits, its nodes by levels

Public Functions

JacobsonTree(void)

the empty tree

explicit JacobsonTree(const std::vector<std::pair<std::size_t, std::size_t>> &c)

the tree whose node u has the children c[ u ].first (left) and c[ u ].second (right), nil if missing, rooted at 0

Pre:

c describes a binary tree rooted at 0

explicit JacobsonTree(BitVector b)

the tree whose code by levels is b

Pre:

b is the code of a binary tree (an audit)

std::size_t size(void) const

the number of nodes

std::size_t root(void) const

the root, nil if the tree is empty

std::size_t left(std::size_t v) const

Pre:

v < size()

std::size_t right(std::size_t v) const

Pre:

v < size()

std::size_t parent(std::size_t v) const

nil for the root

Pre:

v < size()

bool isLeaf(std::size_t v) const

Pre:

v < size()

const BitVector &bits(void) const

B, the code by levels.

Public Static Attributes

static constexpr std::size_t nil = std::size_t(-1)

no node