|
Home | Libraries | People | FAQ | More |
A scapegoat tree is a self-balancing binary search tree, that provides worst-case O(log n) lookup time, and O(log n) amortized insertion and deletion time. Unlike other self-balancing binary search trees that provide worst case O(log n) lookup time, scapegoat trees have no additional per-node overhead compared to a regular binary search tree.
A binary search tree is said to be weight balanced if half the nodes are on the left of the root, and half on the right. An a-height-balanced tree is defined with defined with the following equation:
height(tree) <= log1/a(tree.size())
Scapegoat trees are loosely a-height-balanced so:
height(tree) <= log1/a(tree.size()) + 1
Scapegoat trees support any a between 0.5 and 1. If a is higher, the tree is rebalanced less often, obtaining quicker insertions but slower searches. Lower a values improve search times. Scapegoat-trees implemented in Boost.Intrusive offer the possibility of changing a at run-time taking advantage of the flexibility of scapegoat trees. For more information on scapegoat trees see Wikipedia entry.
Scapegoat trees also have downsides:
auto_unlink hooks.
The size of an empty scapegoat tree is also considerably increased.
Boost.Intrusive offers 3 containers based
on scapegoat trees: sg_set,
sg_multiset and
sgtree. The first two
are similar to set or multiset and the latter is a generalization
that offers functions both to insert unique and multiple keys.
The memory overhead of these containers with Boost.Intrusive hooks is 3 pointers.
An empty, sg_set, sg_multiset or sgtree
has also the size of 3 pointers, two integers and two floating point values
(equivalent to the size of 7 pointers on most systems).
Boost.Intrusive scapegoat associative containers don't use their own hook types but plain Binary search tree hooks. See Binary search tree hooks: bs_set_base_hook and bs_set_member_hook section for more information about these hooks.
template <class T, class ...Options> class sg_set; template <class T, class ...Options> class sg_multiset; template <class T, class ...Options> class sgtree;
These containers receive the same options explained in the section How to use Boost.Intrusive:
base_hook<class Hook>
/ member_hook<class T, class Hook, Hook T::* PtrToMember>
/ value_traits<class ValueTraits>:
To specify the hook type or value traits used to configure the container.
(To learn about value traits go to the section Containers
with custom ValueTraits.)
size_type<typename
SizeType>:
To specify the type that will be used to store the size of the container.
Default: size_type<std::size_t>
And they also can receive additional options:
compare<class Compare>:
Comparison function for the objects to be inserted in containers. The
comparison functor must induce a strict weak ordering. Default: compare<
std::less<key_type>
>
floating_point<bool Enable>:
When this option is deactivated, the scapegoat tree loses the ability
to change the balance factor a at run-time, but the size of an empty
container is reduced and no floating point operations are performed,
normally increasing container performance. The fixed a factor that is
used when this option is activated is 1/sqrt(2) ~ 0,70711.
Default: floating_point<true>
key_of_value<class KeyOfValueFunctionObject>:
A function object that will define the key_type
of the value type to be stored. This type will allow a map-like interface.
See Map and multimap-like interface
with set and multiset for details. Default: key_type
is equal to value_type
(set-like interface).
Now let's see a small example using binary search tree hooks and sg_set/ sg_multiset
containers:
#include <boost/intrusive/sg_set.hpp> #include <vector> #include <functional> #include <cassert> using namespace boost::intrusive; class MyClass : public bs_set_base_hook<> { int int_; public: //This is a member hook bs_set_member_hook<> member_hook_; MyClass(int i) : int_(i) {} friend bool operator< (const MyClass &a, const MyClass &b) { return a.int_ < b.int_; } friend bool operator> (const MyClass &a, const MyClass &b) { return a.int_ > b.int_; } friend bool operator== (const MyClass &a, const MyClass &b) { return a.int_ == b.int_; } }; //Define an sg_set using the base hook that will store values in reverse order //and won't execute floating point operations. typedef sg_set < MyClass, compare<std::greater<MyClass> >, floating_point<false> > BaseSet; //Define an multiset using the member hook typedef member_hook<MyClass, bs_set_member_hook<>, &MyClass::member_hook_> MemberOption; typedef sg_multiset< MyClass, MemberOption> MemberMultiset; int main() { typedef std::vector<MyClass>::iterator VectIt; //Create several MyClass objects, each one with a different value std::vector<MyClass> values; for(int i = 0; i < 100; ++i) values.push_back(MyClass(i)); BaseSet baseset; MemberMultiset membermultiset; //Now insert them in the reverse order in the base hook sg_set for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it){ baseset.insert(*it); membermultiset.insert(*it); } //Change balance factor membermultiset.balance_factor(0.9f); //Now test sg_sets { BaseSet::reverse_iterator rbit(baseset.rbegin()); MemberMultiset::iterator mit(membermultiset.begin()); VectIt it(values.begin()), itend(values.end()); //Test the objects inserted in the base hook sg_set for(; it != itend; ++it, ++rbit) if(&*rbit != &*it) return 1; //Test the objects inserted in the member hook sg_set for(it = values.begin(); it != itend; ++it, ++mit) if(&*mit != &*it) return 1; } return 0; }