二叉查找树的应用 —— K模型和KV模型

---

前言

在上一篇文章中，我们进行了二叉查找树的实现（文章链接），那么今天主要探讨一下二叉查找树的应用

1. K模型

K 模型即只有 key 作为关键码，结构中只需要存储 Key 即可，关键码即为需要搜索到的值。

比如：给一个单词 word，判断该单词是否拼写正确，具体方式如下：

• 以单词集合中的每个单词作为 key，构建一棵二叉查找树
• 在二叉查找树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。

其实这个 K 模型就是上一篇文章中，我们实现的二叉查找树。

2. KV模型

所谓 KV 模型就是每一个关键码 key，都有与之对应的值 Value，即 <Key, Value> 的键值对。

这种方式在现实生活中非常常见：比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文 <word, chinese>就构成一种键值对；

再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是 <word, count> 就构成一种键值对。

下面我们就构造一个 KV 模型的二叉查找树，然后用这棵树来做一些应用。

🍑 构建KV模型的树

我这里直接用递归的方式实现整颗树，需要添加一个模板参数 Value，另外对于查找函数 Find 的返回值就不能写成 bool 类型了，而是需要写成 Node* 类型，因为 Key 不能被修改，但是我们可以通过返回的节点类型来修改 Key 对应的 Value。

代码实现

// KV模型
namespace key_value
{	// 节点类template<class K, class V>struct BSTreeNode{BSTreeNode<K, V>* _left; // 左指针BSTreeNode<K, V>* _right; // 右指针K _key; // 关键码V _value; // 对应的值// 构造函数BSTreeNode(const K& key, const V& value):_left(nullptr), _right(nullptr), _key(key), _value(value){}};// 二叉查找树类template<class K, class V>class BSTree{typedef BSTreeNode<K, V> Node;public:// 中序遍历void InOrder(){_InOrder(_root);cout << endl;}// 查找函数Node* FindR(const K& key){return _FindR(_root, key);}// 插入函数// 注意：这里除了要插入key,还要插入对应的valuebool InsertR(const K& key, const V& value){return _InsertR(_root, key, value);}// 删除函数(只需要删除key即可)bool EraseR(const K& key){return _EraseR(_root, key);}private:// 删除函数(递归删除子函数)bool _EraseR(Node*& root, const K& key){if (root == nullptr)return false;if (root->_key < key){return _EraseR(root->_right, key);}else if (root->_key > key){return _EraseR(root->_left, key);}else{Node* del = root;// 删除if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else{Node* minRight = root->_right;while (minRight->_left){minRight = minRight->_left;}swap(root->_key, minRight->_key);return _EraseR(root->_right, key);}delete del;return true;}}// 插入函数(递归插入子函数)bool _InsertR(Node*& root, const K& key, const V& value){if (root == nullptr){root = new Node(key, value);return true;}if (root->_key < key)return _InsertR(root->_right, key, value);else if (root->_key > key)return _InsertR(root->_left, key, value);elsereturn false;}// 查找函数(递归查找子函数)Node* _FindR(Node* root, const K& key){if (root == nullptr)return nullptr;if (root->_key < key){return _FindR(root->_right, key);}else if (root->_key > key){return _FindR(root->_left, key);}else{return root;}}// 中序遍历(递归遍历子函数)void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << ":" << root->_value << endl;_InOrder(root->_right);}private:Node* _root = nullptr;};
}

🍑 英汉词典

用这棵树实现一个简单的英汉词典 dict，可以通过英文找到与其对应的中文。

以 <单词, 中文含义> 为键值对构造二叉查找树时，二叉查找树需要进行键值对的比较，并且只需要比较 Key，查询英文单词时，只需给出英文单词，就可快速找到与其对应的 key。

代码实现

void TestBSTree1()
{BSTree<string, string> ECDict;ECDict.InsertR("root", "根");ECDict.InsertR("string", "字符串");ECDict.InsertR("left", "左边");ECDict.InsertR("insert", "插入");ECDict.InsertR("erase", "删除");ECDict.InsertR("right", "右边");cout << "请输入要查找的单词: ";string str; // 输入要查找的单词while (cin >> str){auto ret = ECDict.FindR(str);if (ret != nullptr){cout << "对应的中文:" << ret->_value << endl; // 如果单词存在，输出对应的中文}else{cout << "无此单词，请重新输入" << endl; // 如果单词不存在}}
}

可以看到，当我们输入树中存在的单词时，就会显示对应的中文，如果单词不存在，就不会显示。

如果我们要修改某个单词的中文也是可以的，只需要修改节点指向的 Value 即可。

🍑 统计水果出现的次数

KV 模型的二叉树还可以用来统计某个元素出现的次数。

比如下面有一组水果，现在我需要统计水果出现的次数，并输出。

代码实现

void TestBSTree2()
{string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };// 水果出现的次数BSTree<string, int> countTree; // key是字符串; value是次数for (const auto& str : arr){auto ret = countTree.FindR(str); // 查找该水果是否存在if (ret == nullptr) // 如果该水果不存在{countTree.InsertR(str, 1); // 就插入到树中,并把次数置为1(出现了一次)}else // 如果该水果存在{ret->_value++;  // 就修改value}}// 打印结果countTree.InOrder();
}

可以看到水果的次数已经被统计出来了

3. 总结

对于 K 模型的二叉查找树上节课我们已经说过了，它有很多缺点，后面的 AVL树 就是在它的基础上进行优化的，那么与之对应的就是 STL 当中的 set 容器，它的底层就是一颗 K 模型的二叉查找树。

对于 KV 模型的二叉查找树，它与之对应的是 STL 当中的 map 容器，它的底层是一颗 KV 模型的二叉查找树。