数据结构 -- 二叉搜索树
二叉搜索树
概念
二叉搜索树又称为二叉排序树，它或为空树，或为具有以下性质的二叉树：
- 若它的左子树不为空，则左子树上所有节点的值都小于等于根节点的值。
- 若它的右子树不为空，则右子树上所有节点的值都大于等于根节点的值。
- 它的左右子树也分别为二叉搜索树。
- 二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景来定义，在后续我们学习的 map / set / multimap / multiset 系列容器底层就是二叉搜索树，其中 map / set 不支持插入相等值， multimap / multiset 支持插入相等值。
性能分析
最优情况下，二叉搜索树为完全二叉树（或接近完全二叉树），其高度为：logN。
最差情况下，二叉搜索树退化为单支树（或者类似单支），其高度为N。
综合而言，二叉搜索树增删查改时间复杂度为O(N)。
那么这样的效率显然是无法满足我们的需求的，我们后续课程需要继续讲解二叉搜索树的变形：平衡二叉搜索树（AVL树）和红黑树，这两种才能适用于我们在内存中存储和搜索数据。
另外需要说明的是，二分查找也可以实现O(logN)级别的查找效率，但是存在两大缺陷：
- 需要存储在支持下标随机访问的结构中，并且有序。
- 插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据。
因此后续我们会学习平衡二叉搜索树，二叉搜索树是为了后面的学习打基础。
代码演示：
namespace Key
{
//BSNode封装类
template<class K>
class BSNode
{
public:
K _key;
BSNode<K>* _left;
BSNode<K>* _right;
BSNode(const K& key)
:_key(key)
,_left(nullptr)
,_right(nullptr)
{}
};
//BSTree封装类
template<class K>
class BSTree
{
typedef BSNode<K> Node;
public:
bool Insert(const K& key)
{
//根节点为空时
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
// 根节点不为空
Node* cur = _root;
Node* Parent = nullptr;
while (cur) //为空时退出
{
if (cur->_key > key)
{
Parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
Parent = cur;
cur = cur->_right;
}
else
{//相等不插入
return false;
}
}
cur = new Node(key);
if (Parent->_key > cur->_key)
Parent->_left = cur;
else
Parent->_right = cur;
return true;
}
bool Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
cur = cur->_left;
}
else if (cur->_key < key)
{
cur = cur->_right;
}
else
{
return true;
}
}
return false;
}
bool Erase(const K& key)
{
Node* cur = _root;
Node* Parent = nullptr;
while (cur)
{
if (cur->_key > key)
{
Parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
Parent = cur;
cur = cur->_right;
}
else// 找到了
{
// 情况1、2、3
if (cur->_left == nullptr) //左孩子为空
{
if (Parent == nullptr)
{
_root = cur->_right;
}
else
{
if (Parent->_left == cur)
{
Parent->_left = cur->_right;
}
else
{
Parent->_right = cur->_right;
}
}
delete cur;
return true;
}
else if (cur->_right == nullptr)//右孩子为空
{
if (Parent == nullptr)
{
_root = cur->_left;
}
else
{
if (Parent->_left == cur)
{
Parent->_left = cur->_left;
}
else
{
Parent->_right = cur->_left;
}
}
delete cur;
return true;
}
else //都不为空 情况4
{
Node* replaceParent = cur;
Node* replace = cur->_right;
while (replace->_left)
{
replaceParent = replace;
replace = replace->_left;
}
//替换法
cur->_key = replace->_key;
if (replaceParent->_left == replace)//连接代替节点的父子节点
replaceParent->_left = replace->_right;
else
replaceParent->_right = replace->_right;
//删除替代节点
delete replace;
return true;
}
}
}
return false;
}
void Inorder()
{
_Inorder(_root);
}
private:
void _Inorder(Node* root)
{
if (root == nullptr)
{
return;
}
_Inorder(root->_left);
cout << root->_key <<" ";
_Inorder(root->_right);
}
private:
Node* _root = nullptr;
};
}BSNode是一个模板类，表示二叉树的节点。每个节点包含一个关键字_key和两个指向左右子节点的指针_left和_right。节点的构造函数接受一个关键字key并初始化左右子节点为空指针。BSTree是一个模板类，表示二叉搜索树。其成员函数包括插入 (Insert)、查找 (Find)、删除 (Erase) 和中序遍历 (Inorder) 树。私有成员_root用于存储树的根节点。- 该方法通过比较待插入的值与当前节点的值，沿着树的左右子树不断向下寻找合适的位置，最终将节点插入。插入时需要更新父节点的指针。插入的具体过程如下：
1. 树为空，则直接新增结点，赋值给 root 指针
2. 树不空，按二叉搜索树性质，插入值比当前结点大往右邹，插入值比当前结点小往左走，找到空位置，插入新结点。
3. 如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点。（要注意的是要保持逻辑⼀致性，插⼊相等的值不要⼀会往右走，⼀会往左走。 - 查找函数根据关键字进行二分搜索，通过与当前节点值的比较决定向左子树还是右子树继续查找。查找具体过程如下：
1. 从根开始比较，查找x，x比根的值大则往右边走查找，x比根值小则往左边走查找。
2. 最多查找高度次，走到到空，还没找到，这个值不存在。
3. 如果不支持插⼊相等的值，找到x即可返回。
4. 如果支持插入相等的值，意味着有多个x存在，⼀般要求查找中序的第⼀个x。如下图，查找到3，要找到1的右孩子的那个3返回。
- 删除函数具体过程如下：
首先查找元素是否在二叉搜索树中存在，如果不存在，则返回false。
如果查找的元素存在则分为下面四种情况进行处理：（假设要删除的节点值为N）
1.要删除的节点N的左右孩子均为nullptr。
2.要删除的节点N的左孩子为nullptr，右孩子不为nullptr。
3.要删除的节点N的右孩子为nullptr，左孩子不为nullptr。
4.要删除的节点N的左右孩子节点均不为nullptr。
对应上述四种情况，作出以下方案：
第一种：把N节点的父亲节点对应孩子指针指向空，直接删除节点。或者我们可以把第一种当做第二或三种情况来处理。
第二种：把N节点的父亲指向原删除孩子的指针指向N的右孩子，直接删除N节点。
第三种：把N节点的父亲指向原删除孩子的指针指向N的左孩子，直接删除N节点。
第四种：无法直接删除N节点，因为N的两个孩子无处安放，只能用替换法删除。找N左子树的值的最大节点(最右节点)R或是N右子树的值的最小节点(最左节点)R来代替N，因为这两个节点中的任意一个，放到N的位置，都能满足二叉搜索树的规则。替代N的意思就是N和R的两个节点值交换，转而删除R节点，R因为符合情况1/2/3，所以可以直接删除。 - 中序遍历函数
_Inorder会递归遍历左子树，访问当前节点，再递归遍历右子树。这样遍历的结果是按顺序输出树中的所有节点。
二叉搜索树使用场景
key搜索场景
只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索的值，搜索场景只需要判断key在不在。key的搜索场景实现的二叉搜索树支持增删查，但是不支持修改，修改key会破坏搜索树的结构。
场景1：校区无人值守车库，校区车库买了车位的业主才能进小区，那么物业会把买了车位的业主的车牌号录入后台系统，车辆进入时扫描车牌在不在系统中，在就允许进入，不再则不能进入。
场景2：检查一篇英文文章单词拼写是否正确，将词库所有单词放入二叉搜索树，读取文章中的单词，查找是否在二叉搜索树中，不再则波浪线标红提示。
key&value搜索场景
每⼀个关键码key，都有与之对应的值value，value可以任意类型对象。树的结构中(结点)除了需要存储key还要存储对应的value，增/删/查还是以key为关键字走二叉搜索树的规则进行比较，可以快速查找到key对应的value。key/value的搜索场景实现的⼆叉树搜索树⽀持修改，但是不支持修改key，修改key破坏搜索树性质了，可以修改value。
场景1：简单中英互译字典，树的结构中(结点)存储key(英文)和vlaue(中文)，搜索时输⼊英文，则同时查找到了英文对应的中文。
场景2：商场无人值守车库，入口进场时扫描车牌，记录车牌和入场时间，出口离场时，扫描车牌，查找入场时间，用当前时间减入场时间计算出停车时长，计算出停车费用，缴费后抬杆，车辆离场。
场景3：统计⼀篇文章中单词出现的次数，读取⼀个单词，查找单词是否存在，不存在这个说明第⼀次出现，（单词，1），单词存在，则++单词对应的次数。
key&value二叉搜索树
代码演示：
namespace key_value
{
//BSNode封装类
template<class K, class V>
class BSNode
{
public:
K _key;
V _value;
BSNode<K, V>* _left;
BSNode<K, V>* _right;
BSNode(const K& key, const V& value)
:_key(key)
,_value(value)
, _left(nullptr)
, _right(nullptr)
{}
};
//BSTree封装类
template<class K, class V>
class BSTree
{
typedef BSNode<K, V> Node;
public:
//默认构造
BSTree() = default;
//拷贝构造
BSTree(const BSTree<K, V>& t)
{
_root = Copy(t._root);
}
//赋值重载
BSTree<K, V>& operator=(BSTree<K, V> t)
{
swap(_root, t._root);
return *this;
}
~BSTree()
{
Destroy(_root);
_root = nullptr;
}
bool Insert(const K& key, const V& value)
{
//根节点为空时
if (_root == nullptr)
{
_root = new Node(key, value);
return true;
}
// 根节点不为空
Node* cur = _root;
Node* Parent = nullptr;
while (cur) //为空时退出
{
if (cur->_key > key)
{
Parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
Parent = cur;
cur = cur->_right;
}
else
{//相等不插入
return false;
}
}
cur = new Node(key, value);
if (Parent->_key > cur->_key)
Parent->_left = cur;
else
Parent->_right = cur;
return true;
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
cur = cur->_left;
}
else if (cur->_key < key)
{
cur = cur->_right;
}
else
{
return cur;
}
}
return nullptr;
}
bool Erase(const K& key)
{
Node* cur = _root;
Node* Parent = nullptr;
while (cur)
{
if (cur->_key > key)
{
Parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
Parent = cur;
cur = cur->_right;
}
else// 找到了
{
// 情况1、2、3
if (cur->_left == nullptr) //左孩子为空
{
if (Parent == nullptr)
{
_root = cur->_right;
}
else
{
if (Parent->_left == cur)
{
Parent->_left = cur->_right;
}
else
{
Parent->_right = cur->_right;
}
}
delete cur;
return true;
}
else if (cur->_right == nullptr)//右孩子为空
{
if (Parent == nullptr)
{
_root = cur->_left;
}
else
{
if (Parent->_left == cur)
{
Parent->_left = cur->_left;
}
else
{
Parent->_right = cur->_left;
}
}
delete cur;
return true;
}
else //都不为空 情况4
{
Node* replaceParent = cur;
Node* replace = cur->_right;
while (replace->_left)
{
replaceParent = replace;
replace = replace->_left;
}
//替换法
cur->_key = replace->_key;
if (replaceParent->_left == replace)//连接代替节点的父子节点
replaceParent->_left = replace->_right;
else
replaceParent->_right = replace->_right;
//删除替代节点
delete replace;
return true;
}
}
}
return false;
}
void Inorder()
{
_Inorder(_root);
}
private:
void _Inorder(Node* root)
{
if (root == nullptr)
{
return;
}
_Inorder(root->_left);
cout << root->_key << ":"<<root->_value<<endl;
_Inorder(root->_right);
}
void Destroy(Node* root)
{
if (root == nullptr)
{
return;
}
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
Node* Copy(Node* root)
{
//拷贝使用前序遍历
if (root == nullptr)
return;
Node* newnode = new Node(root->_key, root->_value);
newnode->_left = Copy(root->_left);
newnode->_right = Copy(root->_right);
return newnode;
}
private:
Node* _root = nullptr;
};
}BSNode是一个模板类，用于表示树中的每个节点。每个节点保存一个键值对（key和value），以及指向其左子节点和右子节点的指针。-
BSTree是一个模板类，表示二叉搜索树。它具有以下成员函数：
构造函数：包括默认构造函数、拷贝构造函数和赋值重载。
插入函数：Insert，将键值对插入到树中。
查找函数：Find，根据键查找节点。
删除函数：Erase，根据键删除节点。
遍历函数：Inorder，中序遍历树并输出节点的键值对。 -
Insert函数通过比较键的大小来决定将新节点插入到树中的位置。如果找到一个相同的键，则不插入。 -
Find函数根据键值进行二分查找，返回匹配的节点指针。如果没有找到对应的节点，返回nullptr。 -
Erase函数根据节点的子树情况处理：
左右子树均为空：按一个子数为空处理。
左子树为空：将右子树直接连接到父节点。
右子树为空：将左子树直接连接到父节点。
左右子树都不为空：找到右子树的最小节点，并替换当前节点。 -
Inorder函数是树的中序遍历，通过递归打印节点的键值对，按升序输出。 -
Destroy函数递归销毁树的所有节点，而Copy函数递归拷贝树的结构，生成一棵新的树。