朋友们大家好,本篇文章来到二叉搜索树的内容
1.二叉搜索树的介绍
二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:
它在动态数据集合中维护了一定的排序顺序,以便实现快速的数据查找、插入和删除操作
左子树比根小,右子树比根大
比如我想查找13,就不需要暴力比较,按照大小往左边或者右边走
对于二叉搜索树,进行中序遍历为升序
2.二叉搜索树的操作与实现
首先我们构建节点:
template<class K>
struct BSTreeNode
{
K _key;
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
BSTreeNode()
:_key(K())
,_left(nullptr)
,_right(nullptr)
{}
BSTreeNode(const K& key)
: _key(key)
, _left(nullptr)
, _right(nullptr)
{}
};
每个节点有两个指针,分别指向它的左子节点和右子节点。如果子节点不存在,则这些指针为nullptr
BSTreeNode()
:_key(K())
,_left(nullptr)
,_right(nullptr)
{}
默认构造函数,它初始化键值为K
类型的默认值(通过调用K
的默认构造函数),并将左右子节点指针都设置为nullptr
,表示节点没有子节点
BSTreeNode(const K& key)
: _key(key)
, _left(nullptr)
, _right(nullptr)
{}
采用键值作为参数的构造函数,它会创建一个节点,这个节点的键值为传入的key
值,同时初始化左右子节点指针为nullptr
接着我们来完成主体部分:
template<class T>
class BSTree
{
public:
typedef BSTreeNode<T> Node;
private:
Node* _root = nullptr;
};
insert插入
比如插入5,我们从根节点开始,比8小,往左走,比3大,往右走…:
bool Insert(const T& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
cur = cur->_right;
}
else if (cur->_key > key)
{
cur = cur->_left;
}
else
{
return false;
}
}
return true;
}
比当前节点小,往左走,反之往右走,搜索树默认是不允许插入重复键值
所以遇到相同的直接返回false,但是最后一步插入,我们还需要父亲位置的节点来完成左边插入或者右边插入,所以我们需要一个父亲节点来记录位置:
bool Insert(const T& 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
{
return false;
}
}
cur = new Node(key);
if (parent->_key < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
由于我们是从根部开始向下遍历直到达到叶节点,parent->_key必定不等于key(因为有重复检查)。如果parent的键值小于插入的键值key,新节点被设置为父节点的右子树;否则设置为左子树
注意
这里如果起始为**空树*
Node* cur = _root;
while (cur)
{
// ...
}
由于cur
是从_root
开始的,如果跳过判空且_root
实际上为nullptr
,这个循环不会执行任何操作,因为它的条件立即不满足(cur
此时为nullptr
),并且会跳到循环之后的代码,如下:
cur = new Node(key);
// ...
这里将创建一个新的节点,但此时变量parent
仍然是nullptr
。代码会接着尝试访问parent
的_key
成员:
if (parent->_key < key)
{
// ...
}
因为parent
是nullptr
,这会导致未定义行为,最常见的是程序崩溃,因为你不能对nullptr
解引用。另外,即使程序不崩溃,新的节点cur
也没有父节点可以挂载到,这样二叉搜索树的结构就不完整了
所以完整代码如下:
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->_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;
}
Find查找
find这里思路很简单,就按照大小关系往下遍历即可:
bool Find(const T& 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;
}
InOrder中序遍历
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
这里我们需要传入根节点,为类成员,单独一个函数是无法实现的,所以我们先完成上面的子函数书写,再一个主函数传入_root
即可
void InOrder()
{
_InOrder(_root);
cout << endl;
}
测试如下:
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
for (int e : a)
{
b1.Insert(e);
}
b1.InOrder();
Erase删除
二叉树的删除是这里的难点,因为它涉及到多种情况,针对不同的情况我们对应不同的方法:
前三种情况可以结合起来:
情况2:删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除
情况3:删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除
情况4:替换法解决
对于一个节点,它的:
替换法删除的思路分为以下步骤:
进行这样的替换之后,二叉搜索树的特性依然得以保持。中序后继节点保证了替换后的节点值仍然比其左子节点的所有值大,且比其右子节点(除了被移除的中序后继节点外)的所有值小
替换法删除操作需要注意的关键点是,通过中序前驱或中序后继节点替换,实际上我们把删除一个可能有两个子节点的难题转变成了删除一个有零个或一个子节点的简单问题,且这个中序后继节点一定在待删除节点的右子树中最左侧
bool Erase(const T& key)
{
if (_root == nullptr)
return false;
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 (cur == parent->_left)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else {
if (cur == parent->_left)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;
}
else
{
//左右都不为空,替换法删除
Node* rightminparent = cur;
Node* rightmin = cur->_right;
while (rightmin->_left)
{
rightminparent = rightmin;
rightmin = rightmin->_left;
}
cur->_key = rightmin->_key;
if (rightminparent->_left = rightmin)
{
rightminparent->_left = rightmin->_right;
}
else
{
rightminparent->_right = rightmin->_right;
}
delete rightmin;
}
return true;
}
}
return false;
}
我们拆分来看这串代码:
if (_root == nullptr)
return false;
while
循环遍历树找到匹配key
的节点。在循环中使用变量cur
作为当前节点,变量parent
作为cur
的父节点
key
匹配的节点后:
cur->_left == nullptr
), 那么它的右子节点直接替换它(也适用于它没有子节点的情况)cur->_right == nullptr
), 那么它的左子节点直接替换它if (cur->_left == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (cur == parent->_left)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
}
如果cur恰好是根节点,我们直接将树的根 _root 指向cur的右子节点。这个更新意味着我们在树中移除了根节点,并将右子节点(如果存在)提升为新的根节点。
如果cur不是根节点,我们需要更新它父节点的相应指针。我们检查cur是其父节点的左子还是右子,并相应地更新父节点的左指针或右指针,使其指向cur的右子节点。这样,在二叉搜索树中删除了cur节点,并保持了其右子树
cur
的键为中序后继节点的键,并将rightmin
放在原来的位置上。else
{
//左右都不为空,替换法删除
Node* rightminparent = cur;
Node* rightmin = cur->_right;
while (rightmin->_left)
{
rightminparent = rightmin;
rightmin = rightmin->_left;
}
cur->_key = rightmin->_key;
if (rightminparent->_left == rightmin)
{
rightminparent->_left = rightmin->_right;
}
else
{
rightminparent->_right = rightmin->_right;
}
delete rightmin;
}
注意,在替换完成后需要删除原始的中序后继节点。这时rightmin
的右子节点(如果存在)会替换rightmin
。
每次删除一个节点后,代码会释放该节点的内存。
最后,如果在树中找到并成功删除了key
对应的节点,则函数返回true
。如果没有找到,则函数返回false
。
3.二叉搜索树的应用(K与KV模型)
比如英汉词典就是英文与中文的对应关系,通过英文可以快速找到与其对应的中文,英文单词与其对应的中文<word, chinese>
就构成一种键值对;
再比如统计单词次数,统计成功后,给定单词就可快速找到其出现的次数,单词与其出现次数就是<word, count>
就构成一种键值对
改造二叉树为KV结构
节点构建,加一个模版参数V
template<class K,class V>
struct BSTreeNode
{
V _value;
K _key;
BSTreeNode<K,V>* _left;
BSTreeNode<K,V>* _right;
BSTreeNode()
:_key(K())
, _value(V());
, _left(nullptr)
, _right(nullptr)
{}
BSTreeNode(const K& key,const V& value)
: _key(key)
,_value(value)
, _left(nullptr)
, _right(nullptr)
{}
};
代码主题部分只需要进行简单的修改即可:
template<class K,class V>
class BSTree
{
public:
typedef BSTreeNode<K,V> Node;
bool Insert(const K& key,const V& value)
{........
cur = new Node(key,value);
........
}
Node* 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 cur;
}
}
return nullptr;
}
........
};
其余部分不需要改变
简单示例如下:
void TestBSTree2()
{
BSTree<string, string> dict;
dict.Insert("string", "字符串");
dict.Insert("left", "左边");
dict.Insert("insert", "插入");
//...
string str;
while (cin >> str)
{
BSTreeNode<string, string>* ret = dict.Find(str);
if (ret)
{
cout << ret->_value << endl;
}
else
{
cout << "无此单词,请重新输入" << endl;
}
}
}
本节内容到此结束! 感谢阅读!!
4.二叉搜索树性能分析
插入和删除操作都必须先查找,查找效率代表了二叉搜索树中各个操作的性能
对有n个结点的二叉搜索树,若每个元素查找的概率相等,则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数,即结点越深,则比较次数越多
但对于同一个关键码集合,如果各关键码插入的次序不同,可能得到不同结构的二叉搜索树:
最优情况下,二叉搜索树为完全二叉树(或者接近完全二叉树),其平均比较次数为O(log n)
最差情况下,二叉搜索树退化为单支树(或者类似单支),查找的时间复杂度为O(n)
如果退化成单支树,二叉搜索树的性能就失去了。那能否进行改进,不论按照什么次序插入关键码,二叉搜索树的性能都能达到最优?
期待后续AVL树和红黑树的讲解
本节内容到此结束!!感谢阅读!!