二叉搜索树
1.关联式容器
根据“数据在容器中的排列”特性，容器分为序列式和关联式两种，前面我们已经讨论过序列式容器了，后面一段时间我们将讨论关联式容器。
标准的STL关联式容器分为 set（集合）和 map（映射表）两大类，以及这两大类的衍生体multiset（多键集合）和 multimap（多键映射表）。这些容器的底层机制均以 RB-tree（红黑树）完成。RB-tree 也是一个独立的容器，但并不开放给外界使用 ...
所谓的关联式容器，观念上类似关联式数据库：每笔数据（每个元素）都有一个键值（key）和实值（value）。当元素被插入到关联式容器中时，容器内部结构变异找其键值大小，以某种特定规则就按这个元素放置于适当位置。关联式容器没有所谓头尾（中有==只有最大元素和最小元素），所以不会有所谓push_back()、push_front()、pop_back()、pop_front()、begin()、end() 这样的行为操作。
一般情况下，关联式容器的内部结构是一个平衡二叉树，一以便获得良好的搜寻效率。
2.二叉搜索树
(1) 概念
(2) 二叉搜索树的性能分析
(3) 二叉搜索树的插入
1. 树为空，则直接新增结点，赋值给root指针2. 树不空，按二叉搜索树性质， 插入值比当前结点大往走，插入值比当前结点小往左走，找到空位置，插入新结点。3. 如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入 新结点。（要注意的是要保持逻辑一致性，插入相等的值不要一会往右走，一会往左走）
(4) 二叉搜索树的查找
(5) 二叉搜索树的删除
首先查找元素是否在二叉搜索树中，如果不存在，则返回false。如果查找元素存在则分以下四种情况分别处理：（假设要删除的结点为N）1. 要删除结点N左右孩子均为空2. 要删除的结点N左孩子位空，右孩子结点不为空3. 要删除的结点N右孩子位空，左孩子结点不为空4. 要删除的结点N左右孩子结点均不为空
对应以上四种情况的解决方案：1. 把N结点的父亲对应孩子指针指向空，直接删除N结点（情况1可以当成2或者3处理，效果是一样 的）
2. 把N结点的父亲对应孩子指针指向N的右孩子，直接删除N结点3. 把N结点的父亲对应孩子指针指向N的左孩子，直接删除N结点
4. 无法直接删除N结点，因为N的两个孩子无处安放，只能用替换法删除。找N左子树的值最大结点R(最右结点)或者N右子树的值最小结点R(最左结点)替代N，因为这两个结点中任意一个，放到N的位置，都满足二叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换，转而变成删除R结点，R结点符合情况2或情况3，可以直接删除。
(6) 二叉搜索树的代码实现
namespace zyt
{
// 节点
template <class K>
struct BSNode
{
K _key;
BSNode<K>* _left;
BSNode<K>* _right;
BSNode(const K& key)
:_key(key)
, _left(nullptr)
, _right(nullptr)
{}
};
template <class K>
struct BSTree
{
typedef BSNode<K> Node;
public:
bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
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);
if (parent->_key < key)
{
parent->_right = cur;
}
else if (parent->_key > key)
{
parent->_left = cur;
}
return true;
}
bool 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 true;
}
}
return false;
}
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 // 找到要删除的位置
{// 情况1
if (cur->_left == nullptr && cur->_right == nullptr)
{
if (parent->_left == cur)
parent->_left = nullptr;
if (parent->_right == cur)
parent->_right = nullptr;
delete cur;
return true;
}
else if (cur->_left == nullptr )
{
if (parent == _root)
{// 删除根节点的情况
_root = cur->_right;
}
else
{
if (parent->_left == cur)
parent->_left = cur->_right;
else
parent->_right = cur->_right;
delete cur;
return true;
}
}
else if (cur->_right == nullptr)
{
if (parent == _root)
{// 删除根节点的情况
_root = cur->_left;
}
else
{
if (parent->_left == cur)
parent->_left = cur->_left;
else
parent->_right = cur->_left;
delete cur;
return true;
}
}
else
{ // 新指针寻找左子树最大值
Node* newparent = cur;
Node* newcur = cur;
while (newcur->_right)// 找到左子树的最右节点
{
newparent = newcur;
newcur = newcur->_right;
}
cur->_key = newcur->_key;
if (newparent->_left == newcur)
newparent->_left = nullptr;
else
newparent->_right = nullptr;
delete newcur;
return true;
}
}
}
return false;
}
void InOrder()
{ // 封装一个函数方便外界调用
_InOreder(_root);
cout << endl;
}
private:
void _InOreder(Node* root)
{
if (root == nullptr)
return;
_InOreder(root->_left);
cout << root->_key << " ";
_InOreder(root->_right);
}
Node* _root = nullptr;
};
}3.key 和 key/value 使用
(1) key 使用场景
只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值，搜索场景只需要判断key在不在。key的搜索场景实现的二叉树搜索树支持增删查，但是不支持修改，修改key破坏搜索树结构了。
场景：检查一篇英文文章单词拼写是否正确，将词库中所有单词放入二叉搜索树，读取文章中的单 词，查找是否在二叉搜索树中，不在则波浪线标红提示。
(2) key / value 使用场景
每一个关键码key，都有与之对应的值value，value可以任意类型对象。树的结构中(结点)除了需要存 储key还要存储对应的value，增/删/查还是以key为关键字走⼆叉搜索树的规则进行比较，可以快速查 找到key对应的value。key/value的搜索场景实现的二叉树搜索树支持修改，但是不支持修改key，修 改key破坏搜索树结构了，可以修改value。
场景：简单中英互译字典，树的结构中(结点)存储key(英文)和vlaue(中文)，搜索时输入英文，则同时查找到了英文对应的中文。
(3) key/value二叉搜索树代码实现
namespace zyt1
{
// 节点
template <class K ,class V>
struct BSNode
{
K _key;
V _value;
BSNode<K,V>* _left;
BSNode<K,V>* _right;
BSNode(const K& key,const V& value)
:_key(key)
,_value(value)
, _left(nullptr)
, _right(nullptr)
{}
};
template <class K,class V>
struct BSTree
{
typedef BSNode<K,V> Node;
public:
bool Insert(const K& key, const V& value)
{
if (_root == nullptr)
{
_root = new Node(key,value);
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,value);
if (parent->_key < key)
{
parent->_right = cur;
}
else if (parent->_key > key)
{
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 // 找到要删除的位置
{// 情况1
if (cur->_left == nullptr && cur->_right == nullptr)
{
if (parent->_left == cur)
parent->_left = nullptr;
if (parent->_right == cur)
parent->_right = nullptr;
delete cur;
return true;
}
else if (cur->_left == nullptr)
{
if (parent == _root)
{// 删除根节点的情况
_root = cur->_right;
}
else
{
if (parent->_left == cur)
parent->_left = cur->_right;
else
parent->_right = cur->_right;
delete cur;
return true;
}
}
else if (cur->_right == nullptr)
{
if (parent == _root)
{// 删除根节点的情况
_root = cur->_left;
}
else
{
if (parent->_left == cur)
parent->_left = cur->_left;
else
parent->_right = cur->_left;
delete cur;
return true;
}
}
else
{ // 新指针寻找左子树最大值
Node* newparent = cur;
Node* newcur = cur;
while (newcur->_right)// 找到左子树的最右节点
{
newparent = newcur;
newcur = newcur->_right;
}
cur->_key = newcur->_key;
if (newparent->_left == newcur)
newparent->_left = nullptr;
else
newparent->_right = nullptr;
delete newcur;
return true;
}
}
}
return false;
}
BSTree() = default;// 强制生成
// 拷贝
BSTree(const BSTree<K, V>& t)
{
_root = Copy(t._root);
}
// 赋值
BSTree<K, V>& operator=(BSTree<K, V> t)
{
swap(_root, t.root);
return *this;
}
~BSTree()
{
Destory(_root);
_root = nullptr;
}
void Destory(Node* root)
{
if (root == nullptr)
return;
Destory(root->_left);
Destory(root->_right);
delete root;
}
// 构造
Node* Copy(Node* root)
{
if (root == nullptr)
return nullptr;
Node* newnode = new Node(root->_key, root->_value);
newnode->_left = Copy(root->_left);
newnode->_right = Copy(root->_right);
return newnode;
}
void InOrder()
{ // 封装一个函数方便外界调用
_InOreder(_root);
cout << endl;
}
private:
void _InOreder(Node* root)
{
if (root == nullptr)
return;
_InOreder(root->_left);
cout << root->_key << ":" << root->_value << endl;;
_InOreder(root->_right);
}
Node* _root = nullptr;
};
}原文地址：https://blog.csdn.net/2401_83431652/article/details/142591242
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！