string red black tree

Question

Я должен сформировать ответ на бумагу, которую я читаю о красных черных деревьях, и используя относительные ключи вместо абсолютных. Предполагается, что точка обсуждения относится к строкам.

Я точно не знаю, как можно использовать красное черное дерево для обработки строк, когда ключи должны быть числовыми значениями.

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

Это правильно? И если да, для чего его можно использовать?

Answer 1

Существует лексикографический порядок, который можно использовать в качестве критерия для сравнения строк и реализован на многих языках. Этот лексикографический порядок используется для упорядочения слов реального словаря, одного из документов.

Вам нужно установить этот порядок, чтобы знать, если ключ должен быть помещен слева от узла (когда ключ меньше, чем ключ узла) или вправо (если больше)

Wikipedia entry for lexicographical order

Так что да, вы можете обращаться с красным черным деревом со строками в виде ключей.