c # — красное черное дерево и мультикарта
Во многих компиляторах стандартные структуры данных, такие как Set, Map а также Multimap использовать красно-черные деревья сзади, и multimap хранит несколько и дублированные ключи.
У меня есть вопрос по поводу цитаты ниже:
«Красно-черное дерево хранит ключи уникальным образом и связывает только одно DataValue с
каждый ключ «
- Вышеприведенное утверждение верно?
- Если это правда, как мы можем использовать красно-черное дерево для реализации
multimap(как C ++ STL сделал)?
Решение
1) Нет, не правда.
2) Изменение одного красного красного дерева сопоставления для сопоставления ключей с несколькими значениями будет тривиальным. Это просто потребует использования второй структуры данных и ключа сопоставления -> коллекции.
Например, вместо сопоставления строки и int вы можете сопоставить строку со вектором целых чисел. Или строка к связанному списку целых. Или строка для RBT с одним отображением. Скоро :).
Повторное посещение # 1: Технически это все равно будет отображать ключ на одно значение, просто значение не будет напрямую сопоставленным типом. В зависимости от того, что вы считаете «DataValue», тогда да, утверждение верно.
Кроме того, вспомогательная структура данных на самом деле не нужна; это просто упрощает обход. В основном, для размещения дубликатов, вместо строгого отношения меньше / больше, чем между родителем / слева и родителем / справа, у вас есть одна из сторон, также включающая равные.
Например:
5
3 7
3
Другие решения
Вы разрешаете дочерним элементам по обе стороны узла содержать ключи, которые ни меньше, ни больше, чем родительский. Вам нужно разрешить равенство с обеих сторон, потому что иначе вы можете ужасно потерять равновесие — дерево, состоящее из n равных ключей, будет иметь высоту n.
detector