Super class of binary space-partitioning trees. More...
#include <shark/Models/Trees/BinaryTree.h>
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 > | |
Range2::iterator | 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... | |
Super class of binary space-partitioning trees.
Definition at line 128 of file BinaryTree.h.
|
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 138 of file BinaryTree.h.
|
inlinevirtual |
Destroy the tree and its internal data structures.
Definition at line 155 of file BinaryTree.h.
|
inlineprotected |
|
inline |
Function describing the separation of space.
Definition at line 224 of file BinaryTree.h.
Referenced by shark::LCTree< VectorType, CuttingAccuracy >::squaredDistanceLowerBound().
|
protectedpure virtual |
Function describing the separation of space.
Implemented in shark::KDTree< InputT >.
|
inline |
Does this node have children? Opposite of isLeaf()
Definition at line 174 of file BinaryTree.h.
Referenced by shark::HierarchicalClustering< InputT >::hardMembership(), shark::IterativeNNQuery< DataContainer >::IterativeNNQuery(), and shark::IterativeNNQuery< DataContainer >::queuesize().
|
inline |
Definition at line 204 of file BinaryTree.h.
Referenced by shark::KDTree< InputT >::squaredDistanceLowerBound().
|
inline |
Is this a leaf node? Opposite of hasChildren()
Definition at line 179 of file BinaryTree.h.
Referenced by shark::KDTree< InputT >::squaredDistanceLowerBound().
|
inline |
return true if the reference point belongs to the "left" sub-node, or to the "negative" sub-cell.
Definition at line 235 of file BinaryTree.h.
Referenced by shark::HierarchicalClustering< InputT >::hardMembership(), and shark::IterativeNNQuery< DataContainer >::IterativeNNQuery().
|
inline |
return true if the reference point belongs to the "right" sub-node, or to the "positive" sub-cell.
Definition at line 240 of file BinaryTree.h.
|
inlinevirtual |
If the tree uses a kernel metric, returns a pointer to the kernel object, else NULL.
Definition at line 244 of file BinaryTree.h.
|
inline |
"left" sub-node of the binary tree
Definition at line 183 of file BinaryTree.h.
Referenced by shark::IterativeNNQuery< DataContainer >::IterativeNNQuery(), and shark::IterativeNNQuery< DataContainer >::queuesize().
|
inline |
"left" sub-node of the binary tree
Definition at line 186 of file BinaryTree.h.
|
inline |
number of sub-nodes in this tree (including the node itself)
Definition at line 201 of file BinaryTree.h.
Referenced by shark::HierarchicalClustering< InputT >::numberOfClusters().
|
inline |
parent node
Definition at line 166 of file BinaryTree.h.
Referenced by shark::KDTree< InputT >::lower(), and shark::KDTree< InputT >::upper().
|
inline |
parent node
Definition at line 169 of file BinaryTree.h.
|
inline |
"right" sub-node of the binary tree
Definition at line 190 of file BinaryTree.h.
Referenced by shark::IterativeNNQuery< DataContainer >::IterativeNNQuery(), and shark::IterativeNNQuery< DataContainer >::queuesize().
|
inline |
"right" sub-node of the binary tree
Definition at line 193 of file BinaryTree.h.
|
inline |
number of points inside the space represented by this node
Definition at line 197 of file BinaryTree.h.
Referenced by shark::KDTree< InputT >::squaredDistanceLowerBound().
|
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
values | the value of every point returned by funct(point) |
points | the points themselves |
Definition at line 306 of file BinaryTree.h.
|
pure virtual |
Compute lower bound on the squared distance to the space cell.
Implemented in shark::KDTree< InputT >.
Referenced by shark::IterativeNNQuery< DataContainer >::queuesize().
|
inline |
Separation threshold.
Definition at line 229 of file BinaryTree.h.
Referenced by shark::KDTree< InputT >::lower(), shark::KDTree< InputT >::squaredDistanceLowerBound(), and shark::KDTree< InputT >::upper().
|
protected |
number of nodes in the sub-tree represented by this node
Definition at line 352 of file BinaryTree.h.
Referenced by shark::KDTree< InputT >::buildTree(), shark::KHCTree< Container, CuttingAccuracy >::squaredDistanceLowerBound(), and shark::KDTree< InputT >::squaredDistanceLowerBound().
|
protected |
number of points in this node
Definition at line 349 of file BinaryTree.h.
Referenced by shark::KDTree< InputT >::buildTree(), shark::KDTree< InputT >::calculateCuttingDimension(), shark::KDTree< InputT >::KDTree(), shark::KHCTree< Container, CuttingAccuracy >::squaredDistanceLowerBound(), and shark::KDTree< InputT >::squaredDistanceLowerBound().
|
protected |
threshold for the separating function
Definition at line 355 of file BinaryTree.h.
|
protected |
parent node
Definition at line 337 of file BinaryTree.h.
Referenced by shark::KDTree< InputT >::lower(), shark::KHCTree< Container, CuttingAccuracy >::squaredDistanceLowerBound(), shark::LCTree< VectorType, CuttingAccuracy >::squaredDistanceLowerBound(), shark::KDTree< InputT >::squaredDistanceLowerBound(), and shark::KDTree< InputT >::upper().
|
protected |
list of indices to points in the dataset
Definition at line 346 of file BinaryTree.h.
Referenced by shark::KDTree< InputT >::KDTree(), shark::KHCTree< Container, CuttingAccuracy >::squaredDistanceLowerBound(), and shark::KDTree< InputT >::squaredDistanceLowerBound().
|
protected |
"left" child node
Definition at line 340 of file BinaryTree.h.
Referenced by shark::KHCTree< Container, CuttingAccuracy >::squaredDistanceLowerBound(), shark::KDTree< InputT >::squaredDistanceLowerBound(), and shark::KDTree< InputT >::upper().
|
protected |
"right" child node
Definition at line 343 of file BinaryTree.h.
Referenced by shark::KDTree< InputT >::lower(), shark::KHCTree< Container, CuttingAccuracy >::squaredDistanceLowerBound(), shark::LCTree< VectorType, CuttingAccuracy >::squaredDistanceLowerBound(), and shark::KDTree< InputT >::squaredDistanceLowerBound().