Повышение навязчивых/бинарных деревьев поиска

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

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

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

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

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

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


c++ boost tree voronoi avl-tree
person Kristian D'Amato    schedule 22.05.2013    source источник

Ответы (4)


arrow_upward
3
arrow_downward 

 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; });
 }

Выход

x: 0 x: 1 x: 2

Я заметил, что push_back/push_front не вызывает переупорядочивание дерева. Возможно, я пропустил это в документах.

person Steven Maitlall    schedule 22.05.2013
comment
Это не похоже. Вызов begin(), по-видимому, возвращает первый элемент, определенный функцией сравнения. - person Kristian D'Amato; 22.05.2013
comment
Спасибо за ваш ответ, но все же мне нужен верхний (корневой/заголовочный) узел, а не самый левый/самый правый узел. - person Kristian D'Amato; 23.05.2013

arrow_upward
1
arrow_downward

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

Кажется, что дерево AVL отлично справляется со своей задачей.

person Kristian D'Amato    schedule 29.05.2013

arrow_upward
0
arrow_downward

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

Во-первых, вам нужно написать обычные вещи для использования boost::intrusive, такие как хуки и т. д.

boost::intrusive::avltree<Object> avl;

Если вы хотите найти узел в любом boost::intrusive, вы должны использовать find(). Теперь для функции find() требуется перегруженный оператор (), который в основном проверяет, является ли $a>b$ или $b ‹ a$ (очень похоже на логический вывод 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
    }
person Adel Ahmadyan    schedule 16.08.2013

arrow_upward
0
arrow_downward

У древовидных контейнеров Boost.Intrusive есть член root(), который возвращает итератор к корневому узлу или end(), если корневого узла нет. Эти функции были совершены давно. Следующий коммит:

https://github.com/boostorg/intrusive/commit/6d38384e369697894bb71fb81132ad60c796c70>

документирует эти функции, поэтому теперь они являются официальными. Следующий код показывает, как его использовать:

#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;   
}
person igaztanaga    schedule 03.09.2016