【C++数据结构】二叉搜索树
目录
- 【C++数据结构】二叉搜索树
- 二叉搜索树概念
- 二叉搜索树操作
- 二叉搜索树的查找
- 二叉搜索树的插入
- 二叉搜索树的删除
- 二叉搜索树的实现
- 二叉搜索树的应用
- 二叉搜索树的性能分析
作者：爱写代码的刚子
时间：2023.8.22
前言：二叉搜索树是为后面的map和set做铺垫，在有些题目中难度较大，需要我们打好二叉树的基础。
二叉搜索树概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
- 它的左右子树也分别为二叉搜索树
二叉搜索树操作
二叉搜索树的查找
二叉搜索树的插入
- a树为空，则直接插入
- 树不空，按二叉搜索树性质查找插入位置，插入新节点
- 如果插入的节点大于当前节点，就走右子树；如果插入的节点小于当前节点，就走左子树。
二叉搜索树的删除
首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况:
a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点
看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下:
情况b:删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点
情况c:删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点
情况d:在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中， 再来处理该结点的删除问题
二叉搜索树的实现
以下是我模拟实现二叉搜索树的代码
template<class T>
class BSTreeNode
{
public:
BSTreeNode<T>* _left;
BSTreeNode<T>* _right;
T _key;
BSTreeNode(const T&key)
:_left(nullptr)
,_right(nullptr)
,_key(key)
{}
};
template<class T>
class BSTree
{
typedef BSTreeNode<T> Node;
public:
BSTree()
:_root(nullptr)
{}
BSTree(const BSTree<T>& tree)
{
_root=_Copy(tree._root);
}
~BSTree()
{
_Destroy(_root);
}
BSTree<T>& operator=(BSTree<T> tree)
{
swap(_root,tree._root);
return *this;
}
bool InSert(const T&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->_left;
}
else if(cur->_key<key)
{
parent=cur;
cur=cur->_right;
}
else
{
return false;
}
}
cur = new Node(key);
if(parent->_key<key)
{
parent->_right=cur;
}
else{
parent->_left=cur;
}
return true;
}
bool Find(const T&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 T&key)
{
Node*parent=nullptr;
Node*cur=_root;
while(cur)
{
if(cur->_key>key)
{
parent = cur;
cur=cur->_left;
}
else if(cur->_key<key)
{
parent = cur;
cur = cur->_right;
}
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;//这里父节点不能置空，考虑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 if(parent->_right==leftMax)
{
parent->_right=leftMax->_left;
}
cur=leftMax;
}
delete cur;
cur=nullptr;
return true;
}
}
return false;
}
bool FindR(const T&key)//递归实现
{
return _FindR(_root,key);
}
void InOrder()
{
_InOrder(_root);
cout<<endl;
}
bool InSertR(const T&key)
{
return _InSertR(_root,key);
}
bool EraseR(const T&key)
{
return _EraseR(_root,key);
}
private:
Node* _Copy(const Node* root)
{
if(root==nullptr)
{
return nullptr;
}
Node* copynode=new Node(root->_key);
copynode->_left=_Copy(root->left);
copynode->_right=_Copy(root->_right);
return copynode;
}
bool _FindR(const Node*root,const T&key)
{
if(root==nullptr)
{
return false;
}
if(root->_key>key)
{
return _FindR(root->_left,key);
}
else if(root->_key<key)
{
return _FindR(root->_right,key);
}
else{
return true;
}
}
void _Destroy(Node*&root)
{
if(root==nullptr)
{
return;
}
_Destroy(root->_left);
_Destroy(root->_right);
delete root;
root=nullptr;
}
void _InOrder(const Node*root)
{
if(root==nullptr)
{
return;
}
_InOrder(root->_left);
cout<<root->_key<<" ";
_InOrder(root->_right);
}
bool _InSertR(Node*&root,const T&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;
}
//return false;
}
bool _EraseR(Node*&root,const T&key)
{
if(root==nullptr)
{
return false;
}
if(root->_key>key)
{
return _EraseR(root->_left,key);
}
else if(root->_key<key)
{
return _EraseR(root->_right,key);
}
else{
Node*save=root;
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);//注意这里不是传root
}
delete save;
return true;
}
}
private:
Node* _root;
};
几个需要注意的地方：
- 在
bool _EraseR(Node*&root,const T&key)这个函数中return _EraseR(root->_left,key);不能写为return _EraseR(root,key);否则会出现头节点删除不干净的情况：
举例：
- 在
bool Erase(const T&key)函数中
if(parent->_left==leftMax)//特殊情况
{
parent->_left=leftMax->_left;
}
是为了解决如下情况：
二叉搜索树的应用
- K模型:K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。 比如:给一个单词word，判断该单词是否拼写正确，具体方式如下:
- 以单词集合中的每个单词作为key，构建一棵二叉搜索树
- 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
- KV模型:每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生 活中非常常见:比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英 文单词与其对应的中文<word, chinese>就构成一种键值对;再比如统计单词次数，统计成功后，给定 单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。
比如:实现一个简单的英汉词典dict，可以通过英文找到与其对应的中文，具体实现方式如下:
- <单词，中文含义>为键值对构造二叉搜索树，注意:二叉搜索树需要比较，键值对比较时只比较 Key
- 查询英文单词时，只需给出英文单词，就可快速找到与其对应的key
（举例代码略过）
二叉搜索树的性能分析
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的 深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树:
最优情况下，二叉搜索树为完全二叉树，其平均比较次数为: log2N
最差情况下，二叉搜索树退化为单支树，其平均比较次数为: N/2
要学好搜索二叉树的应用还是要多刷题，多看看原理。
