Oberon space

General Category => Общий раздел => Тема начата: ilovb от Ноябрь 11, 2013, 01:07:12 pm

Название: Вставка в красно-чёрное дерево
Отправлено: ilovb от Ноябрь 11, 2013, 01:07:12 pm: Возможно глупый вопрос. При вставке, если данный ключ уже имеется в дереве, то как правильно обрабатывать эту ситуацию?
1. Вставлять
2. Ничего не делать
3. Сгенерить исключение

Смотрел две реализации. В одной вставляют, в другой ничего не делают. Какое поведение правильное?
Название: Re: Вставка в красно-чёрное дерево
Отправлено: valexey_u от Ноябрь 11, 2013, 01:25:24 pm: Цитата: ilovb от Ноябрь 11, 2013, 01:07:12 pm
Возможно глупый вопрос. При вставке, если данный ключ уже имеется в дереве, то как правильно обрабатывать эту ситуацию?
1. Вставлять
2. Ничего не делать
3. Сгенерить исключение

Смотрел две реализации. В одной вставляют, в другой ничего не делают. Какое поведение правильное?
Заменить значение для этого ключа.
Название: Re: Вставка в красно-чёрное дерево
Отправлено: ilovb от Ноябрь 11, 2013, 01:33:35 pm: Да, вроде логично.
А тут косяк получается?:
Код: [Выделить]
if (compEQ(data, current->data)) return (current);http://algolist.manual.ru/ds/rbtree.php
Название: Re: Вставка в красно-чёрное дерево
Отправлено: ilovb от Ноябрь 11, 2013, 01:40:53 pm: Вообще, я правильно понимаю, что поведение должно быть 1:1 как у map?
Название: Re: Вставка в красно-чёрное дерево
Отправлено: valexey_u от Ноябрь 11, 2013, 01:53:30 pm: Цитата: ilovb от Ноябрь 11, 2013, 01:40:53 pm
Вообще, я правильно понимаю, что поведение должно быть 1:1 как у map?
Как у плюсатого std::map, да. Ибо это и есть то самое дерево скорее всего.
Название: Re: Вставка в красно-чёрное дерево
Отправлено: Geniepro от Ноябрь 11, 2013, 02:02:07 pm: Цитата: valexey_u от Ноябрь 11, 2013, 01:25:24 pm
Цитата: ilovb от Ноябрь 11, 2013, 01:07:12 pm
Возможно глупый вопрос. При вставке, если данный ключ уже имеется в дереве, то как правильно обрабатывать эту ситуацию?
1. Вставлять
2. Ничего не делать
3. Сгенерить исключение

Смотрел две реализации. В одной вставляют, в другой ничего не делают. Какое поведение правильное?

Заменить значение для этого ключа.

Не совсем понял. Получится два разных значения для одного ключа или второе значение перезапишет первоначальное?
Название: Re: Вставка в красно-чёрное дерево
Отправлено: valexey_u от Ноябрь 11, 2013, 02:04:06 pm: Цитата: Geniepro от Ноябрь 11, 2013, 02:02:07 pm
Цитата: valexey_u от Ноябрь 11, 2013, 01:25:24 pm
Цитата: ilovb от Ноябрь 11, 2013, 01:07:12 pm
Возможно глупый вопрос. При вставке, если данный ключ уже имеется в дереве, то как правильно обрабатывать эту ситуацию?
1. Вставлять
2. Ничего не делать
3. Сгенерить исключение

Смотрел две реализации. В одной вставляют, в другой ничего не делают. Какое поведение правильное?

Заменить значение для этого ключа.

Не совсем понял. Получится два разных значения для одного ключа или второе значение перезапишет первоначальное?
Перезапишет. Иначе это уже не map, a multimap.
Название: Re: Вставка в красно-чёрное дерево
Отправлено: ilovb от Ноябрь 11, 2013, 02:36:52 pm: Кажись понял. В этой сишной реализации ключ выступает и в качестве значения. А в этом случае действительно ничего не надо делать.