Увеличить интрузивные / бинарные деревья поиска
Я ищу бинарное дерево поиска для алгоритма тесселяции Вороного (алгоритм Фортуны; чертовски нетривиальная задача сама по себе, метинкс), так что, конечно, я решил взглянуть на Boost.
Повышение имеет Intrusive заголовочный файл, который, кажется, содержит множество BST-файлов (таких как AVL, Splay-деревья и деревья козла отпущения — ха, я должен был убедиться в этом имени!) и на первый взгляд выглядел как раз то, что мне было нужно.
1: Я что-то упустил или нет прямого доступа к корневому узлу дерева?
2: Подходит ли дерево AVL для структуры береговой линии алгоритма Fortune?
Черт, я думал, что это будет легко.
Обновить: Возможно, лучше заявить, чего я хочу достичь: я бы хотел реализовать поиск по параболе, который является частью алгоритма Fortune, той частью, где обнаруживается новый сайт, и нам нужно найти параболу непосредственно над головой. Я думал, что пройду дерево, начиная с корня, чтобы найти правильную дугу.
Решение
iterator begin();
const_iterator begin() const;
const_iterator cbegin() const;
Это немного неясно, основываясь на документации, но похоже, что begin () вернет первый узел заголовка (он же корневой узел).
http://www.dcs.gla.ac.uk/~samm/trees.html
Обновить
#include <iostream>
#include <algorithm>
#include <boost/intrusive/rbtree.hpp>
using namespace boost::intrusive;
struct X : public set_base_hook<optimize_size<true> > {
X(int x) : _x{x} { }
int _x;
friend inline std::ostream& operator<<(std::ostream&, const X&);
friend bool operator<(const X&, const X&);
friend bool operator>(const X&, const X&);
friend bool operator==(const X&, const X&);
};
std::ostream& operator<<( std::ostream& os, const X& x) {
os << x._x;
return os;
}
bool operator<(const X& lhs, const X& rhs) { return lhs._x < rhs._x; }
bool operator>(const X& lhs, const X& rhs) { return lhs._x > rhs._x; }
bool operator==(const X& lhs, const X& rhs) { return lhs._x == rhs._x; }
int main()
{
typedef rbtree<X> tree_t;
tree_t tree;
X x0(0);
X x1(1);
X x2(2);
/*! Output is the same for the following
* X x1(1);
* X x0(0);
* X x2(2);
*/
tree.insert_unique(x1);
tree.insert_unique(x0);
tree.insert_unique(x2);
std::for_each(
tree.begin(), tree.end(),
[](const X& xx) { std::cout << "x: " << xx << std::endl; });
}
Выход
х: 0
х: 1
х: 2
Я заметил, что push_back / push_front не вызывает переупорядочение дерева. Возможно, я пропустил это в документах.
Другие решения
В конце концов я реализовал свое собственное дерево AVL. Сложность алгоритма Вороного, казалось, требовала этого, и версия Boost не имела доступа к узлам, во всяком случае (если я ошибаюсь, пожалуйста, укажите на это; это возможно, учитывая незаметность Boost).
Дерево AVL, кажется, делает работу отлично.
На самом деле поиск корня проще, чем кажется.
Во-первых, вы должны написать обычные вещи для использования boost :: intrusive типа hooks и т. Д.
boost::intrusive::avltree<Object> avl;
Если вы хотите искать узел в любом boost :: intrusive, вы должны использовать find ().
Теперь функция find () требует оператора overloaded (), который в основном проверяет, являются ли $ a> b $ или $ b < $ (очень похоже на логический вывод strcmp), Вы хотите, чтобы этот оператор потерпел неудачу в корневом узле поэтому он вернет рут в качестве результата. Один из способов сделать это будет
class RootComp{
bool operator () (const Object &a, const int b) const {
return false;
}
bool operator () (int b, const Object &a) const{
return false;
}
};
Тогда использовать find () просто:
int data=0;
boost::intrusive::avltree<Object>::iterator it = avl.find(data, RootComp());
if( it != avl.end() ){
//*it is the root
}else{
// the tree is empty
}
Boost.Intrusive древовидные контейнеры имеют элемент root (), который возвращает итератор в корневой узел или end (), если корневого узла нет. Эти функции были совершены давно. Следующий коммит:
https://github.com/boostorg/intrusive/commit/6d38384e369697894bb71fb81132ad60b796c70c
документирует эти функции, поэтому теперь они официальные. Следующий код показывает, как его использовать:
#include <boost/intrusive/set.hpp>
#include <cassert>
using namespace boost::intrusive;
struct MyClass : public set_base_hook<>
{
friend bool operator<(const MyClass&, const MyClass&)
{ return true; }
};
int main()
{
set<MyClass> set;
//end() is returned when the tree is empty
assert(set.root() == set.end() );
//insert myobject, must be root
MyClass myobject;
set.insert(myobject);
assert(&*set.root() == &myobject);
//erase and check root is again end()
set.erase(set.root());
assert(set.croot() == set.cend());
return 0;
}