个人主页：仍有未知等待探索-CSDN博客
专题分栏：C++
一、概念
二叉搜索树，又称二叉排序树（中序是有序的）。
性质
1、非空左子树的键值小于根节点的键值
2、非空右子树的键值大于根节点的键值
（空树也是二叉搜索树）
二、操作
查找
查找，从根节点开始比较键值大小，如果比根节点的键值小，进左子树；比根节点的键值大，进右子树，然后继续进行比较。
插入
和查找差不多，先找到要插入的位置，然后进行插入即可。
// 要插入的值 val void insert(const T& val) { // 特判一下空树 if (_root == nullptr) { node* tmp = new node(val); _root = tmp; return; } // 记得要记录一下插入位置的父节点 node* parent = _root; node* cur = _root; while (cur) { if (cur->val > val) { parent = cur; cur = cur->left; } else { parent = cur; cur = cur->right; } } cur = new node(val); if (parent->val > val) { parent->left = cur; } else { parent->right = cur; } }
删除
删除一个节点的情况比较复杂，分为四种情况。
a.删除的节点为叶子节点
如果要删除 13 这个叶子节点，我们只需要让 13 的父节点的左孩子指向nullptr。
如果要删除 7 这个叶子节点，我们需要让 7 的父节点的右孩子指向nullptr。
总结：让要删除节点的父节点的对应指针指向空。
对应指针：判断要删除的节点是其父节点的左孩子还是右孩子。如果是左孩子，父节点的左孩子指向空；如果是右孩子，父节点的右孩子指向空。
b.删除的节点只有左子树
如果要删除 14 这个节点，我们需要让 14 的父节点的对应指针指向 14 的左子树。
总结：让要删除节点的父节点的对应指针指向要删除节点的左子树。
c.删除的节点只有右子树
如果要删除 10 这个节点，我们需要让 10 的父节点指向 10 的右子树。
总结：让要删除节点的父节点的对应指针指向要删除节点的右子树。
d.删除的节点有左、右子树
对于这个这种情况，我们用替换法来进行删除。首先我们先找到要删除节点的右子树中的最小值，然后和要删除的节点进行值替换，最后我们要删除掉替换后的节点。
总结：先替换，然后删除替换后的节点（判断替换后的节点的类型，然后用对应的删除方法）
void erase(const T& val)
{
node* cur = _root;
node* parent = _root;
while (cur)
{
if (cur->val > val)
{
parent = cur;
cur = cur->left;
}
else if (cur ->val < val)
{
parent = cur;
cur = cur->right;
}
else
{
if (cur->left == nullptr)
{
if (cur == _root)
{
_root = cur->right;
}
else if (parent->left == cur)
{
parent->left = cur->right;
}
else if (parent->right == cur)
{
parent->right = cur->right;
}
delete cur;
}
else if(cur->right == nullptr)
{
if (cur == _root)
{
_root = cur->left;
}
else if (parent->left == cur)
{
parent->left = cur->left;
}
else if (parent->right == cur)
{
parent->right = cur->left;
}
delete cur;
}
else
{
node* tmp = cur->right;
node* tp = cur;
while (tmp->left)
{
tp = tmp;
tmp = tmp->left;
}
swap(cur->val, tmp->val);
// 交换完，就相当是删除tmp，tmp的特点是左子树为空
// 也相当于是删除没有左子树的节点
if (tp->left == tmp)
tp->left = tmp->right;
else
tp->right = tmp->right;
delete tmp;
}
}
}
}总代码
#include <iostream> #include <vector> using namespace std; template<class T> struct BSTN { BSTN(const T& e) :left(nullptr) ,right(nullptr) ,val(e) {} BSTN<T>* left; BSTN<T>* right; T val; }; template<class T> class BST { typedef BSTN<T> node; public: BST() :_root(nullptr) {} void insert(const T& val) { if (_root == nullptr) { node* tmp = new node(val); _root = tmp; return; } node* parent = _root; node* cur = _root; while (cur) { if (cur->val > val) { parent = cur; cur = cur->left; } else { parent = cur; cur = cur->right; } } cur = new node(val); if (parent->val > val) { parent->left = cur; } else { parent->right = cur; } } void inorder() { _inorder(_root); } bool find(const T& val) { node* cur = _root; while (cur) { if (cur->val > val) { cur = cur->left; } else if (cur->val < val) { cur = cur->right; } else { return true; } } return false; } void erase(const T& val) { node* cur = _root; node* parent = _root; while (cur) { if (cur->val > val) { parent = cur; cur = cur->left; } else if (cur ->val < val) { parent = cur; cur = cur->right; } else { if (cur->left == nullptr) { if (cur == _root) { _root = cur->right; } else if (parent->left == cur) { parent->left = cur->right; } else if (parent->right == cur) { parent->right = cur->right; } delete cur; } else if(cur->right == nullptr) { if (cur == _root) { _root = cur->left; } else if (parent->left == cur) { parent->left = cur->left; } else if (parent->right == cur) { parent->right = cur->left; } delete cur; } else { node* tmp = cur->right; node* tp = cur; while (tmp->left) { tp = tmp; tmp = tmp->left; } swap(cur->val, tmp->val); // 交换完，就相当是删除tmp，tmp的特点是左子树为空 // 也相当于是删除没有左子树的节点 if (tp->left == tmp) tp->left = tmp->right; else tp->right = tmp->right; delete tmp; } } } } private: void _inorder(node* root) { if (root == nullptr) return; _inorder(root->left); cout << root->val << " "; _inorder(root->right); } private: node* _root; };
三、K-V模型
什么叫K-V模型？
其全称是key-value模型，是一种映射关系。一个key（关键字）对应一个value（值）。
比如：英语和汉语就是一种kv模型。stl库中的map也是一种kv模型，不过底层不是用二叉搜索树实现的。
代码
#include <iostream>
#include <vector>
using namespace std;
template<class K, class V>
struct BSTN
{
typedef pair<K, V> PKV;
BSTN(const PKV& e)
:left(nullptr)
,right(nullptr)
,val(e)
{}
BSTN<K, V>* left;
BSTN<K, V>* right;
PKV val;
};
template<class K, class V>
class BST
{
typedef pair<K, V> PKV;
typedef BSTN<K, V> node;
public:
BST()
:_root(nullptr)
{}
void insert(const PKV& val)
{
if (_root == nullptr)
{
node* tmp = new node(val);
_root = tmp;
return;
}
node* parent = _root;
node* cur = _root;
while (cur)
{
if (cur->val.first > val.first)
{
parent = cur;
cur = cur->left;
}
else
{
parent = cur;
cur = cur->right;
}
}
cur = new node(val);
if (parent->val.first > val.first)
{
parent->left = cur;
}
else
{
parent->right = cur;
}
}
void inorder()
{
_inorder(_root);
}
bool find(const K& val)
{
node* cur = _root;
while (cur)
{
if (cur->val > val)
{
cur = cur->left;
}
else if (cur->val < val)
{
cur = cur->right;
}
else
{
return true;
}
}
return false;
}
void erase(const PKV& val)
{
node* cur = _root;
node* parent = _root;
while (cur)
{
if (cur->val.first > val.first)
{
parent = cur;
cur = cur->left;
}
else if (cur ->val.first < val.first)
{
parent = cur;
cur = cur->right;
}
else
{
if (cur->left == nullptr)
{
if (cur == _root)
{
_root = cur->right;
}
else if (parent->left == cur)
{
parent->left = cur->right;
}
else if (parent->right == cur)
{
parent->right = cur->right;
}
delete cur;
}
else if(cur->right == nullptr)
{
if (cur == _root)
{
_root = cur->left;
}
else if (parent->left == cur)
{
parent->left = cur->left;
}
else if (parent->right == cur)
{
parent->right = cur->left;
}
delete cur;
}
else
{
node* tmp = cur->right;
node* tp = cur;
while (tmp->left)
{
tp = tmp;
tmp = tmp->left;
}
swap(cur->val, tmp->val);
// 交换完，就相当是删除tmp，tmp的特点是左子树为空
// 也相当于是删除没有左子树的节点
if (tp->left == tmp)
tp->left = tmp->right;
else
tp->right = tmp->right;
delete tmp;
}
}
}
}
private:
void _inorder(node* root)
{
if (root == nullptr) return;
_inorder(root->left);
cout << root->val.first << " " << root->val.second << endl;
_inorder(root->right);
}
private:
node* _root;
};
