A tree class based on the balances parentheses (BP) representation. More...

#include <bp.h>

Inheritance diagram for pixie::BPTree< RMMTree >:

Public Types
using	Node = TreeNode
	A node class of BP tree.

Public Types inherited from pixie::TreeBase< BPTree< RMMTree > >
using	Node

Public Member Functions
	BPTree (const std::vector< std::uint64_t > &words, size_t tree_size)
	Constructor from an external array of uint64_t.

Node	root_impl () const
	Returns the root node.

size_t	size_impl () const
	Returns the size of the tree.

bool	is_leaf_impl (const Node &node) const
	Indicates if `node` is a leaf.

bool	is_root_impl (const Node &node) const
	Indicates if `node` is a root.

size_t	degree_impl (const Node &node) const
	Returns the number of children of a `node` this method has O(d) time complexity!

Node	first_child_impl (const Node &node) const
	Returns first child of a `node`.

Node	child_impl (const Node &node, size_t i) const
	Returns the i-th child of `node` Indexing starts at 0 this method has O(i) time complexity!

Node	parent_impl (const Node &node) const
	Returns the parent of a `node` if `node` is not root, else returns root.

bool	is_last_child_impl (const Node &node) const
	Indicates if `node` is last child.

Node	next_sibling_impl (const Node &node) const
	Returns next sibling of a `node`.

Public Member Functions inherited from pixie::TreeBase< BPTree< RMMTree > >
Node	root () const
	Return the root node.

std::size_t	size () const
	Return the number of nodes.

bool	empty () const
	Check whether the tree contains no nodes.

bool	is_leaf (const Node &node) const
	Check whether `node` has no children.

bool	is_root (const Node &node) const
	Check whether `node` is the root.

std::size_t	degree (const Node &node) const
	Return the number of children of `node`.

Node	first_child (const Node &node) const
	Return the first child of `node`.

Node	child (const Node &node, std::size_t index) const
	Return a child of `node` by zero-based index.

Node	parent (const Node &node) const
	Return the parent of `node`.

bool	is_last_child (const Node &node) const
	Check whether `node` is its parent's last child.

Node	next_sibling (const Node &node) const
	Return the next sibling of `node`.

Detailed Description

template<typename RMMTree>
class pixie::BPTree< RMMTree >

A tree class based on the balances parentheses (BP) representation.

Member Function Documentation

◆ child_impl()

template<typename RMMTree>

Node pixie::BPTree< RMMTree >::child_impl	(	const Node &	node,
		size_t	i ) const

inline

Returns the i-th child of node Indexing starts at 0 this method has O(i) time complexity!

TODO try make this faster

◆ degree_impl()

template<typename RMMTree>

size_t pixie::BPTree< RMMTree >::degree_impl ( const Node & node ) const

inline

Returns the number of children of a node this method has O(d) time complexity!

TODO try make this faster

The documentation for this class was generated from the following file:

include/pixie/tree/bp.h

Public Types

Public Member Functions

Detailed Description

Member Function Documentation

◆ child_impl()

◆ degree_impl()