数据结构 -- 二叉搜索树

🕗 发布于 2024-11-16 17:32 c++ 数据结构

二叉搜索树

概念

二叉搜索树又称为二叉排序树，它或为空树，或为具有以下性质的二叉树：

若它的左子树不为空，则左子树上所有节点的值都小于等于根节点的值。
若它的右子树不为空，则右子树上所有节点的值都大于等于根节点的值。
它的左右子树也分别为二叉搜索树。
二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景来定义，在后续我们学习的 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二叉搜索树