Вставка в красно-чёрное дерево

[ilovb]

Возможно глупый вопрос. При вставке, если данный ключ уже имеется в дереве, то как правильно обрабатывать эту ситуацию?
1. Вставлять
2. Ничего не делать
3. Сгенерить исключение

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

[valexey_u]

Возможно глупый вопрос. При вставке, если данный ключ уже имеется в дереве, то как правильно обрабатывать эту ситуацию?
1. Вставлять
2. Ничего не делать
3. Сгенерить исключение

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

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

[ilovb]

Да, вроде логично.
А тут косяк получается?:

Код: [Выделить]

if (compEQ(data, current->data)) return (current);http://algolist.manual.ru/ds/rbtree.php

[ilovb]

Вообще, я правильно понимаю, что поведение должно быть 1:1 как у map?

[valexey_u]

Вообще, я правильно понимаю, что поведение должно быть 1:1 как у map?

Как у плюсатого std::map, да. Ибо это и есть то самое дерево скорее всего.

[Geniepro]

Возможно глупый вопрос. При вставке, если данный ключ уже имеется в дереве, то как правильно обрабатывать эту ситуацию?
1. Вставлять
2. Ничего не делать
3. Сгенерить исключение

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

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

Не совсем понял. Получится два разных значения для одного ключа или второе значение перезапишет первоначальное?

[valexey_u]

Возможно глупый вопрос. При вставке, если данный ключ уже имеется в дереве, то как правильно обрабатывать эту ситуацию?
1. Вставлять
2. Ничего не делать
3. Сгенерить исключение

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

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

Не совсем понял. Получится два разных значения для одного ключа или второе значение перезапишет первоначальное?

Перезапишет. Иначе это уже не map, a multimap.

[ilovb]

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