Class BPTree

Class Documentation

class BPTree

an ordered tree in 2n bits by balanced parentheses, its nodes in preorder

Public Functions

BPTree(void) = default

the empty tree

explicit BPTree(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 BPTree(BitVector b)

the tree whose parentheses are b

Pre:

b is balanced and encloses one 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 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 degree(std::size_t v) const

the number of children, by a walk along them

Pre:

v < size()

std::size_t subtreeSize(std::size_t v) const

the nodes of the subtree of v, v included

Pre:

v < size()

std::size_t depth(std::size_t v) const

the edges from the root

Pre:

v < size()

bool isAncestor(std::size_t u, std::size_t v) const

whether u is v or one of its ancestors

Pre:

u , v < size()

bool isLeaf(std::size_t v) const
Pre:

v < size()

const BalancedParentheses &parentheses(void) const

the parentheses, with their matching

Public Static Attributes

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

no node