Увеличить интрузивные / бинарные деревья поиска

Я ищу бинарное дерево поиска для алгоритма тесселяции Вороного (алгоритм Фортуны; чертовски нетривиальная задача сама по себе, метинкс), так что, конечно, я решил взглянуть на Boost.

Повышение имеет Intrusive заголовочный файл, который, кажется, содержит множество BST-файлов (таких как AVL, Splay-деревья и деревья козла отпущения — ха, я должен был убедиться в этом имени!) и на первый взгляд выглядел как раз то, что мне было нужно.

1: Я что-то упустил или нет прямого доступа к корневому узлу дерева?

2: Подходит ли дерево AVL для структуры береговой линии алгоритма Fortune?

Черт, я думал, что это будет легко.

Обновить: Возможно, лучше заявить, чего я хочу достичь: я бы хотел реализовать поиск по параболе, который является частью алгоритма Fortune, той частью, где обнаруживается новый сайт, и нам нужно найти параболу непосредственно над головой. Я думал, что пройду дерево, начиная с корня, чтобы найти правильную дугу.

3

Решение

 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 не вызывает переупорядочение дерева. Возможно, я пропустил это в документах.

3

Другие решения

В конце концов я реализовал свое собственное дерево AVL. Сложность алгоритма Вороного, казалось, требовала этого, и версия Boost не имела доступа к узлам, во всяком случае (если я ошибаюсь, пожалуйста, укажите на это; это возможно, учитывая незаметность Boost).

Дерево AVL, кажется, делает работу отлично.

1

На самом деле поиск корня проще, чем кажется.

Во-первых, вы должны написать обычные вещи для использования 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
}
0

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;
}
0
По вопросам рекламы [email protected]