文章目录
二叉搜索树的概念
二叉搜索树,它的左子树的值比根的值小,右子树的值比根的值大
比如这一树,根节点的值8比左子树所有节点都大,比右子树的所有节点都小.
二叉搜索树的操作
二叉搜索树的查找find
因为二叉树有以上特性,所有使得它在搜索方面有极大的优势.
比如我们要找值为7的节点在不在
1.我们从根节点开始找,因为7<根节点的值8,所有根节点在左子树
2.现在根节点的值为3<7,所有在3的右子树中
3.现在根节点的值为6<7,所有在6的右子树中,刚好右子树的节点为7.
二叉搜索树最多寻找高度次,如果走到空还没有找到,说明这个值不存在
二叉搜索树的模拟实现
构造节点
template<class K>
struct BSTreeNode
{
typedef BSTreeNode<K> Node;
Node* _left;
Node* _right;
K _val;
BSTreeNode(const K& val)
:_left(nullptr)
, _right(nullptr)
, _val(val)
{}
};
_val里面存节点的值
insert
bool insert(const K& val)
{
//a.树为空,直接构造新节点赋值给根节点
if (_root == nullptr)
{
_root = new Node(val);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
//找到空的节点进行插入
while (cur)
{
if (cur->_val < val)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_val > val)
{
parent = cur;
cur = cur->_left;
}
// 二叉搜索树默认不允许重复
else
{
return false;
}
}
cur = new Node(val);
if (parent->_val < val)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
插入有两种情况
a.树为空,直接构造新节点赋值给根节点
b.树不为空,按照二叉树的性质找到应该插入的空位置插入.
注意:
在b情况下,要找到新节点的位置,也要找到该节点的父亲节点,这样才能进行链接
假设要插入0节点,不光要找到0节点应该放的位置,还要找到0节点的父亲1,将他们链接起来
find
bool find(const K& val)
{
Node* cur = _root;
while (cur)
{
if (cur->_val < val)
{
cur = cur->_right;
}
else if (cur->_val > val)
{
cur = cur->_left;
}
else
{
return true;
}
}
return false;
}
按照二叉搜索树的概念,比根大的往右走,比根小的往左走.
找到返回true,找不到返回false
erase(细节巨多,面试可能会考)
erase里面的细节很多,要细品.
删除的节点有多种可能
a.叶子节点
比如这棵树我们要删除4节点,就只需要找到4节点和它的父亲节点6,让父亲节点6指向空,再删除4节点.
b.有一个孩子
特殊情况
要删除的是根节点,此时要更新新的根节点10.
if (_root == cur)
{
_root = cur->_right;
delete cur;
}
左孩子
右为空,父亲指向我的左
有一个左孩子,说明右子树为空.
此时要让父亲指向3的左边,此时不清楚是父亲的左边还是父亲的右边指向1节点
父亲的左指向我的左
父亲的右指向我的左
代码实现
if (cur->_right == nullptr)
{
//删除头节点
if (_root == cur)
{
_root = cur->_left;
delete cur;
}
else
{
if (parent->_right == cur)
parent->_right = cur->_left;
else
parent->_left = cur->_left;
delete cur;
}
}
右孩子
左为空, 父亲指向我的右
//左为空, 父亲指向我的右
else if (cur->_left == nullptr)
{
//删除头节点
if (_root == cur)
{
_root = cur->_right;
delete cur;
}
else
{
if (parent->_right == cur)
parent->_right = cur->_right;
else
parent->_left = cur->_right;
delete cur;
}
}
右孩子的判断和左孩子类似,方向反过来而已.
c.有两个孩子
找到左边的最大值或者右边的最小值,与目标值进行替换.
这里以右边的最小值为例.
我们寻找右边的最小值时,同时要找它的父亲节点,因为要对它的父亲节点进行修改.
找到右边的最小值为4,将4覆盖到cur上面,再删除right_min这个节点.
注意:
因为是寻找右子树的最小值,所以这个最小值理论上应该没有左子树.
如果有左子树,说明有更小的值.但是可能会有右子树.
所有要让right_min_parent左节点指向right_min的右节点.
这只是理论上,实际里面还有一个大坑
如果我们要删除的节点:cur和right_min_parent 指向同一个地方时,此时应该让right_min_parent 的右节点指向right_min的右节点.
//有两个孩子:找到左边的最大值或者右边的最小值,与目标值进行替换
//让这个右最小节点的父亲的左边指向右最小的右边,因为它此时最多只有右孩子
else
{
Node* right_min_parent = cur;
Node* right_min = cur->_right;
while (right_min->_left)
{
right_min_parent = right_min;
right_min = right_min->_left;
}
cur->_val = right_min->_val;
//右最小节点,有坑,是连续存放的有序值
if (cur->_right == right_min)
right_min_parent->_right = right_min->_right;
else
right_min_parent->_left = right_min->_right;
delete right_min;
}
erase代码
bool erase(const K& val)
{
Node* parent = _root;
Node* cur = _root;
//找到要删除的目标值
while (cur)
{
if (cur->_val < val)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_val > val)
{
parent = cur;
cur = cur->_left;
}
else
{
//只有一个孩子/叶子节点:让父亲节点指向子节点的右(nullptr)
//右为空,父亲指向我的左
if (cur->_right == nullptr)
{
//删除头节点
if (_root == cur)
{
_root = cur->_left;
delete cur;
}
else
{
if (parent->_right == cur)
parent->_right = cur->_left;
else
parent->_left = cur->_left;
delete cur;
}
}
//左为空, 父亲指向我的右
else if (cur->_left == nullptr)
{
//删除头节点
if (_root == cur)
{
_root = cur->_right;
delete cur;
}
else
{
if (parent->_right == cur)
parent->_right = cur->_right;
else
parent->_left = cur->_right;
delete cur;
}
}
//有两个孩子:找到左边的最大值或者右边的最小值,与目标值进行替换
//让这个右最小节点的父亲的左边指向右最小的右边,因为它此时最多只有右孩子
else
{
Node* right_min_parent = cur;
Node* right_min = cur->_right;
while (right_min->_left)
{
right_min_parent = right_min;
right_min = right_min->_left;
}
cur->_val = right_min->_val;
//右最小节点,有坑,是连续存放的有序值
if (cur->_right == right_min)
right_min_parent->_right = right_min->_right;
else
right_min_parent->_left = right_min->_right;
delete right_min;
}
return true;
}
}
return false;
}
中序遍历
void MidOrder()
{
_MidOrder(_root);
cout << endl;
}
private:
void _MidOrder(const Node* root)
{
if (root == nullptr)
{
return;
}
_MidOrder(root->_left);
std::cout << root->_val << " ";
_MidOrder(root->_right);
}
首先,中序的搜索方式是左子树 根 右子树.按照这个顺序就能有序的取出搜索二叉树里面的值了
为什么会有两个函数?
因为函数的形参没有this指针,没法调用_root根节点,我们需要另外一个函数来传_root根节点
二叉搜索树的应用
k模型
k模型跟我们上面实现的一样,只存储一个值
比如:我们可以用这个功能查找到我们英文作文里面的拼写错误的单词.
我们可以把词库里面所有的英语单词丢进这个二叉搜索树,再遍历整个作文,检查每个单词是否存在,不存在就报错.
k模型模拟实现的总代码
namespace shh1
{
template<class K>
struct BSTreeNode
{
typedef BSTreeNode<K> Node;
Node* _left;
Node* _right;
K _val;
BSTreeNode(const K& val)
:_left(nullptr)
, _right(nullptr)
, _val(val)
{}
};
//k模型
template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;
public:
bool insert(const K& val)
{
if (_root == nullptr)
{
_root = new Node(val);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
//找到空的节点进行插入
while (cur)
{
if (cur->_val < val)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_val > val)
{
parent = cur;
cur = cur->_left;
}
// 二叉搜索树默认不允许重复
else
{
return false;
}
}
cur = new Node(val);
if (parent->_val < val)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
bool erase(const K& val)
{
Node* parent = _root;
Node* cur = _root;
//找到要删除的目标值
while (cur)
{
if (cur->_val < val)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_val > val)
{
parent = cur;
cur = cur->_left;
}
else
{
//只有一个孩子/叶子节点:让父亲节点指向子节点的右(nullptr)
//右为空,父亲指向我的左
if (cur->_right == nullptr)
{
//删除头节点
if (_root == cur)
{
_root = cur->_left;
delete cur;
}
else
{
if (parent->_right == cur)
parent->_right = cur->_left;
else
parent->_left = cur->_left;
delete cur;
}
}
//左为空, 父亲指向我的右
else if (cur->_left == nullptr)
{
//删除头节点
if (_root == cur)
{
_root = cur->_right;
delete cur;
}
else
{
if (parent->_right == cur)
parent->_right = cur->_right;
else
parent->_left = cur->_right;
delete cur;
}
}
//有两个孩子:找到左边的最大值或者右边的最小值,与目标值进行替换
//让这个右最小节点的父亲的左边指向右最小的右边,因为它此时最多只有右孩子
else
{
Node* right_min_parent = cur;
Node* right_min = cur->_right;
while (right_min->_left)
{
right_min_parent = right_min;
right_min = right_min->_left;
}
cur->_val = right_min->_val;
//右最小节点,有坑,是连续存放的有序值
if (cur->_right == right_min)
right_min_parent->_right = right_min->_right;
else
right_min_parent->_left = right_min->_right;
delete right_min;
}
return true;
}
}
return false;
}
bool find(const K& val)
{
Node* cur = _root;
while (cur)
{
if (cur->_val < val)
{
cur = cur->_right;
}
else if (cur->_val > val)
{
cur = cur->_left;
}
else
{
return true;
}
}
return false;
}
void MidOrder()
{
_MidOrder(_root);
cout << endl;
}
private:
void _MidOrder(const Node* root)
{
if (root == nullptr)
{
return;
}
_MidOrder(root->_left);
std::cout << root->_val << " ";
_MidOrder(root->_right);
}
private:
Node* _root = nullptr;
};
void BST_Test1()
{
int a[] = { 6,5,1,4,7,2,3,8,9,11,55,68,-1 };
BSTree<int> t;
for (auto e : a)
{
t.insert(e);
}
t.MidOrder();
}
void BST_Test2()
{
int a[] = { 8 };
BSTree<int> t;
for (auto e : a)
{
t.insert(e);
}
t.MidOrder();
for (auto e : a)
{
t.erase(e);
t.MidOrder();
}
}
}
k-value模型
每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。
这个在我们日常生活很常见,比如词典的翻译,我们在key里面存英语单词,value里面存相对应的中文翻译.
我们就可以通过输入英文单词得到其对应的中文翻译.
下面稍作演示:
void TestBSTree()
{
BSTree<string, string> dict;
dict.Insert("insert", "插入");
dict.Insert("erase", "删除");
dict.Insert("left", "左边");
dict.Insert("string", "字符串");
string str;
while (cin >> str)
{
auto ret = dict.Find(str);
if (ret)
{
cout << str << ":" << ret->_val << endl;
}
else
{
cout << "单词拼写错误" << endl;
}
}
}
k-value模型模拟实现的总代码
k-value模型的代码和上面的key模型类似,我们只需要要添加新节点的时候再加一个值就行.
namespace shh2
{
template<class K, class V>
struct BSTreeNode
{
typedef BSTreeNode<K, V> Node;
Node* _left;
Node* _right;
K _key;
V _val;
BSTreeNode(const K& key, const V& val)
:_left(nullptr)
, _right(nullptr)
, _key(key)
, _val(val)
{}
};
template<class K, class V>
class BSTree
{
typedef BSTreeNode<K, V> Node;
Node* _root = nullptr;
public:
bool Insert(const K& key, const V& val)
{
//头节点
if (_root == nullptr)
{
_root = new Node(key, val);
return true;
}
Node* parent = _root;
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, val);
if (parent->_key < key)
parent->_right = cur;
else
parent->_left = cur;
return true;
}
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;
}
bool Erase(const K& key)
{
Node* parent = _root;
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;
delete cur;
}
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;
delete cur;
}
else
{
if (cur == parent->_left)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
delete cur;
}
}
//两个孩子 找到cur左子树的最大值替换
else
{
Node* left_max_parent = cur;
Node* left_max = cur->_left;
while (left_max->_right)
{
left_max_parent = left_max;
left_max = left_max->_right;
}
swap(cur->_key, left_max->_key);
if (left_max_parent->_left = left_max)
left_max_parent->_left = left_max->_left;
else
left_max_parent->_right = left_max->_left;
delete left_max;
}
return true;
}
}
}
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << ":" << root->_val << endl;
_InOrder(root->_right);
}
void InOrder()
{
_InOrder(_root);
}
};
void TestBSTree()
{
BSTree<string, string> dict;
dict.Insert("insert", "插入");
dict.Insert("erase", "删除");
dict.Insert("left", "左边");
dict.Insert("string", "字符串");
string str;
while (cin >> str)
{
auto ret = dict.Find(str);
if (ret)
{
cout << str << ":" << ret->_val << endl;
}
else
{
cout << "单词拼写错误" << endl;
}
}
}
};
二叉搜索树的不足
当二叉搜索树有序存入了一段值
这棵树会退化成单叉树,因为插入,查找和删除的时间复杂度都是高度次,
所以在这种情况下插入,查找和删除的时间复杂度会接近于N.搜索二叉树也就失去了它的优势.
AVL树和红黑树的出现
怎么解决这个问题呢,就要用到AVL和红黑树了.
在插入的时候,AVL树会查看树的高度是否平衡,
左子树和右子树的高度差不超过1.超过1会让树的几个节点之间发生旋转,最终这棵树会变成这样.
我们平时调用的容器map和set底层就是用AVL树和红黑树生成的.
总结
二叉搜索树的插入和查找不难,但是它的删除细节很多,分类很细,一不留神容易掉坑里面,面试也经常会考.大家如果不懂的话,要多看几遍.