C++二叉平衡树单词频次统计

在C++中，我们可以使用二叉平衡树（如AVL树或红黑树）来高效地统计单词的频次。二叉平衡树的一个典型应用就是作为字典结构，因为它提供O(log n)的时间复杂度来插入、删除和查找元素，这对于频繁的插入和查询操作非常有利。

以下是大致步骤：

1. **创建节点结构**：首先定义一个节点结构，包含一个字符表示单词的一部分、指向左右子节点的指针以及用于维护平衡的附加字段（如AVL树的高度差或红黑树的颜色标记）。

struct TreeNode {
    char ch;
    int freq;
    TreeNode* left;
    TreeNode* right;
    // 平衡树的额外字段...
};

2. **构建平衡树**：遍历输入文本，每次遇到新词或单词结束时，将单词插入到树中。插入操作会自动保持平衡，如果插入导致不平衡，就需要通过旋转操作调整。

TreeNode* insert(TreeNode*& root, const string& word) {
    if (!root)
        return new TreeNode(word[0], 1);
    // 插入操作...
}

3. **查找和更新**：查找单词频率只需从根节点开始递归，更新则直接修改对应的节点计数。

4. **统计频次**：遍历整个树，计算每个节点的`freq`属性即可得到单词的总频次。

5. **迭代搜索**：如果你想在运行时查找特定单词，可以采用迭代的方式来避免不必要的遍历，只关注感兴趣的路径。

int searchFrequency(const TreeNode* root, const string& word) {
    for (char c : word) {
        if (!root || root->ch != c)
            return 0; // 如果遇到非当前单词的字符或到达空节点，返回0
        root = root->right; // 转向右子树
    }
    return root ? root->freq : 0;
}