文章目录
1.二叉搜索树概念
二叉搜索树又称二叉排序树，可以是一棵空树；如果不是空树，则是一棵具有以下性质的二叉树:
- 若它的左子树不为空，则左子树上
所有节点的值都小于根节点的值 - 若它的右子树不为空，则右子树上
所有节点的值都大于根节点的值 - 它的左右子树也分别为二叉搜索树
二叉搜索树也是递归定义的。由定义可以得出一个重要的性质：中序遍历一棵二叉搜索树时可以得到一个节点值递增的有序序列。
2.二叉搜索树的操作
2.1节点与树结构
跟二叉树类似，我们的树仅仅维持一个root指针即可，这里无非就是增加了模板的使用。
- 节点
template<class K>
struct BSTNode
{
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;
BSTNode(const K& val = K())
:_key(val)
,_left(nullptr)
,_right(nullptr)
{}
};
- 树
template<class K>
class BSTree
{
typedef BSTNode<K> Node;//节点重命名
public:
BSTree()
:_root(nullptr)
{}
private:
Node* _root;
};
2.2二叉搜索树的查找
- 从根开始比较，比根大，就在右子树中查找；比根小，就在左子树中查找
- 最多查找高度次，走到空还未找到，则找不到
bool find(const K& val)
{
Node* cur = _root;
while (cur)
{
if (cur->_key < val)
cur = cur->_right;
else if (cur->_key > val)
cur = cur->_left;
else
return true;
}
return false;
}
2.3二叉搜索树的插入
- 二叉搜索树不允许出现重复的节点；若要插入的节点已经存在，则插入失败
- 树为空，插入的节点就作为根
- 树不为空，按照树的规则寻找插入位置，将节点插入
- 要想连接上，应记录其父节点
- 比父节点小，插入到左边
- 比父节点大，插入到右边
bool insert(const K& val)
{
//若为空树
if (_root == nullptr)
{
_root = new Node(val);
return true;
}
//非空
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_key > val)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < val)
{
parent = cur;
cur = cur->_right;
}
else//相等了，插入失败
return false;
}
//cur位置就是要插入的位置
cur = new Node(val);
//判断插入到父节点的哪一边
if (parent->_key < val)
parent->_right = cur;
else
parent->_left = cur;
return true;
}
2.4二叉搜索树的遍历
由于二叉搜索树的特性，我们使用中序遍历出来的结果就是有序的，所以它也叫二叉排序树。
如果我们按照上述方式写，由于在类外面访问不到root，我们也就没有办法传递参数。所以我们可以给它套一层
public:
void InOrder()
{
_InOrder(_root);
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
2.5二叉搜索树的删除（重点）
首先查找元素是否在二叉搜索树中，如果不存在，则返回false, 否则要删除的结点可能分下面四种情况：
- a、要删除的节点为叶子节点（无孩子）
- b、要删除的节点只有左孩子
- c、要删除的节点只有右孩子
- d、要删除的节点左右孩子都有
所以，对于a情况，我们可以将其与b、c中任意一个进行合并
如果左右两个孩子都有怎么办呢？
我们要在树中找一个符合二叉树规则的数据去替代他
方法：在它的右子树中寻找一个最小的结点(或者在左子树中找一个最大的节点)，用它的值填补到被删除节点中，再来处理该结点的删除问题（最小的节点就是右树中最左下的节点）
如果我删除的是根节点呢?
总体的结构就是这样
细节如下：
bool erase(const K& val)
{
Node* cur = _root;
Node* parent = null;
while (cur)
{
//寻找要删除的位置
if (cur->_key < val)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > val)
{
parent = cur;
cur = cur->_left;
}
//cur->_key == val找到了要删除的位置
else
{
//只有左孩子或没孩子，父亲指向我的左
if (cur->_right == nullptr)
{
//如果删除根节点，新根就是我的左
if (cur == _root)//如果删除根节点，新根就是我的左
{
_root = cur->_left;
}
else
{
//判断插入到父节点的哪一边
if (parent->_left == cur)
parent->_left = cur->_left;
else
parent->_right = cur->_left;
}
delete cur;
}
//只有右孩子，父亲指向我的右
else if (cur->_left == nullptr)
{
//如果删除根节点，新根就是我的右
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)
parent->_left = cur->_right;
else
parent->_right = cur->_right;
}
delete cur;
}
//左右孩子都有
else
{
Node* rightMin = cur->_right;
Node* rightMinParent = cur;
//找右树的最小
while (rightMin->_left)
{
rightMinParent = rightMin;
rightMin = rightMin->_left;
}
swap(rightMin->_key, cur->_key);//替换
//判断连接在父亲的哪一边
if (rightMinParent->_left == rightMin)
rightMinParent->_left = rightMin->_right;
else
rightMinParent->_right = rightMin->_right;
delete rightMin;
}
return true;
}
}
return false;
}
3.二叉搜索树的应用
3.1K模型
K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
上述代码中所展现的就是K模型的样例，使用K模型查找可以使时间复杂度达到O(logN) (树不退化的前提下)
3.2KV模型
KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。
- 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；
- 再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。
改造K模式，使其变成KV模型：
对于KV模型来说，只需简单变动一下K模型即可。
- find函数：对于查找函数，它找到以后不再返回True，而是返回节点的指针
其余功能基本没有变化，仅仅是节点的值发生了变化
namespace KV
{
template<class K,class V>
struct BSTNode
{
K _key;
V _value;
BSTNode<K,V>* _left;
BSTNode<K,V>* _right;
BSTNode(const K& key = K(),const V& val = V())
:_key(key)
,_value(val)
, _left(nullptr)
, _right(nullptr)
{}
};
template<class K,class V>
class BSTree
{
typedef BSTNode<K,V> Node;//节点重命名
public:
BSTree()
:_root(nullptr)
{}
//析构
~BSTree()
{
Destroy(_root);
}
void Destroy(Node* root)
{
if (root == nullptr)
return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
bool insert(const K& key, const V& val)
{
//若为空树
if (_root == nullptr)
{
_root = new Node(key,val);
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位置就是要插入的位置
cur = new Node(key,val);
//判断插入到父节点的哪一边
if (parent->_key < key)
parent->_right = cur;
else
parent->_left = cur;
return true;
}
Node* find(const K& val)
{
Node* cur = _root;
while (cur)
{
if (cur->_key < val)
cur = cur->_right;
else if (cur->_key > val)
cur = cur->_left;
else
return cur;
}
return nullptr;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
bool erase(const K& val)
{
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
//寻找要删除的位置
if (cur->_key < val)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > val)
{
parent = cur;
cur = cur->_left;
}
//cur->_key == val找到了要删除的位置
else
{
//只有左孩子或没孩子，父亲指向我的左
if (cur->_right == nullptr)
{
//如果删除根节点，新根就是我的左
if (cur == _root)//如果删除根节点，新根就是我的左
{
_root = cur->_left;
}
else
{
//判断插入到父节点的哪一边
if (parent->_left == cur)
parent->_left = cur->_left;
else
parent->_right = cur->_left;
}
delete cur;
}
//只有右孩子，父亲指向我的右
else if (cur->_left == nullptr)
{
//如果删除根节点，新根就是我的右
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)
parent->_left = cur->_right;
else
parent->_right = cur->_right;
}
delete cur;
}
//左右孩子都有
else
{
Node* rightMin = cur->_right;
Node* rightMinParent = cur;
//找右树的最小
while (rightMin->_left)
{
rightMinParent = rightMin;
rightMin = rightMin->_left;
}
swap(rightMin->_key, cur->_key);//替换
//判断连接在父亲的哪一边
if (rightMinParent->_left == rightMin)
rightMinParent->_left = rightMin->_right;
else
rightMinParent->_right = rightMin->_right;
delete rightMin;
}
return true;
}
}
return false;
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_key << " " << root->_value<< endl;;
_InOrder(root->_right);
}
private:
Node* _root;
};
}
