文章目录
一、⼆叉搜索树的概念
⼆叉搜索树是二叉树是一个重要应用，就是在二叉树的基础上新增了一个搜索功能。
⼆叉搜索树⼜称⼆叉排序树，它要么是⼀棵空树，要么是具有以下性质的⼆叉树:
- 若它的左⼦树不为空，则左⼦树上所有结点的值都⼩于等于根结点的值
- 若它的右⼦树不为空，则右⼦树上所有结点的值都⼤于等于根结点的值
- 它的左右⼦树也分别为⼆叉搜索树
- ⼆叉搜索树中可以⽀持插⼊相等的值，也可以不⽀持插⼊相等的值，具体看使⽤场景定义，后续小编介绍map/set/multimap/multiset系列容器底层就是⼆叉搜索树，其中map/set不⽀持插⼊相等值，multimap/multiset⽀持插⼊相等值。小编接下来模拟实现是二叉搜索树是不支持插⼊相等的值的。
1、当它要查找一个特定值时，不会像我们前面介绍的list vector一样暴力遍历整个结构查找，⼆叉搜索树最多查找它的高度次。
2、它又叫⼆叉排序树是因为如果中序遍历整颗树最后的结果是有序的。
二、二叉搜索树的性能分析
最优情况下，⼆叉搜索树为完全⼆叉树(或者接近完全⼆叉树)，其⾼度为： log2 N
最差情况下，⼆叉搜索树退化为单⽀树(或者类似单⽀)，其⾼度为： N
所以综合⽽⾔⼆叉搜索树增删查改时间复杂度为： O(N)
那么这样的效率显然是⽆法满⾜我们需求的，我们后续会继续讲解⼆叉搜索树的变形，平衡 ⼆叉搜索树AVL树和红⿊树，才能适⽤于我们在内存中存储和搜索数据。
另外需要说明的是，⼆分查找也可以实现 O(log2 N) 级别的查找效率，但是⼆分查找有两⼤缺陷：
- 需要存储在⽀持下标随机访问的结构中，并且有序。
- 插⼊和删除数据效率很低，因为存储在下标随机访问的结构中，插⼊和删除数据⼀般需要挪动数据，这⾥也就体现出了平衡⼆叉搜索树的价值。
三、⼆叉搜索树模拟实现
在模拟实现之前小编先介绍一个规则，⼆叉搜索树是不允许修改的，因为修改后调整⼆叉搜索树的难度极高。
定义⼆叉搜索树
//定义结点
//定义结点
template<class K>
struct BSTNode
{
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;
BSTNode(const K& key)
{
_key = key;
_left = nullptr;
_right = nullptr;
}
};
template<class K>
class BSTree
{
typedef BSTNode<K> Node;
public:
private:
BSTNode* _root = nullptr;
};
这里注意把typedef BSTNode< K > Node; 定义为类的私有，因为结点属于BSTree 的内部实现细节，不希望类外部能访问这个别名。
BSTNode不会给外部访问，所以直接用struct定义就可以。
BSTree的成员变量_root应该要给缺省值nullptr。
插入
这里可以用递归实现，但是没必要，递归开销太大。我们这里就用循环来控制，逻辑是定义一个cur指针从_root开始走，可是最后要将cur和原二叉树连接到一起，所以还需要定义一个结点parent来记录cur的上一个走过的结点，最后cur走到空后与parent连接就完成了插入操作。若_root为nullptr直接将值new给root，若_root不为nullptr则比较key和当前结点的大小，比当前结点小则往左走，比当前结点大则往右走，若走到和key相等的结点说明重复了，直接return。走到nullptr后表示已经到了应该插入的位置，parent已经就绪，但是这时不知道应该插到parent的左边还是右边，所以还需要比较key与parent所在结点的值的大小，结点值比key大插左边，否则插右边。
如果支持插入相等的值的话相等的值插到和它相等的值结点的左边和右边都可以，因为无论左右都不影响中序遍历的结果，并且我们后面学到红黑树会发现就算插到了左边也有可能旋转到右边。（要注意的是要保持逻辑⼀致性，插⼊相等的值不要⼀会往右⾛，⼀会往左⾛）
bool Insert(const K& key)
{
//若根节点为空直接插入
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
//parent记录位置，方便新结点与原树做连接
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
//若插入值比当前结点小，往当前结点左边走
if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
//若插入值比当前结点大，往当前结点右边走
else if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
//若当前树有与插入值相等的结点，直接返回
else
{
return false;
}
}
//出循环表示待连接的parent已经就位
//还需判断插在parent的左边还是右边
cur = new Node(key);
if (key < parent->_key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}
查找
1、从根开始⽐较，查找x，x⽐根的值⼤则往右边⾛查找，x⽐根值⼩则往左边⾛查找，这里和插入操作的一部分代码很相似。
2、最多查找⾼度次，⾛到到空，还没找到，这个值不存在，返回false。
3、如果不⽀持插⼊相等的值，找到x即可返回。
4、如果⽀持插⼊相等的值，意味着有多个x存在，⼀般要求查找中序遍历的第⼀个x。如下图，查找3，要找到1的右孩⼦的那个3返回。
bool Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key < cur->_key)
{
cur = cur->_left;
}
else if (key > cur->_key)
{
cur = cur->_right;
}
else
{
return true;
}
}
//cur走到空还没找到说明树里没有key
return false;
}
删除
删除操作相对比较复杂，首先还是需要先找到待删除元素结点和它的父结点，如果待删除元素不存在，则返回false。若存在这里结点的删除依待结点的孩子不同分为4种情况：
- 1、要删除结点N左右孩⼦均为空
- 2、要删除的结点N左孩⼦为空，右孩⼦结点不为空
- 3、要删除的结点N右孩⼦为空，左孩⼦结点不为空
- 4、要删除的结点N左右孩⼦结点均不为空
对应以上四种情况的解决⽅案：
- 把N结点的⽗亲对应孩⼦指针指向空，直接删除N结点（情况1可以当成2或者3处理，相当于把空指针当成N的左、右孩⼦，效果是⼀样的）
- 把N结点的⽗亲对应孩⼦指针指向N的右孩⼦(不为空的孩子，相当于把自己的孩子给孩子的爷爷托管(bushi))，具体操作是修改指向之前需要先判断cur父亲结点的哪个指针指向cur，把该指针指向N的右孩⼦，然后直接删除N结点
- 把N结点的⽗亲对应孩⼦指针指向N的左孩⼦，具体操作是修改指向之前需要先判断父亲结点的哪个指针指向cur，把该指针指向N的左孩⼦，然后直接删除N结点
- 这里⽆法直接删除N结点，因为N的两个孩⼦⽆处安放，只能⽤替换法删除。找N左⼦树里值最⼤的结点R(最右结点)或者N右⼦树里值最⼩的结点R(最左结点)替代N，因为这两个结点中任意⼀个，放到N的位置，都满⾜⼆叉搜索树的规则，不改变结构。替代N的意思就是N和R的两个结点的值交换，转⽽变成删除R结点，R结点符合情况2或情况3，可以直接删除。(小编下面用找N左⼦树里值最右结点来演示）
除此之外还有两个坑需要注意避开：
坑点1，如下图若删除根结点且根的右子树为空，不能用常规方法那样调整父节点的指针指向当前结点的孩子结点来删除，因为根节点没有父节点。这种情况的处理方法是把根节点给给不为空子树的根节点，原来的根节点会在delete cur时释放。
坑点2：代码最后交换后删除结点哪里，修改指针指向时不能直接把replace的左给给replaceparent的右，这里有个思维惯性就是左子树的最右结点就是它的父节点的右孩子，这并不一定。因为有可能cur的左子树只有一个结点，那么左子树的最右结点是它的父节点的右孩子了，要把replace的左给给replaceparent的左，比如下面示意图删3或6。所以还需要判断replace是replaceparent的左孩子还是右孩子。
bool erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else //cur的值等于key，删除结点cur
{
//情况1、2
if (cur->_left == nullptr)
{
//若删除根且根的左子树为空，
// 直接转移根节点给根的左孩子
if (cur == _root) //坑点1
{
//这里不用delete旧的_root,后面cur会删
_root = _root->_right;
}
//常规删除
else
{
if (parent->_right == cur)
{
parent->_right = cur->_right;
}
else
{
parent->_left = cur->_right;
}
}
delete cur;
return true;
}
//情况3
else if(cur->_right == nullptr)
{
//若删除根且根的右子树为空，
// 直接转移根节点给根的右孩子
if (cur == _root)
{
_root = _root->_left;
}
else
{
//常规删除
if (parent->_right == cur)
{
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}
}
delete cur;
return true;
}
//情况4
else
{
//找左子树最右结点
Node* replace = cur->_left;
Node* replaceparent = cur;
while (replace->_right)
{
replaceparent = replace;
replace = replace->_right;
}
swap(cur->_key, replace->_key);
//坑点2
if (replaceparent->_right == replace)
replaceparent->_right = replace->_left;
else
replaceparent->_left = replace->_left;
delete replace;
}
return true;
}
}
return false; //树里没有key，删除失败
}
中序遍历
中序遍历二叉树我们已经介绍过了，小编还画了一幅详细的递归展开图，感兴趣的读者可以看看：点这里
这里我们实现的中序遍历就可以体现出C和C++的区别，我们C语言实现的二叉树没有类的访问限制，所以可以直接把创建出来的二叉树根节点传给中序遍历，而C++因为有类的访问限制，我们在类外面只能调用类的公有成员函数来完成插入删除之类的操作，类内部的私有成员变量我们无法访问，意思是虽然我们自己创建了一颗二叉树，可二叉树的根节点值是多少我们是不知道的也访问不到，而中序遍历需要我们传根节点指针进去，所以这里我们可以实现成友元或者再写一个get函数，这里小编用一种更优雅的方式来实现，再写一层inorder的壳供外部调用，这个壳内部再去调用真正的inorder。
void InOrder() //壳
{
_InOrder(_root);
cout << endl;
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
析构
⼆叉搜索树存在浅拷贝的问题，所以析构、拷贝构造、赋值运算符重载都需要我们自己写，析构函数和inorder的情况一样，需要套一层壳。递归析构应该采用后序遍历的方式，以免先把父节点析构后找不到左右孩子了。
~BSTree()
{
Destroy(_root);
_root = nullptr;
}
void Destroy(Node* root)
{
if (root == nullptr)
return;
Destroy(root->_left);
Destroy(root->_right);
}
拷贝构造
首先不能遍历树然后插入，因为插入顺序不同最后树的结构也不同，所以这里要递归拷贝，先拷贝根节点，然后拷贝它的左右子树。写了拷贝构造后还要把显示要求编译器生成默认构造函数写上。
BSTree() = default;
BSTree(const BSTree<K>& t)
{
_root = Copy(t._root);
}
Node* Copy(const Node* root)
{
if (root == nullptr)
return nullptr;
Node* newroot = new Node(root->_key);
newroot->_left = Copy(root->_left);
newroot->_right = Copy(root->_right);
return newroot;
}
赋值运算符重载(优雅)
这里小编隆重推出一个赋值运算符重载现代写法的最优解，以前我们现代写法是传引用调用operator=和手动拷贝再swap，未免太麻烦了吧，看下面这四行优雅的代码，值传递天然完成拷贝，然后再用拷贝的值去swap。只需要注意一点，参数不能加const，因为它还要接受原来旧资源的值，出了作用域后调用拷贝构造清理旧资源，而且是值传递，不涉及权限的放大，const对象也能调用。
这里也不用担心传值调用要拷贝会有花销，就算不在传值的时候拷贝在operator=内部也需要手动拷贝。
BSTree<K>& operator=(BSTree<K> t)
{
swap(_root, t._root);
return *this;
}
以前的写法小编也贴一份：
BSTree<K>& operator=(const BSTree<K>& root)
{
BSTree tmp(root); //手动拷贝
swap(_root, tmp);
return *this;
}
四、⼆叉搜索树key和key/value
key：
只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值，搜索场景只需要判断key在不在。key的搜索场景实现的⼆叉树搜索树⽀持增删查，但是不⽀持修改，修改key破坏搜索树结构了。
key/value：
每⼀个关键码key，都有与之对应的值value，value可以任意类型对象。树的结构中(结点)除了需要存储key还要存储对应的value，增/删/查还是以key为关键字⾛⼆叉搜索树的规则进⾏⽐较，可以快速查找到key对应的value。key/value的搜索场景实现的⼆叉树搜索树⽀持修改，但是不⽀持修改key，修改key破坏搜索树性质了，可以修改value。
改造原key⼆叉搜索树为key/value
首先结点结构要多一个value变量和对应的模板参数，后面BSTree模板参数、内部插入接口参数，new新结点等都需要跟着改，find函数因为key/value可以修改结点的value值了，所以不止要判断某个值是否存在，还需要提供节点访问能力，方便对 value 进行操作，所以key/value版的find返回值是Node*。删除操作只在交换key时要顺带把value交换了，其他保持不变。
template<class K, class V>
struct BSTNode
{
K _key;
V _value;
BSTNode<K, V>* _left;
BSTNode<K, V>* _right;
BSTNode(const K& key, const V& value)
{
_key = key;
_value = value;
_left = nullptr;
_right = nullptr;
}
};
template<class K, class V>
class BSTree
{
typedef BSTNode<K, V> Node;
public:
bool Insert(const K& key, const V& value)
{
//若根节点为空直接插入
if (_root == nullptr)
{
_root = new Node(key, value);
return true;
}
//parent记录位置，方便新结点与原树做连接
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
//若插入值比当前结点小，往当前结点左边走
if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
//若插入值比当前结点大，往当前结点右边走
else if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
//若当前树有与插入值相等的结点，直接返回
else
{
return false;
}
}
//出循环表示待连接的parent已经就位
//还需判断插在parent的左边还是右边
cur = new Node(key, value);
if (key < parent->_key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key < cur->_key)
{
cur = cur->_left;
}
else if (key > cur->_key)
{
cur = cur->_right;
}
else
{
return cur;
}
}
//cur走到空还没找到说明树里没有key
return nullptr;
}
bool erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else //cur的值等于key，删除结点cur
{
//情况1、2
if (cur->_left == nullptr)
{
//若删除根且根的左子树为空，
// 直接转移根节点给根的左孩子
if (cur == _root)
{
//这里不用delete旧的_root,后面cur会删
_root = _root->_right;
}
//常规删除
else
{
if (parent->_right == cur)
{
parent->_right = cur->_right;
}
else
{
parent->_left = cur->_right;
}
}
delete cur;
return true;
}
//情况3
else if (cur->_right == nullptr)
{
//若删除根且根的右子树为空，
// 直接转移根节点给根的右孩子
if (cur == _root)
{
_root = _root->_left;
}
else
{
//常规删除
if (parent->_right == cur)
{
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}
}
delete cur;
return true;
}
//情况4
else
{
//找左子树最右结点
Node* replace = cur->_left;
Node* replaceparent = cur;
while (replace->_right)
{
replaceparent = replace;
replace = replace->_right;
}
swap(cur->_key, replace->_key);
swap(cur->_value, replace->_value);
if (replaceparent->_right == replace)
replaceparent->_right = replace->_left;
else
replaceparent->_left = replace->_left;
delete replace;
}
return true;
}
}
return false; //树里没有key，删除失败
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << ":" << root->_value << " ";
_InOrder(root->_right);
}
Node* _root = nullptr;
};
它的使用场景如下，第一个样例如果把所有英语单词都插入这颗二次搜索树的话，可以用来快速分辨你输入是是不是英语单词，第二个可以用来统计一个数组里某个字符串出现的次数。
BSTree<string, string> dict;
//BSTree<string, string> copy = dict;
dict.Insert("left", "左边");
dict.Insert("right", "右边");
dict.Insert("insert", "插⼊");
dict.Insert("string", "字符串");
string str;
while (cin >> str)
{
auto ret = dict.Find(str);
if (ret)
{
cout << "->" << ret->_value << endl;
}
else
{
cout << "无此单词，请重新输入" << endl;
}
}
string arr[] = { "苹果", "西瓜","苹果", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果"};
BSTree<string, int> countTree;
for (const auto& str : arr)
{
// 先查找⽔果在不在搜索树中
// 1、不在，说明⽔果第⼀次出现，则插⼊<⽔果, 1>
// 2、在，则查找到的结点中⽔果对应的次数++
//BSTreeNode<string, int>* ret = countTree.Find(str);
auto ret = countTree.Find(str);
if (ret == NULL)
{
countTree.Insert(str, 1);
}
else
{
ret->_value++;
}
}
countTree.InOrder();
以上就是小编分享的全部内容了，如果觉得不错还请留下免费的关注和收藏
如果有建议欢迎通过评论区或私信留言，感谢您的大力支持。
一键三连好运连连哦~~
