spatial::loose_balancing Struct Reference

This policy triggers rebalancing for the node when the difference in weight between left or right is more than a half. More...

#include <spatial_relaxed_kdtree.hpp>

Public Member Functions
template<typename Rank >
bool	operator() (const Rank &, weight_type left, weight_type right) const
	Rebalancing predicate. More...

Detailed Description

This policy triggers rebalancing for the node when the difference in weight between left or right is more than a half.

The default policy for rebalancing.

In effect, this policy leaves the tree roughly balanced: the path from the root to the furthest leaf is no more than twice as long as the path from the root to the nearest leaf.

This policy is adequate in many cases cause it prevents worse-case insertion or deletion time, and worst-case run-time on many search algorithms, and does not require a large amount of rebalancing.

Definition at line 60 of file spatial_relaxed_kdtree.hpp.

Member Function Documentation

template<typename Rank >

bool spatial::loose_balancing::operator()	(	const Rank &	,
		weight_type	left,
		weight_type	right
	)		const

Rebalancing predicate.

Parameters

left	The weight at the left
right	The weight at the right

Returns

true indicate that reblancing must occurs, otherwise false.

Definition at line 70 of file spatial_relaxed_kdtree.hpp.

---

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

• /home/sylvain/Projects/spatial_build/spatial_2.1.8/src/bits/spatial_relaxed_kdtree.hpp