pbat::common::BinaryRadixTree< TIndex > Class Template Reference

Binary radix tree implementation. More...

#include <BinaryRadixTree.h>

Public Member Functions
template<class TDerived>
	BinaryRadixTree (Eigen::DenseBase< TDerived > const &codes, bool bStoreParent=false)
	Construct a new Binary Radix Tree object.
template<class TDerived>
void	Construct (Eigen::DenseBase< TDerived > const &codes, bool bStoreParent=false)
	Construct a Radix Tree from a sorted list of unsigned integral codes.
TIndex	Left (TIndex i) const
	Get the left child of internal node i
TIndex	Right (TIndex i) const
	Get the right child of internal node i
TIndex	Parent (TIndex i) const
	Get the parent of a node.
TIndex	InternalNodeCount () const
	Get the number of internal nodes.
TIndex	LeafCount () const
	Get the number of leaf nodes.
bool	IsLeaf (TIndex i) const
	Check if a node is a leaf.
constexpr TIndex	Root () const
	Get the root of the tree.
TIndex	CodeIndex (TIndex leaf) const
	Get the index of the code associated with a leaf node.
TIndex	LeafIndex (TIndex codeIdx) const
	Get the index of the leaf node associated with a code.
auto	Children () const
	Get the children array of the tree.
auto	Left () const
	Left child array of the tree.
auto	Right () const
	Right child array of the tree.
auto	Parent () const
	Get the parent array of the tree.
bool	HasParentRelationship () const
	Check if the tree has parent relationships.

Detailed Description

template<class TIndex = Index>
class pbat::common::BinaryRadixTree< TIndex >

Binary radix tree implementation.

Template Parameters

TIndex

Type of the indices to use for tree topology

Constructor & Destructor Documentation

BinaryRadixTree()

template<class TIndex>

template<class TDerived>

pbat::common::BinaryRadixTree< TIndex >::BinaryRadixTree ( Eigen::DenseBase< TDerived > const & codes, bool bStoreParent = false )

inline

Construct a new Binary Radix Tree object.

Template Parameters

TDerived

Type of the Eigen expression for codes

Parameters

codes	Sorted list of integral codes
bStoreParent	Store parent indices/relationships if true

Member Function Documentation

Children()

template<class TIndex = Index>

auto pbat::common::BinaryRadixTree< TIndex >::Children ( ) const

inline

Get the children array of the tree.

Returns

2 x |# internal nodes| matrix c, s.t. c(0,i) -> left child of internal node i, c(1,i) -> right child of internal node i

CodeIndex()

template<class TIndex = Index>

TIndex pbat::common::BinaryRadixTree< TIndex >::CodeIndex ( TIndex leaf ) const

inline

Get the index of the code associated with a leaf node.

Parameters

leaf	Index of the leaf node

Returns

Index of the code

Construct()

template<class TIndex>

template<class TDerived>

void pbat::common::BinaryRadixTree< TIndex >::Construct ( Eigen::DenseBase< TDerived > const & codes, bool bStoreParent = false )

inline

Construct a Radix Tree from a sorted list of unsigned integral codes.

Implementation has average linear time complexity \( O(n) \), where \( n \) is the number of codes/leaves. We do not prove the worst case time complexity, but it is most probably the same as the average case.

We visit \( n-1 \) internal nodes of the tree during construction. At each internal node \( i \), a \( O(\log(n)) \) binary search is performed over the range of codes covered by that internal node. Assuming we always split ranges in the middle, the work done at each level k of the tree is \( 2^k \log(\frac{n}{2^k}) \). The total work is thus

\[\sum_{k=0}^{\log(n)} 2^k \log(\frac{n}{2^k}) = \sum_{k=0}^{\log(n)} 2^k \log(n) - \sum_{k=0}^{\log(n)} 2^k \log(2^k) \]

The first term is a constant \( \log(n) \) times the sum of a geometric series, which is \( 2^{\log(n)+1} - 1 = 2n - 1 \), leading to

\[\log(n) (2n - 1) \]

The second term can be written as the series

\[S = 0 \cdot 2^0 + 1 \cdot 2^1 + 2 \cdot 2^2 + \ldots + \log(n) \cdot 2^{\log(n)} \]

