Форум программистов, компьютерный форум CyberForum.ru

Дерево поиска. добавление элемента - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.73
PointsEqual
ниначмуроФ
 Аватар для PointsEqual
832 / 516 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
23.03.2011, 11:32     Дерево поиска. добавление элемента #1
Привет. Поясните кое что с деревом.
Допустим есть класс
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class bst
{
    public:
        bst(): root(NULL) {}
        virtual ~bst() {}
 
        void insert(binaryNode*& , size_t);
        void inorder(binaryNode*);
        binaryNode* getRoot(){  return root; }
 
    protected:
        node* root;
    private:
};

и операция добавления элемента в дерево
C++
1
2
3
4
5
6
7
8
9
10
void bst::insert(binaryNode*& r , size_t key){
    if ( r == NULL ){
         r = new binaryNode(key);
        return;
    }
    else if (key < r -> key)
        insert(r ->left, key);
    else if (key > r -> key)
        insert(r -> right, key);
}
В функцию передается по ссылке указатель на корень дерева(root), но после, например, 5 операций insert, root ведь будет указывать не на вершину дерева а на последний вставленный элемент.
И тогда getRoot() тоже будет возвращать указатель не на вершину дерева а на последний вставленный элемент.
А мне хотелось бы чтобы root всегда указывал на вершину.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.03.2011, 11:32     Дерево поиска. добавление элемента
Посмотрите здесь:

дерево поиска C++
C++ Дерево бинарного поиска
Бинарное дерево поиска C++
C++ Дерево двоичного поиска
Бинарное дерево поиска (удаление, добавление элемента) C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
23.03.2011, 13:07     Дерево поиска. добавление элемента #2
Мне не видно, чтобы insert изменял root.

Добавлено через 1 минуту
В корректной реализации, вставка элемента реализуется через бинарный поиск.

Добавлено через 21 секунду
*от корня.

Добавлено через 16 секунд
*с последующей перестройкой дерева.)
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
23.03.2011, 13:12     Дерево поиска. добавление элемента #3
Цитата Сообщение от Deviaphan Посмотреть сообщение
В корректной реализации, вставка элемента реализуется через бинарный поиск.
Чем, интересно, рекурсивная реализация некорректна?
Цитата Сообщение от Deviaphan Посмотреть сообщение
с последующей перестройкой дерева
Опять непонятно, зачем перестраивать дерево после вставки элемента для несбалансированных деревьев?

Цитата Сообщение от PointsEqual Посмотреть сообщение
А мне хотелось бы чтобы root всегда указывал на вершину.
Так и есть.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
23.03.2011, 13:19     Дерево поиска. добавление элемента #4
Цитата Сообщение от fasked Посмотреть сообщение
Чем, интересно, рекурсивная реализация некорректна?
Моей невнимательностью.(
PointsEqual
ниначмуроФ
 Аватар для PointsEqual
832 / 516 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
23.03.2011, 14:10  [ТС]     Дерево поиска. добавление элемента #5
fasked,

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    int main()
{
    bst klen;
 
    binaryNode* p_root = klen.getRoot();
    klen.insert(p_root, 8 );
    klen.insert(p_root, 6 );
   // p_root = klen.getRoot();
    klen.insert(p_root, 12 );
 
 
    klen.inorder(p_root);
 
  return 0;
}
если я расскоментирую строку, то inorder выведет только последнее добавленное число(12), следовательно root указывает не на вершину все таки

Добавлено через 7 минут
Цитата Сообщение от Deviaphan Посмотреть сообщение
Мне не видно, чтобы insert изменял root.
insert изменяет не совсем root, а указатель на root
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
23.03.2011, 14:14     Дерево поиска. добавление элемента #6
А должен изменять левый или правй узел в руте.
Yandex
Объявления
23.03.2011, 14:14     Дерево поиска. добавление элемента
Ответ Создать тему
Опции темы

Текущее время: 19:52. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru