Super class of binary space-partitioning trees. More...

#include <shark/Models/Trees/BinaryTree.h>

Inheritance diagram for shark::BinaryTree< InputT >:

Collaboration diagram for shark::BinaryTree< InputT >:

Public Member Functions
	BinaryTree (std::size_t size)
	Root node constructor: build the tree from data. More...

virtual	~BinaryTree ()
	Destroy the tree and its internal data structures. More...

BinaryTree *	parent ()
	parent node More...

const BinaryTree *	parent () const
	parent node More...

bool	hasChildren () const

bool	isLeaf () const

BinaryTree *	left ()
	"left" sub-node of the binary tree More...

const BinaryTree *	left () const
	"left" sub-node of the binary tree More...

BinaryTree *	right ()
	"right" sub-node of the binary tree More...

const BinaryTree *	right () const
	"right" sub-node of the binary tree More...

std::size_t	size () const
	number of points inside the space represented by this node More...

std::size_t	nodes () const
	number of sub-nodes in this tree (including the node itself) More...

std::size_t	index (std::size_t point) const

double	distanceFromPlane (value_type const &point) const
	Function describing the separation of space. More...

double	threshold () const
	Separation threshold. More...

bool	isLeft (value_type const &point) const

bool	isRight (value_type const &point) const

virtual AbstractKernelFunction < value_type > const *	kernel () const
	If the tree uses a kernel metric, returns a pointer to the kernel object, else NULL. More...

virtual double	squaredDistanceLowerBound (value_type const &point) const =0
	Compute lower bound on the squared distance to the space cell. More...

Protected Member Functions
	BinaryTree (BinaryTree parent, std::size_t list, std::size_t size)
	Sub-node constructor. More...

virtual double	funct (value_type const &point) const =0
	Function describing the separation of space. More...

template<class Range1 , class Range2 >
boost::range_iterator< Range2 > ::type	splitList (Range1 &values, Range2 &points)
	Split the data in the point list and calculate the treshold accordingly. More...

Protected Attributes
BinaryTree *	mep_parent
	parent node More...

BinaryTree *	mp_left
	"left" child node More...

BinaryTree *	mp_right
	"right" child node More...

std::size_t *	mp_indexList
	list of indices to points in the dataset More...

std::size_t	m_size
	number of points in this node More...

std::size_t	m_nodes
	number of nodes in the sub-tree represented by this node More...

double	m_threshold
	threshold for the separating function More...

Detailed Description

template<class InputT>
class shark::BinaryTree< InputT >

Super class of binary space-partitioning trees.

: This class represents a generic node in a binary space-partitioning tree. At each junction the space cell represented by the parent node is split into sub-cells by thresholding a real-valued function. Different sub-classes implement different such functions. The absolute value of the function minus the threshold m_threshold must represent the distance to the separating hyper-surface in the underlying metric. This allows for linear separation, but also for kernel-induced feature spaces and other embeddings.

Definition at line 120 of file BinaryTree.h.

Constructor & Destructor Documentation

template<class InputT>

shark::BinaryTree< InputT >::BinaryTree ( std::size_t size )

inline

Root node constructor: build the tree from data.

Please refer the specific sub-classes such as KDTree for examples of how the binary tree is built.

Definition at line 130 of file BinaryTree.h.

template<class InputT>

virtual shark::BinaryTree< InputT >::~BinaryTree ( )

inlinevirtual

Destroy the tree and its internal data structures.

Definition at line 147 of file BinaryTree.h.

template<class InputT>

shark::BinaryTree< InputT >::BinaryTree	(	BinaryTree< InputT > *	parent,
		std::size_t *	list,
		std::size_t	size
	)

inlineprotected

Sub-node constructor.

: Initialize a sub-node

Definition at line 282 of file BinaryTree.h.

Member Function Documentation

template<class InputT>

double shark::BinaryTree< InputT >::distanceFromPlane ( value_type const & point ) const

inline

Function describing the separation of space.

: This function is shifted by subtracting the threshold from the virtual function "funct" (which acts as a "decision" function to split space into sub-cells). The result of this function describes "signed" distance to the separation boundary, and the two cells are thresholded at zero. We obtain the two cells:
left ("negative") cell: {x | distance(x) < 0}
right ("positive") cell {x | distance(x) >= 0}

Definition at line 216 of file BinaryTree.h.

Referenced by shark::LCTree< VectorType, CuttingAccuracy >::squaredDistanceLowerBound().

template<class InputT>

virtual double shark::BinaryTree< InputT >::funct ( value_type const & point ) const

protectedpure virtual

Function describing the separation of space.

: This is the primary interface for customizing sub-classes.

: This function splits the space represented by the node by thresholding at m_threshold. The "negative" cell, represented in the "left" sub-node, represents the space {x | funct(x) < threshold}. The "positive" cell, represented by the "right" sub-node, represents {x | funct(x) >= threshold}. The function needs to be normalized such that |f(x) - f(y)| is the distance between {z | f(z) = f(x)} and {z | f(z) = f(y)}, w.r.t. the distance function also used by the virtual function squaredDistanceLowerBound. The exact distance function does not matter as long as the same distance function is used in both cases.

Implemented in shark::KDTree< InputT >.

