Как сравнить строки (без учета регистра) при вставке одинаковых строк в двоичное дерево (с учетом регистра)?

Question

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

Вот моя insert функция.

TreeNode* Tree::insert(TreeNode* node, string value) {
    transform(value.begin(), value.end(), value.begin(), ::tolower);

    if (node == nullptr) {
        return newTreeNode(value);
    }
    if (node->data < value) {
        node->left = insert(node->left, value);
    }
    else if(node-> data > value) {
        node->right = insert(node->right, value);
    }
    else {
        return node;
    }
    node->height = 1 + max(height(node->left), height(node->right));
    return node;
}

Вот мой заголовочный файл дерева:

struct TreeNode {
public:
    TreeNode* left;
    TreeNode* right;
    string data;
};

class Tree {
public:
    TreeNode * newTreeNode(string data);
    TreeNode * insert(TreeNode* node, string value);
    void lexographicPrint(TreeNode* root);
};

newTreeNode Funciton:

TreeNode* AvlTree::newTreeNode(string value) {
    TreeNode* treeNode = new TreeNode();
    treeNode->data = value;
    treeNode->left = nullptr;
    treeNode->right= nullptr;
    treeNode->height = 1;
    return treeNode;
}

Функция печати:

void AvlTree::lexographicPrint(TreeNode* root) {
    if (root != nullptr) {
        lexographicPrint(root->right);
        cout << root->data << " ";
        lexographicPrint(root->left);
    }
}

В настоящее время это работает так, как я хочу, за исключением того факта, что дерево содержит все значения в нижнем регистре, очевидно из-за функции transform. Я попытался использовать holdValue, вот так:

string holdValue;
if (isupper(value[0]) {
    holdValue = value;
}

в верхней части моей функции, заменив все insert вызовы holdValue. Меня смущает, почему это меняет порядок моего дерева, когда все еще производятся сравнения с value. Я ожидал, что это сработает, но это не так. Я еще не нашел решение с помощью поиска Google.

Answer 1

Вместо использования std::string < вы можете использовать сравнение без учета регистра.

bool ci_less(const std::string & lhs, const std::string & rhs) {
    return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), [](char l, char r){ return std::to_lower(l) < std::tolower(r); });
}

TreeNode* Tree::insert(TreeNode* node, std::string value) {

    if (node == nullptr) {
        return newTreeNode(std::move(value));
    }
    if (ci_less(node->data, value)) {
        node->left = insert(node->left, std::move(value));
    }
    else if(ci_less(value, node->data)) {
        node->right = insert(node->right, std::move(value));
    }
    else {
        return node;
    }
    node->height = 1 + max(height(node->left), height(node->right));
    return node;
}

Вам потребуется #include <algorithm> для std::lexicographical_compare.

Аналогичным образом вы могли бы вместо этого определить нечувствительный к регистру тип строки

struct ci_char_traits : public std::char_traits<char> {
    static char to_upper(char ch) {
        return std::toupper((unsigned char) ch);
    }
    static bool eq(char c1, char c2) {
         return to_upper(c1) == to_upper(c2);
     }
    static bool lt(char c1, char c2) {
         return to_upper(c1) <  to_upper(c2);
    }
    static int compare(const char* s1, const char* s2, size_t n) {
        while ( n-- != 0 ) {
            if ( to_upper(*s1) < to_upper(*s2) ) return -1;
            if ( to_upper(*s1) > to_upper(*s2) ) return 1;
            ++s1; ++s2;
        }
        return 0;
    }
    static const char* find(const char* s, int n, char a) {
        auto const ua (to_upper(a));
        while ( n-- != 0 ) 
        {
            if (to_upper(*s) == ua)
                return s;
            s++;
        }
        return nullptr;
    }
};

using ci_string = std::basic_string<char, ci_char_traits>;

Answer 2

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

Есть две вещи, которые вы можете сделать.

1. Заменить все из ваших a < b и a > b проверок с case_insensitive_compare(a, b) < 0 и case_insensitive_compare(a, b) > 0, где case_insensitive_compare выглядит примерно так:

   // +ve => l > r
   // 0 => l equivalent to r (possibly different case)
   // -ve => l < r
   int case_insensitive_compare(const std::string& l, const std::string& r) noexcept {
       std::size_t max_size = std::max(l.size(), r.size());
       for (std::size_t i = 0; i < max_size; ++i) {
           int cmp = std::tolower(l[i]) - std::tolower(r[i]);
           if (cmp != 0) return cmp;
       }
       return l.size() - r.size();
   }
   
   // Or in c++20
   // std::weak_ordering::greater => l > r
   // std::weak_ordering::equivalent => l equivalent to r
   // std::weak_ordering::less => l < r
   std::weak_ordering case_insensitive_compare(const std::string& l, const std::string& r) noexcept {
       std::size_t max_size = std::max(l.size(), r.size());
       for (std::size_t i = 0; i < max_size; ++i) {
           auto cmp = std::tolower(l[i]) <=> std::tolower(r[i]);
           if (cmp != 0) return cmp;
       }
       return l.size() <=> r.size();
   }
   

   Вы должны иметь возможность обобщить это для любой функции компаратора (Для Tree<T>, компаратор cmp(const T&, const T&) -> int)

2. Заставьте TreeNode сохранить пару ключ / значение, где ключ - это строчная строка, а значение - это смешанный регистр строка. Если вам нужно, чтобы дерево сохраняло другое значение, задайте значение std::tuple<std::string, ValueType>.