C++：二叉搜索树进阶
文章目录
- 前言
- 一、二叉搜索树的查找（递归版本）
- 二、二叉树搜索树的插入（递归版本）
- 三、二叉搜索树的删除（递归版本）
- 四、析构函数
- 五、拷贝构造
- 六、赋值重载
- 七、代码总结
- 八、二叉搜索树性能对比
- 九、key_value模型
- 总结
前言
前面我们学习的二叉搜索树迭代的版本，今天我们来学习递归的版本~
递归版本在结构，以及遍历等这些地方都是一样的，最大的区别就在于插入和删除，代码量会简单很多。
一、二叉搜索树的查找（递归版本）
代码如下：
bool _FindR(Node* root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (key < root->_key)
{
return _FindR(root->_left, key);
}
else if (key > root->_key)
{
return _FindR(root->_right, key);
}
else
{
return true;
}
}
但是这样还有一个问题，同样就是外部_root我们调不到，就无法递归了，因此我们可以包一层：
bool _FindR(const K& key)
{
return _FindR(_root, key);
}
二、二叉树搜索树的插入（递归版本）
代码如下：
bool InsertR(const K& key)
{
return InsertR(_root, key);
}
bool InsertR(Node*& root, const K& key)
{
if (root->_key == nullptr)
{
root = new Node(key);
return true;
}
if (key < root->_key)
{
return InsertR(root->_left, key);
}
else if (key > root->_key)
{
return InsertR(root->_right, key);
}
else
{
return false;
}
}
三、二叉搜索树的删除（递归版本）
bool EraseR(const K& key)
{
return EraseR(_root, key);
}
bool EraseR(Node*& root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (key < root->_key)
{
return EraseR(root->_left, key);
}
else if (key > root->_key)
{
return EraseR(root->_right, key);
}
else
{
Node* del = root;
if (root->_left == nullptr)
{
root = root->_right;
}
else if (root->_right == nullptr)
{
root = root->_left;
}
else
{
Node* left_Max = root->_left;
while (left_Max->_right)
{
left_Max = left_Max->_right;
}
swap(root->_key, left_Max->_key);
EraseR(root->_left, key);
}
delete del;
return true;
}
}
四、析构函数
~BSTree()
{
Destroy(_root);
}
递归去删除：
这里要注意的是，删除的时候要使用后序遍历！
void Destroy(Node*& root)
{
if (root == nullptr)
return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
root = nullptr;
}
五、拷贝构造
BSTree(const BSTree<K>& t)
{
_root = Copy(t._root);
}
同样，递归去拷贝：
Node* Copy(Node* root)
{
if (root == nullptr)
return nullptr;
Node* copyroot = new Node(root->_key);
copyroot->_left = Copy(root->_left);
copyroot->_right = Copy(root->_right);
return copyroot;
}
六、赋值重载
直接使用现代写法：
BSTree<K>& operator= (BSTree<K> t)
{
swap(_root, t._root);
return *this;
}
七、代码总结
这里总结了递归版本以及非递归版本的代码总和：
namespace key
{
template<class K>
struct BSTreeNode
{
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
K _key;
BSTreeNode(const K& key)
:_left(nullptr)
, _right(nullptr)
, _key(key)
{}
};
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
BSTree()
:_root(nullptr)
{}
BSTree(const BSTree<K>& t)
{
_root = Copy(t._root);
}
BSTree<K>& operator=(BSTree<K> t)
{
swap(_root, t._root);
return *this;
}
~BSTree()
{
Destroy(_root);
}
bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(key);
if (parent->_key < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
bool Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
cur = cur->_right;
}
else if (cur->_key > key)
{
cur = cur->_left;
}
else
{
return true;
}
}
return false;
}
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else // 找到了
{
// 左为空
if (cur->_left == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent->_right == cur)
{
parent->_right = cur->_right;
}
else
{
parent->_left = cur->_right;
}
}
}// 右为空
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (parent->_right == cur)
{
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}
}
} // 左右都不为空
else
{
// 找替代节点
Node* parent = cur;
Node* leftMax = cur->_left;
while (leftMax->_right)
{
parent = leftMax;
leftMax = leftMax->_right;
}
swap(cur->_key, leftMax->_key);
if (parent->_left == leftMax)
{
parent->_left = leftMax->_left;
}
else
{
parent->_right = leftMax->_left;
}
cur = leftMax;
}
delete cur;
return true;
}
}
return false;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
bool FindR(const K& key)
{
return _FindR(_root, key);
}
bool InsertR(const K& key)
{
return _InsertR(_root, key);
}
bool EraseR(const K& key)
{
return _EraseR(_root, key);
}
private:
Node* Copy(Node* root)
{
if (root == nullptr)
return nullptr;
Node* copyroot = new Node(root->_key);
copyroot->_left = Copy(root->_left);
copyroot->_right = Copy(root->_right);
return copyroot;
}
void Destroy(Node*& root)
{
if (root == nullptr)
return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
root = nullptr;
}
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;
// 1、左为空
// 2、右为空
// 3、左右都不为空
if (root->_left == nullptr)
{
root = root->_right;
}
else if (root->_right == nullptr)
{
root = root->_left;
}
else
{
Node* leftMax = root->_left;
while (leftMax->_right)
{
leftMax = leftMax->_right;
}
swap(root->_key, leftMax->_key);
return _EraseR(root->_left, key);
}
delete del;
return true;
}
}
bool _InsertR(Node*& root, const K& key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (root->_key < key)
{
return _InsertR(root->_right, key);
}
else if (root->_key > key)
{
return _InsertR(root->_left, key);
}
else
{
return false;
}
}
bool _FindR(Node* root, const K& key)
{
if (root == nullptr)
return false;
if (root->_key < key)
{
return _FindR(root->_right, key);
}
else if (root->_key > key)
{
return _FindR(root->_left, key);
}
else
{
return true;
}
}
void _InOrder(Node* root)
{
if (root == NULL)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
private:
Node* _root;
};
八、二叉搜索树性能对比
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
- 最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为： l o g 2 N log_2 N log2N
- 最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为： N 2 \frac{N}{2} 2N
问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，二叉搜索树的性能都能达到最优？那么我们后续章节学习的AVL树和红黑树就可以上场了。
九、key_value模型
- K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
-
比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
-
以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树。在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
- KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：
-
比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对
-
再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。
这里我们要改的也就是模板参数初始化和插入，其他都不变。
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:
BSTree()
:_root(nullptr)
{}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
Node* FindR(const K& key)
{
return _FindR(_root, key);
}
bool InsertR(const K& key, const V& value)
{
return _InsertR(_root, key, value);
}
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;
// 1、左为空
// 2、右为空
// 3、左右都不为空
if (root->_left == nullptr)
{
root = root->_right;
}
else if (root->_right == nullptr)
{
root = root->_left;
}
else
{
Node* leftMax = root->_left;
while (leftMax->_right)
{
leftMax = leftMax->_right;
}
swap(root->_key, leftMax->_key);
return _EraseR(root->_left, 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);
}
else
{
return 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 == NULL)
{
return;
}
_InOrder(root->_left);
cout << root->_key << ":" << root->_value << endl;
_InOrder(root->_right);
}
private:
Node* _root;
};
void TestBSTree1()
{
//BSTree<string, Date> carTree;
BSTree<string, string> dict;
dict.InsertR("insert", "插入");
dict.InsertR("sort", "排序");
dict.InsertR("right", "右边");
dict.InsertR("date", "日期");
string str;
while (cin >> str)
{
BSTreeNode<string, string>* ret = dict.FindR(str);
if (ret)
{
cout << ret->_value << endl;
}
else
{
cout << "无此单词" << endl;
}
}
}
void TestBSTree2()
{
// 统计水果出现的次数
string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
BSTree<string, int> countTree;
for (auto& str : arr)
{
auto ret = countTree.FindR(str);
if (ret == nullptr)
{
countTree.InsertR(str, 1);
}
else
{
ret->_value++;
}
}
countTree.InOrder();
}
}
总结
到这里二叉搜索树的内容就都结束啦，接下来我们需要学习有关于AVL树以及红黑树的知识，以此解决二叉搜索树效率不稳定的问题。
创作不易，求求观众老爷多多支持😘😘😘
