VPF::binary tree - Форум программистов

comp

Дата 17.11.2006, 15:18 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 61
Регистрация: 15.11.2006

Репутация: нет
Всего: 1

Код


class tree
{
 private:

 class vertex
 {
  private:
  
  int data;
  vertex *left, *right;

  public:
 
  vertex(int x) : data(x), left(NULL), right(NULL) {}
 
  void insert(int x, vertex **p)
  {
   if (!*p)
      {
       *p = new vertex(x);
       return;
      }
 
   if (data < x) this->right->insert(x, &right);
   if (data > x) this->left->insert(x, &left);
  }

  void pass_vertex()
  {  
   if (!this) return;

   this->left->pass_vertex();
   printf("%d ", this->data);
   this->right->pass_vertex();
  }
 
 };

 vertex *root; 

 public: 

 tree() : root(NULL) {}

 void insert(int x)
 {
  root->insert(x, &root);
 }

 void pass()
 {
  root->pass_vertex();
 }
};

albertn

Дата 17.11.2006, 15:58 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 368
Регистрация: 17.7.2006
Где: г. Ставрополь

Репутация: нет
Всего: 34

Данную реализацию трудно назвать бинарным деревом, т.к. что будет если в него загонять в цикле отсортированные числа? То будет повторяться сортировка методом вставки, причем без бинарного поиска, а полным перебором
Почему-то я ненашел в программе ниодной строчки освобождения памяти. new есть, а delete нет. А если нет сборщика мусора?
Я конечно не могу точно утвердать как принято во всем обществе, но имхо выделение памяти указателю-аргументу это неправильно
Конструкция if (!this) return; меня честно говоря пугает. Нельзя вызывать методы несозданного объекта.
А зачем собсно изобретать велосипед? В STL есть замечательные библиотеки, которые без труда реализуют все необходимое.

zabivator

Дата 17.11.2006, 16:04 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 171
Регистрация: 7.6.2006
Где: нск

Репутация: 1
Всего: 2

comp, как минимум, распределитель памяти должен быть стратегией - аргументом шаблона.

--------------------

#include <zabivator>int main( int, char * [] ){ while( Zabivator::жив() ) Zabivator::моск()++; return 0;}

JackYF

Дата 17.11.2006, 16:12 (ссылка)

(нет голосов)

Загрузка ...

полуавантюрист

Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

Репутация: 18
Всего: 162

pass() и pass_vertex() объяви константными, так как они не изменяют полей класса...

А вообще в принципе такого рода структуры шаблонными делать надо в будущем... smile

Добавлено @ 16:14
zabivator, распределитель памяти? В таком классе?
Даже при использовании STL ты много раз менял стандартный распределитель памяти?

--------------------

Пожаловаться на меня как модератора можно здесь.

zabivator

Дата 17.11.2006, 18:26 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 171
Регистрация: 7.6.2006
Где: нск

Репутация: 1
Всего: 2

JackYF, В этот кокретный класс не вникал, но для подобных классов всегда надо указывать стратегию. А менять распределитель stl'я не так уж и редко, чтобы не вспоминать о нем.

--------------------

#include <zabivator>int main( int, char * [] ){ while( Zabivator::жив() ) Zabivator::моск()++; return 0;}

JackYF

Дата 17.11.2006, 18:30 (ссылка)

(нет голосов)

Загрузка ...

полуавантюрист

Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

Репутация: 18
Всего: 162

zabivator, в таком случае поздравляю... Сам ни разу ни пользовался и не видел примером применения.
Если есть достойный - ткни ссылкой...

--------------------

Пожаловаться на меня как модератора можно здесь.

zabivator

Дата 17.11.2006, 18:32 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 171
Регистрация: 7.6.2006
Где: нск

Репутация: 1
Всего: 2

Код


std::vector<SomeClass*>

Код


std::vector<SomeClass*,boost::memory_pool>

Когда экземпляров класса несколько тысяч, быстродействие начинает отличаться раз в шесть-семь

Это сообщение отредактировал(а) zabivator - 17.11.2006, 18:32

--------------------

#include <zabivator>int main( int, char * [] ){ while( Zabivator::жив() ) Zabivator::моск()++; return 0;}

JackYF

Дата 17.11.2006, 18:55 (ссылка)

(нет голосов)

Загрузка ...

полуавантюрист

Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

Репутация: 18
Всего: 162

zabivator, ясно.
Я просто boost не юзаю пока, неоткуда memory_pool брать smile

--------------------

Пожаловаться на меня как модератора можно здесь.

zabivator

Дата 17.11.2006, 19:14 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 171
Регистрация: 7.6.2006
Где: нск

Репутация: 1
Всего: 2

JackYF, свой написать? Модно еще из Loki дернуть =)

--------------------

#include <zabivator>int main( int, char * [] ){ while( Zabivator::жив() ) Zabivator::моск()++; return 0;}

JackYF

