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

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

Inheritance diagram for shark::BinaryTree< InputT >:

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

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

BinaryTree *	parent ()
	parent node

const BinaryTree *	parent () const
	parent node

bool	hasChildren () const

bool	isLeaf () const

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

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

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

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

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

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

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

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

double	threshold () const
	Separation threshold.

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.

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

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

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

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

Protected Attributes
BinaryTree *	mep_parent
	parent node

BinaryTree *	mp_left
	"left" child node

BinaryTree *	mp_right
	"right" child node

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

std::size_t	m_size
	number of points in this node

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

double	m_threshold
	threshold for the separating function

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 137 of file BinaryTree.h.

Constructor & Destructor Documentation

◆ BinaryTree() [1/2]

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 147 of file BinaryTree.h.

References shark::BinaryTree< InputT >::m_size, shark::BinaryTree< InputT >::mp_indexList, and SHARK_ASSERT.

◆ ~BinaryTree()

template<class InputT >

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

inlinevirtual

Destroy the tree and its internal data structures.

Definition at line 164 of file BinaryTree.h.

References shark::BinaryTree< InputT >::mep_parent, shark::BinaryTree< InputT >::mp_indexList, shark::BinaryTree< InputT >::mp_left, and shark::BinaryTree< InputT >::mp_right.

◆ BinaryTree() [2/2]

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 275 of file BinaryTree.h.

Member Function Documentation

◆ distanceFromPlane()

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 233 of file BinaryTree.h.

References shark::BinaryTree< InputT >::funct(), and shark::BinaryTree< InputT >::m_threshold.

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

◆ funct()

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< InputT >::distanceFromPlane(), shark::BinaryTree< InputT >::isLeft(), and shark::BinaryTree< InputT >::isRight().

◆ hasChildren()

template<class InputT >

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

inline

Does this node have children? Opposite of isLeaf()

Definition at line 183 of file BinaryTree.h.

References shark::BinaryTree< InputT >::mp_left.

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

◆ index()

template<class InputT >

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

inline

Definition at line 213 of file BinaryTree.h.

References shark::BinaryTree< InputT >::mp_indexList.

◆ isLeaf()

template<class InputT >

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

inline

Is this a leaf node? Opposite of hasChildren()

Definition at line 188 of file BinaryTree.h.

References shark::BinaryTree< InputT >::mp_left.

◆ isLeft()

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 244 of file BinaryTree.h.

References shark::BinaryTree< InputT >::funct(), and shark::BinaryTree< InputT >::m_threshold.

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

◆ isRight()

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 249 of file BinaryTree.h.

References shark::BinaryTree< InputT >::funct(), and shark::BinaryTree< InputT >::m_threshold.

◆ kernel()

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 253 of file BinaryTree.h.

◆ left() [1/2]

template<class InputT >

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

inline

"left" sub-node of the binary tree

Definition at line 192 of file BinaryTree.h.

References shark::BinaryTree< InputT >::mp_left.

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

◆ left() [2/2]

template<class InputT >

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

inline

"left" sub-node of the binary tree

Definition at line 195 of file BinaryTree.h.

References shark::BinaryTree< InputT >::mp_left.

◆ nodes()

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 210 of file BinaryTree.h.

References shark::BinaryTree< InputT >::m_nodes.

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

◆ parent() [1/2]

template<class InputT >

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

inline

parent node

Definition at line 175 of file BinaryTree.h.

References shark::BinaryTree< InputT >::mep_parent.

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

◆ parent() [2/2]

template<class InputT >

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

inline

parent node

Definition at line 178 of file BinaryTree.h.

References shark::BinaryTree< InputT >::mep_parent.

◆ right() [1/2]

template<class InputT >

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

inline

"right" sub-node of the binary tree

Definition at line 199 of file BinaryTree.h.

References shark::BinaryTree< InputT >::mp_right.

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

◆ right() [2/2]

template<class InputT >

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

inline

"right" sub-node of the binary tree

Definition at line 202 of file BinaryTree.h.

References shark::BinaryTree< InputT >::mp_right.

◆ size()

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 206 of file BinaryTree.h.

References shark::BinaryTree< InputT >::m_size.

