The RPlusTreeSplit class performs the split process of a node on overflow. More...

Public Types
typedef SplitPolicyType	SplitPolicy

Static Public Member Functions
template<typename TreeType >
static void	SplitLeafNode (TreeType *tree, std::vector< bool > &relevels)
	Split a leaf node using the "default" algorithm. More...

template<typename TreeType >
static bool	SplitNonLeafNode (TreeType *tree, std::vector< bool > &relevels)
	Split a non-leaf node using the "default" algorithm. More...

Static Private Member Functions
template<typename TreeType >
static void	AddFakeNodes (const TreeType tree, TreeType emptyTree)
	This method is used to make sure that the tree has equivalent maximum depth in every branch. More...

template<typename TreeType >
static void	InsertNodeIntoTree (TreeType destTree, TreeType srcNode)
	Insert a node into another node. More...

template<typename TreeType >
static bool	PartitionNode (const TreeType *node, size_t &minCutAxis, typename TreeType::ElemType &minCut)
	Partition a node using SweepType. More...

template<typename TreeType >
static void	SplitLeafNodeAlongPartition (TreeType tree, TreeType treeOne, TreeType *treeTwo, const size_t cutAxis, const typename TreeType::ElemType cut)
	Split a leaf node along an axis. More...

template<typename TreeType >
static void	SplitNonLeafNodeAlongPartition (TreeType tree, TreeType treeOne, TreeType *treeTwo, const size_t cutAxis, const typename TreeType::ElemType cut)
	Split a non-leaf node along an axis. More...

Detailed Description

template<typename SplitPolicyType, template< typename > class SweepType>
class mlpack::tree::RPlusTreeSplit< SplitPolicyType, SweepType >

The RPlusTreeSplit class performs the split process of a node on overflow.

Template Parameters

SplitPolicyType	The class that helps to determine the subtree into which we should insert a child node.
SweepType	The class that finds the partition of a node along a given axis. The partition algorithm tries to find a partition along each axis, evaluates each partition and chooses the best one.

Definition at line 32 of file r_plus_tree_split.hpp.

Member Typedef Documentation

template<typename SplitPolicyType , template< typename > class SweepType>

typedef SplitPolicyType mlpack::tree::RPlusTreeSplit< SplitPolicyType, SweepType >::SplitPolicy

Definition at line 35 of file r_plus_tree_split.hpp.

Member Function Documentation

template<typename SplitPolicyType , template< typename > class SweepType>

template<typename TreeType >

static void mlpack::tree::RPlusTreeSplit< SplitPolicyType, SweepType >::AddFakeNodes	(	const TreeType *	tree,
		TreeType *	emptyTree
	)

staticprivate

This method is used to make sure that the tree has equivalent maximum depth in every branch.

The method should be invoked if one of two resulting subtrees is empty after the split process (i.e. the subtree contains no children). The method convert the empty node into an empty subtree (increase the node in depth).

Parameters

tree	One of two subtrees that is not empty.
emptyTree	The empty subtree.

template<typename SplitPolicyType , template< typename > class SweepType>

template<typename TreeType >

static void mlpack::tree::RPlusTreeSplit< SplitPolicyType, SweepType >::InsertNodeIntoTree	(	TreeType *	destTree,
		TreeType *	srcNode
	)

staticprivate

Insert a node into another node.

template<typename SplitPolicyType , template< typename > class SweepType>

template<typename TreeType >

static bool mlpack::tree::RPlusTreeSplit< SplitPolicyType, SweepType >::PartitionNode	(	const TreeType *	node,
		size_t &	minCutAxis,
		typename TreeType::ElemType &	minCut
	)

staticprivate

Partition a node using SweepType.

This method invokes SweepType::Sweep(Non)LeafNode() for each dimension and chooses the best one. The method returns false if the node needn't partitioning. Overwise, the method returns true. If the method failed in finding an acceptable partition, the minCutAxis will be equal to the number of dimensions.

Parameters

node	The node that is being split.
minCutAxis	The axis along which the node will be split.
minCut	The coordinate at which the node will be split.

template<typename SplitPolicyType , template< typename > class SweepType>

template<typename TreeType >

static void mlpack::tree::RPlusTreeSplit< SplitPolicyType, SweepType >::SplitLeafNode	(	TreeType *	tree,
		std::vector< bool > &	relevels
	)

static

Split a leaf node using the "default" algorithm.

If necessary, this split will propagate upwards through the tree.

Parameters

node.	The node that is being split.
relevels	Not used.

template<typename SplitPolicyType , template< typename > class SweepType>

template<typename TreeType >

static void mlpack::tree::RPlusTreeSplit< SplitPolicyType, SweepType >::SplitLeafNodeAlongPartition	(	TreeType *	tree,
		TreeType *	treeOne,
		TreeType *	treeTwo,
		const size_t	cutAxis,
		const typename TreeType::ElemType	cut
	)

staticprivate

Split a leaf node along an axis.

Parameters

tree	The node that is being split into two new nodes.
treeOne	The first subtree of two resulting subtrees.
treeOne	The second subtree of two resulting subtrees.
cutAxis	The axis along which the node is being split.
cut	The coordinate at which the node is being split.

template<typename SplitPolicyType , template< typename > class SweepType>

template<typename TreeType >

static bool mlpack::tree::RPlusTreeSplit< SplitPolicyType, SweepType >::SplitNonLeafNode	(	TreeType *	tree,
		std::vector< bool > &	relevels
	)

static

Split a non-leaf node using the "default" algorithm.

If this is a root node, the tree increases in depth.

Parameters

node.	The node that is being split.
relevels	Not used.

template<typename SplitPolicyType , template< typename > class SweepType>

template<typename TreeType >

static void mlpack::tree::RPlusTreeSplit< SplitPolicyType, SweepType >::SplitNonLeafNodeAlongPartition	(	TreeType *	tree,
		TreeType *	treeOne,
		TreeType *	treeTwo,
		const size_t	cutAxis,
		const typename TreeType::ElemType	cut
	)

staticprivate

Split a non-leaf node along an axis.

This method propagates the split downward up to a leaf node if necessary.

Parameters

tree	The node that is being split into two new nodes.
treeOne	The first subtree of two resulting subtrees.
treeOne	The second subtree of two resulting subtrees.
cutAxis	The axis along which the node is being split.
cut	The coordinate at which the node is being split.

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

src/mlpack/core/tree/rectangle_tree/r_plus_tree_split.hpp

Public Types

Static Public Member Functions

Static Private Member Functions

Detailed Description

template<typename SplitPolicyType, template< typename > class SweepType> class mlpack::tree::RPlusTreeSplit< SplitPolicyType, SweepType >

Member Typedef Documentation

Member Function Documentation

template<typename SplitPolicyType, template< typename > class SweepType>
class mlpack::tree::RPlusTreeSplit< SplitPolicyType, SweepType >