Class LoudsTree

• Defined in File LoudsTree.h

Class Documentation

class LoudsTree

an ordered tree in 2n + 1 bits by LOUDS, its nodes by levels

Public Functions

LoudsTree(void)

the empty tree

explicit LoudsTree(const std::vector<std::vector<std::size_t>> &c)

the tree whose node u has the children c[ u ], in order, rooted at 0

Pre:

c describes a tree rooted at 0

explicit LoudsTree(BitVector b)

the tree whose code is b

Pre:

b is a code of LOUDS (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 degree(std::size_t v) const

Pre:

v < size()

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

nil for the root

Pre:

v < size()

std::size_t leftmostChild(std::size_t v) const

the first child, nil for a leaf

Pre:

v < size()

std::size_t rightSibling(std::size_t v) const

the next sibling, nil for the last one

Pre:

v < size()

std::size_t child(std::size_t v, std::size_t i) const

the child i, from 0

Pre:

v < size() and i < degree( v )

bool isLeaf(std::size_t v) const

Pre:

v < size()

const BitVector &bits(void) const

B, the code.

Public Static Attributes

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

no node