Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, sokel, Вы писали:
S>>Обычно код обоих функций идентичен за исключением проверки в find ключа на равенство перед возвратом. Иная реализация будет сделана в ущерб эффективности. Так что, наверное, не могут... Хотя явно это в стандарте действительно не указано.
К>Как раз наоборот.
К>Давай построим ДДП для 3 одинаковых элементов.
К>К> 1 1 1
К> / \ \ /
К> 1 1 1 1
К> \ /
К> 1 1
К>
К>Три варианта: сбалансированное, вырожденное в правый список, вырожденное в левый список.
Деревья в STL сбалансированные, вырожденных быть не может.
К>Ищем ключ "1". Очевидно, что корневой узел сразу же подходит. И только в одном случае он является нижней границей. Причём видно, что если мы специально заточим дерево под условие, что нижняя граница является корнем поддерева с одинаковыми ключами — то мы введём дисбаланс.
К>То же относится и к двоичному поиску на сортированном массиве, кстати говоря.