We can rewrite this as

\[2S - S = -2^1 - 2^2 - 2^3 + \ldots - 2^{\log(n)} + \log(n) 2^{\log(n)+1} \]

The negative terms form a similar geometric series

\[-\sum_{k=0}^{\log(n)} 2^k = -(2n - 1) \]

while the positive term can be simplified to

\[\log(n) 2^{\log(n)+1} = \log(n) 2n \]

Subtracting the 2nd term from the first leads to

\[\log(n) (2n - 1) - \log(n) 2n + 2n - 1 = 2n - \log(n) - 1 \]

Thus, the time complexity is \( O(n) \).

Template Parameters

TDerived

Type of the Eigen expression for codes

Parameters

codes	Sorted list of integral codes
bStoreParent	Store parent indices/relationships if true

HasParentRelationship()

template<class TIndex = Index>

bool pbat::common::BinaryRadixTree< TIndex >::HasParentRelationship ( ) const

inline

Check if the tree has parent relationships.

Returns

true if the tree has parent relationships, false otherwise

InternalNodeCount()

template<class TIndex = Index>

TIndex pbat::common::BinaryRadixTree< TIndex >::InternalNodeCount ( ) const

inline

Get the number of internal nodes.

Returns

Number of internal nodes

IsLeaf()

template<class TIndex = Index>

bool pbat::common::BinaryRadixTree< TIndex >::IsLeaf ( TIndex i ) const

inline

Check if a node is a leaf.

Parameters

i	Index of the node

Returns

true if the node is a leaf, false otherwise

LeafCount()

template<class TIndex = Index>

TIndex pbat::common::BinaryRadixTree< TIndex >::LeafCount ( ) const

inline

Get the number of leaf nodes.

Returns

Number of leaf nodes

LeafIndex()

template<class TIndex = Index>

TIndex pbat::common::BinaryRadixTree< TIndex >::LeafIndex ( TIndex codeIdx ) const

inline

Get the index of the leaf node associated with a code.

Parameters

codeIdx

Index of the code

Returns

Index of the leaf node

Left() [1/2]

template<class TIndex = Index>

auto pbat::common::BinaryRadixTree< TIndex >::Left ( ) const

inline

Left child array of the tree.

Returns

|# internal nodes| vector l, s.t. l(i) -> left child of internal node i

Left() [2/2]

template<class TIndex = Index>

TIndex pbat::common::BinaryRadixTree< TIndex >::Left ( TIndex i ) const

inline

Get the left child of internal node i

Parameters

i	Index of the internal node

Returns

Index of the left child.

Precondition

IsLeaf(i) is false

Parent() [1/2]

template<class TIndex = Index>

auto pbat::common::BinaryRadixTree< TIndex >::Parent ( ) const

inline

Get the parent array of the tree.

Note

The root node is its own parent, i.e. p(0) == 0 is true

Returns

|# internal + leaf nodes| vector p, s.t. p(i) -> parent of node i

Parent() [2/2]

template<class TIndex = Index>

TIndex pbat::common::BinaryRadixTree< TIndex >::Parent ( TIndex i ) const

inline

Get the parent of a node.

Parameters

i	Index of the node

Returns

Index of the parent

Right() [1/2]

template<class TIndex = Index>

auto pbat::common::BinaryRadixTree< TIndex >::Right ( ) const

inline

Right child array of the tree.

Returns

|# internal nodes| vector r, s.t. r(i) -> right child of internal node i

Right() [2/2]

template<class TIndex = Index>

TIndex pbat::common::BinaryRadixTree< TIndex >::Right ( TIndex i ) const

inline

Get the right child of internal node i

Parameters

i	Index of the internal node

Returns

Index of the right child

Precondition

IsLeaf(i) is false

Root()

template<class TIndex = Index>

TIndex pbat::common::BinaryRadixTree< TIndex >::Root ( ) const

inlineconstexpr

Get the root of the tree.

Returns

Index of the root node

---

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

• C:/git/PhysicsBasedAnimationToolkit/source/pbat/common/BinaryRadixTree.h