◆ splitList()

template<class InputT >

template<class Range1 , class Range2 >

Range2::iterator 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 315 of file BinaryTree.h.

References shark::BinaryTree< InputT >::m_threshold, and shark::partitionEqually().

Referenced by shark::KDTree< InputT >::buildTree(), and shark::LCTree< VectorType, CuttingAccuracy >::buildTree().

◆ squaredDistanceLowerBound()

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 >.

◆ threshold()

template<class InputT >

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

inline

Separation threshold.

Definition at line 238 of file BinaryTree.h.

References shark::BinaryTree< InputT >::m_threshold.

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

Member Data Documentation

◆ m_nodes

template<class InputT >

std::size_t shark::BinaryTree< InputT >::m_nodes

protected

number of nodes in the sub-tree represented by this node

Definition at line 361 of file BinaryTree.h.

Referenced by shark::BinaryTree< InputT >::nodes().

◆ m_size

template<class InputT >

std::size_t shark::BinaryTree< InputT >::m_size

protected

number of points in this node

Definition at line 358 of file BinaryTree.h.

Referenced by shark::BinaryTree< InputT >::BinaryTree(), and shark::BinaryTree< InputT >::size().

◆ m_threshold

template<class InputT >

double shark::BinaryTree< InputT >::m_threshold

protected

threshold for the separating function

Definition at line 364 of file BinaryTree.h.

Referenced by shark::BinaryTree< InputT >::distanceFromPlane(), shark::BinaryTree< InputT >::isLeft(), shark::BinaryTree< InputT >::isRight(), shark::BinaryTree< InputT >::splitList(), and shark::BinaryTree< InputT >::threshold().

◆ mep_parent

template<class InputT >

BinaryTree* shark::BinaryTree< InputT >::mep_parent

protected

parent node

Definition at line 346 of file BinaryTree.h.

Referenced by shark::BinaryTree< InputT >::parent(), shark::BinaryTree< InputT >::parent(), and shark::BinaryTree< InputT >::~BinaryTree().

◆ mp_indexList

template<class InputT >

std::size_t* shark::BinaryTree< InputT >::mp_indexList

protected

list of indices to points in the dataset

Definition at line 355 of file BinaryTree.h.

Referenced by shark::BinaryTree< InputT >::BinaryTree(), shark::BinaryTree< InputT >::index(), and shark::BinaryTree< InputT >::~BinaryTree().

◆ mp_left

template<class InputT >

BinaryTree* shark::BinaryTree< InputT >::mp_left

protected

"left" child node

Definition at line 349 of file BinaryTree.h.

Referenced by shark::BinaryTree< InputT >::hasChildren(), shark::BinaryTree< InputT >::isLeaf(), shark::BinaryTree< InputT >::left(), shark::BinaryTree< InputT >::left(), shark::KDTree< InputT >::upper(), and shark::BinaryTree< InputT >::~BinaryTree().

◆ mp_right

template<class InputT >

BinaryTree* shark::BinaryTree< InputT >::mp_right

protected

"right" child node

Definition at line 352 of file BinaryTree.h.

Referenced by shark::KDTree< InputT >::lower(), shark::BinaryTree< InputT >::right(), shark::BinaryTree< InputT >::right(), and shark::BinaryTree< InputT >::~BinaryTree().

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

include/shark/Models/Trees/BinaryTree.h

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ BinaryTree() [1/2]

◆ ~BinaryTree()

◆ BinaryTree() [2/2]

Member Function Documentation

◆ distanceFromPlane()

◆ funct()

◆ hasChildren()

◆ index()

◆ isLeaf()

◆ isLeft()

◆ isRight()

◆ kernel()

◆ left() [1/2]

◆ left() [2/2]

◆ nodes()

◆ parent() [1/2]

◆ parent() [2/2]

◆ right() [1/2]

◆ right() [2/2]

◆ size()

◆ splitList()

◆ squaredDistanceLowerBound()

◆ threshold()

Member Data Documentation

◆ m_nodes

◆ m_size

◆ m_threshold

◆ mep_parent

◆ mp_indexList

◆ mp_left

◆ mp_right