题解 P3370 【【模板】字符串哈希】

· · 题解

其实这题不用哈希，用二叉搜索树就可以解决了

什么是二叉搜索树

  1. 每个元素都有一个关键字，并且任意两个关键字都不同；因此，所有的关键字都是唯一的。
  2. 在根节点的左子树中，元素的关键字（如果有的话）都小于根节点的关键字。
  3. 在根节点的右子树中，元素的关键字（如果有的话）都大于根节点的关键字。
  4. 根节点的左子树，右子树也是二叉搜索树

如图：这两棵树都是二叉搜索树

由此看出：二叉搜索树的时间复杂度为O(h) ,h为树的高度。也就是说二叉搜索树的平均时间为O(log n),最坏为O(n)。随机数据的情况下最坏的几率很小。

依题意，我们只要把关键字 key由数字改为字符串即可。

插入

要插入 D ，因为树为空，所以直接插入到根节点，插入成功。

然后要插入 A, 因为D的字典序比A大，指针指向D的左子树，发现D的左子树为空，所以插入到D的左子树，插入成功，如下图所示。

然后要插入 F, 因为D的字典序比F小，指针指向D的右子树，发现D的右子树为空，所以插入到D的左子树，插入成功，如下图所示。

然后要插入 E，因为D的字典序比E小，指针指向D的右子树（也就是指针指向F），之后发现 E的字典序比 F小，指针指向 F的左子树，发现左子树为空，所以插入到F的左子树，插入成功，如下图所示。

最后要插入 A，因为D的字典序比A大，指针指向D的左子树，注意的地方来了 ，发现 A已经存在了，所以插入失败。

以此类推，我们这要统计 插入成功 的次数，把他输出即可。

然后我们可以很容易用链表写出二叉搜索树来。


#include <iostream>
#include<cstdio>
#include<string>
template<typename A, typename B>
class Binary_Search_Tree
{
public:
    Binary_Search_Tree()
    {
        root = NULL;
        treesize = 0;
    }
    ~Binary_Search_Tree()
    {
    }
    /*插入元素*/
    void ins(const A thekey, const B thedate)
    {
        node *q = root, *qq = NULL;
        while (q != NULL)
        {
            qq = q;
            if (thekey > q->key)/*如果要查找的关键字大于根节点的关键字，则取右子树找*/
                q = q->right;
            else if (thekey < q->key)/*如果要查找的关键字小于根节点的关键字，则取左子树找*/
                q = q->left;
            else
            {
                q->date = thedate;  /*如果相同关键字，则覆盖旧的值*/
                return;
            }
        }
        /*新建节点*/
        node *newnode = new node(thekey, thedate);
        if (root != NULL)   /*如果树不为空*/
        {
            if (thekey > qq->key)
                qq->right = newnode;
            else qq->left = newnode;
        }
        else    /*如果树为空*/
            root = newnode;
        treesize++;
    }
    /*返回节点个数*/
    inline unsigned int size()const
    {
        return treesize;
    }
private:
    struct node
    {
        A key;
        B date;
        node *left, *right;
        node(A _key,B _date)
        {
            key = _key;
            date = _date;
            left = NULL;
            right = NULL;
        }
    }*root;
    unsigned int treesize;
};
Binary_Search_Tree<std::string, bool> t;
int main()
{
    int n;
    scanf("%d", &n);
    std::string tmp;
    for (int i = 1; i <= n; i++)
    {
        std::cin >> tmp;
        t.ins(tmp, 1);
    }
    printf("%d", t.size());
    return 0;
}

二叉搜索树还有很多功能（查找、删除、最小值、最大值and so on），但是对于本题我们就不需要了，如果想学习的自行百度。如果你对二叉搜索树感兴趣的话，请学习特殊的平衡二叉搜索树：AVL树，它能保证树的高度为log(n)，也就是查找，插入，删除的复杂度都为log(n)。

如果还有不懂的可以点我头像私信我，如果你发现本题解有问题或有写得不清楚的地方，欢迎私信或在评论区留言。