字符串紅黑樹

Question

我應該對我正在閱讀關於紅黑樹的一篇論文形成迴應，並使用相對鍵而不是絕對值。討論的重點應該是把它與字符串聯繫起來。

我並不完全知道如何使用紅黑樹來處理字符串，當鍵被假定爲數字值時。

我能弄清楚的最好的是字符串可以按照某些標準進行排序，然後該有序列表中每個字符串的索引就是其關鍵字。之後，樹上的所有操作都是在紅黑樹上製作的普通操作。

這是正確的嗎？如果是這樣，它可以用於什麼？

Answer 1

您可以使用字典學順序作爲比較字符串的標準，並以多種語言實現。這個辭典順序是用來排列一個真正的詞典，其中一個紙。

您需要設置此順序以便知道密鑰是否必須放置在節點的左側（當密鑰小於節點的密鑰時）或向右（當大於時）

Wikipedia entry for lexicographical order

所以是的，你可以處理一個紅色的黑樹，用琴鍵作爲琴鍵。