Дата 17.11.2006, 19:26 (ссылка)

(нет голосов)

Загрузка ...

полуавантюрист

Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

Репутация: 18
Всего: 162

Цитата(zabivator @ 17.11.2006, 19:14

)

JackYF, свой написать? Модно еще из Loki дернуть =)

Обязательно! Как только руки дойдут smile

А будет это где-то к зиме smile

--------------------

Пожаловаться на меня как модератора можно здесь.

comp

Дата 17.11.2006, 21:35 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 61
Регистрация: 15.11.2006

Репутация: нет
Всего: 1

Цитата

[*]Данную реализацию трудно назвать бинарным деревом, т.к. что будет если в него загонять в цикле отсортированные числа? То будет повторяться сортировка методом вставки, причем без бинарного поиска, а полным перебором

Чем не бинарное, логики построения деревьев не противоречит. А если будем вставлять уже упорядоченные числа, то будет простой список(Вот для этого уже и существуют всевозможные авл, красно-черные и много-много всяких деревьев).

Цитата

[*]Почему-то я ненашел в программе ниодной строчки освобождения памяти. new есть, а delete нет. А если нет сборщика мусора?

Да, мой косяк. Как-то на этом внимание не заострял, т.к. для других целей писал дерево.

Цитата

[*]Я конечно не могу точно утвердать как принято во всем обществе, но имхо выделение памяти указателю-аргументу это неправильно

Вот, собственно для этого я и засабмитил сюда код, чтобы покритиковали. Просто я не знаю, как по другому добавлять вершины. Как правильнее, точнее, добавлять, чтобы код был красивый и без изъянов.

Цитата

[*]Конструкция if (!this) return; меня честно говоря пугает. Нельзя вызывать методы несозданного объекта.
[*]А зачем собсно изобретать велосипед? В STL есть замечательные библиотеки, которые без труда реализуют все необходимое.

С классами хочу поработать

albertn

Дата 18.11.2006, 15:20 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 368
Регистрация: 17.7.2006
Где: г. Ставрополь

Репутация: нет
Всего: 34

Цитата(comp @ 17.11.2006, 21:35

)

Вообще бинарное дерево предполагает равномерное распределение ветвей.
А чем тогда этот дерево будет лучше того-же отсортированного list или даже set, ведь эти методы гораздо быстрее, функциональней, и эффективнее.
И единственный случай, когда хоть какой-то толк будет - когда все числа будут равномерно разбросаны. Во всех остальных ситуациях не имеет практического смысла.

comp

Дата 18.11.2006, 16:39 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 61
Регистрация: 15.11.2006

Репутация: нет
Всего: 1

Цитата

Вообще бинарное дерево предполагает равномерное распределение ветвей.
А чем тогда этот дерево будет лучше того-же отсортированного list или даже set, ведь эти методы гораздо быстрее, функциональней, и эффективнее.
И единственный случай, когда хоть какой-то толк будет - когда все числа будут равномерно разбросаны. Во всех остальных ситуациях не имеет практического смысла.

Бррр... кто-то читать не умеет... я кажеться упоминул про существование сбалансированных деревьев(соответственно, можно сделать вывод, что я достаточно отчётливо представляю, что это за структуры, какие у них свойства, какова сложность). Да, и бинарное дерево ничего не преполагает! Также упоминул про то, зачем я это написал, а также, зачем я это сюда засабмитил.
Хотелось бы более конструктивной критики услышать!
PS. Быть может кто-нибудь сюда засабмитит свою реализацию двоичного дерева(самого тривиального, без всевозможны балансировок). Меня, в большей степени интересует, как реализованна вставка элемента в дерево.

andrew_

Дата 20.11.2006, 09:01 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 22
Регистрация: 26.10.2006

Репутация: нет
Всего: нет

Вот интерфейс класса и реализация функции insert

Код


class Tree
{
private:
    int num_node;
    typedef Node* link;
    void insert(link& n,int info);
    void insert(link& n,link& subn);
    bool del(link& n,int info);
    void insertT_(link& h, int info);
    
public:
    link head;
    Tree():num_node(0),head(0){};
    void insert(int info);
    bool del(int info);
    void free_mem(link& h);
    ~Tree();
    void insert_(int item);
};    

void Tree::insert(link& n,int info)
{
    if(!n){ 
        n=new Node(info);
        n->count=num_node;
        n->left=NULL;
        n->right=NULL;
        ++num_node;
        return;
    }
    if(info>n->info){
        insert(n->right,info);
    }
    else insert(n->left,info);

}

void Tree::insert_(int item) 
{ 
    insertT_(head, item); 
}

Это сообщение отредактировал(а) andrew_ - 20.11.2006, 09:05

comp

Дата 20.11.2006, 13:38 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 61
Регистрация: 15.11.2006

Репутация: нет
Всего: 1

Ну, собственно, тоже самое, что и у меня...

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »