A scapegoat tree is a selfbalancing binary search tree, that provides worstcase O(log n) lookup time, and O(log n) amortized insertion and deletion time. Unlike other selfbalancing binary search trees that provide worst case O(log n) lookup time, scapegoat trees have no additional pernode 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 aheightbalanced tree is defined with defined with the following equation: height(tree) <= log1/a(tree.size())
Scapegoat trees are loosely aheightbalanced 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. Scapegoattrees implemented in Boost.Intrusive offer the possibility of changing a at runtime taking advantage of the flexibility of scapegoat trees. For more information on scapegoat trees see Wikipedia entry. Scapegoat trees also have downsides:
Boost.Intrusive offers 3 containers based
on scapegoat trees: The memory overhead of these containers with Boost.Intrusive hooks is 3 pointers.
An empty,
template <class ...Options> class bs_set_base_hook;
template <class ...Options> class bs_set_member_hook;
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:
And they also can receive additional options:
Now let's see a small example using both hooks and
#include <boost/intrusive/sg_set.hpp> #include <vector> #include <algorithm> #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; typedef std::vector<MyClass>::reverse_iterator VectRit; //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()), rbitend(baseset.rend()); MemberMultiset::iterator mit(membermultiset.begin()), mitend(membermultiset.end()); 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; }
