sdsl::louds_tree< BitVector, SelectSupport1, SelectSupport0 > Class Template Reference

A tree class based on the level order unary degree sequence (LOUDS) representation. More...

#include <louds_tree.hpp>

List of all members.

Public Types
typedef bit_vector::size_type	size_type
typedef louds_node	node_type
typedef BitVector	bit_vector_type
typedef SelectSupport1	select_1_type
typedef SelectSupport0	select_0_type
Public Member Functions
template<class Cst , class CstBfsIterator >
	louds_tree (const Cst &cst, const CstBfsIterator begin, const CstBfsIterator end)
	Constructor for a cst and a root node for the traversal.
node_type	root () const
	Returns the root node.
size_type	nodes () const
	Returns the number of nodes in the tree.
bool	is_leaf (const node_type &v) const
	Indicates if a node is a leaf.
size_type	degree (const node_type &v) const
	Returns the number of children of a node.
node_type	child (const node_type &v, size_type i) const
	Returns the i-child of a node.
node_type	parent (const node_type &v) const
	Returns the parent of a node v or root() if v==root().
size_type	id (const node_type &v) const
	Returns an unique id for each node in [0..size()-1].
Public Attributes
const bit_vector_type &	bv

---

Detailed Description

template<class BitVector = bit_vector, class SelectSupport1 = typename BitVector::select_1_type, class SelectSupport0 = typename BitVector::select_0_type>
class sdsl::louds_tree< BitVector, SelectSupport1, SelectSupport0 >

A tree class based on the level order unary degree sequence (LOUDS) representation.

Template Parameters:

BitVector	The bit vector representation used for LOUDS.
SelectSupport1	A select_support on 1-bits; it is needed for the child(v,i) operation.
SelectSupport0	A select_support on 0-bits; it is needed for the parent operation.

Example of the structure: A tree with balanced parentheses representation (()()(()())) is translated into 10001110011. Traverse the tree in breadth-first order an write for each node a 1-bit followed by as many 0-bits as the node has children.

Disadvantages of louds: No efficient support for subtree size.

---

Member Function Documentation

template<class BitVector = bit_vector, class SelectSupport1 = typename BitVector::select_1_type, class SelectSupport0 = typename BitVector::select_0_type>

node_type sdsl::louds_tree< BitVector, SelectSupport1, SelectSupport0 >::child	(	const node_type &	v,
		size_type	i
	)		const [inline]

Returns the i-child of a node.

Parameters:

v	The parent node.
i	Index of the child. Indexing starts at 1.

Precondition:

template<class BitVector = bit_vector, class SelectSupport1 = typename BitVector::select_1_type, class SelectSupport0 = typename BitVector::select_0_type>

size_type sdsl::louds_tree< BitVector, SelectSupport1, SelectSupport0 >::degree

(

const node_type &

v

)

const [inline]

Returns the number of children of a node.

Parameters:

v

A node.

template<class BitVector = bit_vector, class SelectSupport1 = typename BitVector::select_1_type, class SelectSupport0 = typename BitVector::select_0_type>

bool sdsl::louds_tree< BitVector, SelectSupport1, SelectSupport0 >::is_leaf

(

const node_type &

v

)

const [inline]

Indicates if a node is a leaf.

Parameters:

v

A node.

---

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

• sdsl/include/sdsl/louds_tree.hpp