Referenced by shark::BinaryTree< VectorType >::distanceFromPlane(), shark::BinaryTree< VectorType >::isLeft(), and shark::BinaryTree< VectorType >::isRight().

template<class InputT>

bool shark::BinaryTree< InputT >::hasChildren ( ) const

inline

Does this node have children? Opposite of isLeaf()

Definition at line 166 of file BinaryTree.h.

Referenced by shark::HierarchicalClustering< InputT >::hardMembership(), and shark::IterativeNNQuery< DataContainer >::IterativeNNQuery().

template<class InputT>

std::size_t shark::BinaryTree< InputT >::index ( std::size_t point ) const

inline

Definition at line 196 of file BinaryTree.h.

template<class InputT>

bool shark::BinaryTree< InputT >::isLeaf ( ) const

inline

Is this a leaf node? Opposite of hasChildren()

Definition at line 171 of file BinaryTree.h.

template<class InputT>

bool shark::BinaryTree< InputT >::isLeft ( value_type const & point ) const

inline

return true if the reference point belongs to the "left" sub-node, or to the "negative" sub-cell.

Definition at line 227 of file BinaryTree.h.

Referenced by shark::HierarchicalClustering< InputT >::hardMembership(), and shark::IterativeNNQuery< DataContainer >::IterativeNNQuery().

template<class InputT>

bool shark::BinaryTree< InputT >::isRight ( value_type const & point ) const

inline

return true if the reference point belongs to the "right" sub-node, or to the "positive" sub-cell.

Definition at line 232 of file BinaryTree.h.

template<class InputT>

virtual AbstractKernelFunction<value_type> const* shark::BinaryTree< InputT >::kernel ( ) const

inlinevirtual

If the tree uses a kernel metric, returns a pointer to the kernel object, else NULL.

Definition at line 236 of file BinaryTree.h.

template<class InputT>

BinaryTree* shark::BinaryTree< InputT >::left ( )

inline

"left" sub-node of the binary tree

Definition at line 175 of file BinaryTree.h.

Referenced by shark::KDTree< InputT >::buildTree(), shark::HierarchicalClustering< InputT >::hardMembership(), and shark::IterativeNNQuery< DataContainer >::IterativeNNQuery().

template<class InputT>

const BinaryTree* shark::BinaryTree< InputT >::left ( ) const

inline

"left" sub-node of the binary tree

Definition at line 178 of file BinaryTree.h.

template<class InputT>

std::size_t shark::BinaryTree< InputT >::nodes ( ) const

inline

number of sub-nodes in this tree (including the node itself)

Definition at line 193 of file BinaryTree.h.

Referenced by shark::LCTree< VectorType, CuttingAccuracy >::buildTree(), shark::KHCTree< Container, CuttingAccuracy >::buildTree(), shark::KDTree< InputT >::buildTree(), shark::HierarchicalClustering< InputT >::hardMembership(), and shark::HierarchicalClustering< InputT >::numberOfClusters().

template<class InputT>

BinaryTree* shark::BinaryTree< InputT >::parent ( )

inline

parent node

Definition at line 158 of file BinaryTree.h.

Referenced by shark::KDTree< InputT >::lower(), and shark::KDTree< InputT >::upper().

template<class InputT>

const BinaryTree* shark::BinaryTree< InputT >::parent ( ) const

inline

parent node

Definition at line 161 of file BinaryTree.h.

template<class InputT>

BinaryTree* shark::BinaryTree< InputT >::right ( )

inline

"right" sub-node of the binary tree

Definition at line 182 of file BinaryTree.h.

Referenced by shark::KDTree< InputT >::buildTree(), shark::HierarchicalClustering< InputT >::hardMembership(), and shark::IterativeNNQuery< DataContainer >::IterativeNNQuery().

template<class InputT>

const BinaryTree* shark::BinaryTree< InputT >::right ( ) const

inline

"right" sub-node of the binary tree

Definition at line 185 of file BinaryTree.h.

template<class InputT>

std::size_t shark::BinaryTree< InputT >::size ( ) const

inline

number of points inside the space represented by this node

Definition at line 189 of file BinaryTree.h.

template<class InputT>

template<class Range1 , class Range2 >

boost::range_iterator<Range2>::type shark::BinaryTree< InputT >::splitList	(	Range1 &	values,
		Range2 &	points
	)

inlineprotected

Split the data in the point list and calculate the treshold accordingly.

The method computes the optimal threshold given the distance of every element of the set and partitions the point range accordingly

Parameters

values	the value of every point returned by funct(point)
points	the points themselves

Returns: returns the position were the point list was split

Definition at line 322 of file BinaryTree.h.

Referenced by shark::KDTree< InputT >::buildTree().

template<class InputT>

virtual double shark::BinaryTree< InputT >::squaredDistanceLowerBound ( value_type const & point ) const

pure virtual

Compute lower bound on the squared distance to the space cell.

: For efficient use of the triangle inequality the space cell represented by each node needs to provide (a lower bound on) the distance of a query point to the space cell represented by this node. Search is fast if this bound is tight.

Implemented in shark::KDTree< InputT >.

template<class InputT>

double shark::BinaryTree< InputT >::threshold ( ) const

inline

Separation threshold.

Definition at line 221 of file BinaryTree.h.

Referenced by shark::KDTree< InputT >::lower(), and shark::KDTree< InputT >::upper().