VPF::B-Tree - Форум программистов

Domain

Дата 18.12.2011, 23:52 (ссылка)

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

Загрузка ...

Бывалый

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

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

Всем привет. Есть задача. Реализовать  в  виде  программы  заданный  набор  операций (принадлежность,  поиск,
объединение,  разность,  пересечение)  с  использованием  управляющей  структуры  данных – B-дерево
порядка k=4.

В Java есть TreeSet, а в си или с++ есть что-то подобное? Реализаций B-Tree в инете завались, а вот методов аналогичных  retainAll и removeAll я не видел.
Что посоветуете, может есть у кого готовая реализация.

bsa

Дата 19.12.2011, 00:18 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

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

обычно, std::set реализуется через черно-красное бинарное дерево. И там есть метод clear. А вот аналога retainAll нет. Придется писать самому.

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

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

Domain

Дата 19.12.2011, 09:35 (ссылка)

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

Загрузка ...

Бывалый

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

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

Это вообщем не радует. А идеи по retainAll есть ? Т.е. как его реализовать, алгоритм.

bsa

Дата 19.12.2011, 10:46 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

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

Domain, конечно. ничего сложного там нет. просто удаляешь все элементы, которые отсутствуют в другом контейнере. В чем проблема?
for, std::set::erase, std::set::count тебе в помощь.

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

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

Domain

Дата 21.12.2011, 01:05 (ссылка)

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

Загрузка ...

Бывалый

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

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

а как понять B-дерево порядка k=4 ?

bsa

Дата 21.12.2011, 11:48 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

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

Цитата(http://en.wikipedia.org/wiki/B-tree)

According to Knuth's definition, a B-tree of order m (the maximum number of children for each node) is a tree which satisfies the following properties:
Every node has at most m children.
Every node (except root) has at least m⁄2 children.
The root has at least two children if it is not a leaf node.
All leaves appear in the same level, and carry information.
A non-leaf node with k children contains k−1 keys.

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

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

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