欢迎来到本期节目- - -
二叉搜索树(去重版)
二叉搜索树的概念
定义：
| 对于该树的任意非空节点的值，左子树上所有节点的值小于等于给该节点，右子树所有节点的值大于等于该节点； |
| 任意节点的左右子树都为二叉搜索树； |
二叉搜索树不支持修改key值，否则会破会搜索树结构；
性能：
需要从两种极端情况综合来看；
-
理想情况：
一颗二叉搜索树的最佳情况是一颗完全二叉树或者接近完全二叉树；此时，高度为logN
二叉搜索树的插入、删除、查找效率为Ο(logN) -
最差情况：
此时退化成了单支树，高度为N
二叉搜索树的插入、删除、查找效率为Ο(N)
在实际运用中，很少机率是最佳情况，所以综合来看，二叉搜索树的增、删、查的效率是O(N).
二叉搜索树的插入
逻辑过程：
向一颗二叉搜索树tree插入一个节点Node;
如果tree是空树，则Node为根，插入成功；
如果tree是非空树，那么需要知道在哪插入；
- 可以给两个指针cur和parent，cur从tree的根开始，parent记录cur的父亲节点；
- 如果cur的key值小于Node的key值，让cur往右子树走；
- 如果cur的key值大于Node的key值，让cur往左子树走；
- 如果等于，插入失败；
- 直到cur走到空为止，然后parent连接Node节点，插入成功；
动图演示：
代码实操：
public:bool Insert(const K& key,const V& val){BSTNode* node = new BSTNode(key, val);if (_root == nullptr){_root = node;return true;}else{BSTNode* cur = _root;BSTNode* parent = nullptr;while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}else{return false;}}if (key > parent->_key){parent->_right = node;}else{parent->_left = node;}return true;}}
二叉搜索树的删除
逻辑过程：
在一颗二叉搜索树tree中删除一个节点Node;
如果tree为空树，删除失败;
如果tree为非空树，依据key寻找对应删除节点；
用cur记录当前节点，parent记录cur的父亲；
如果没找到，删除失败；
如果找到了：
-
1.目标节点cur的左右子树都为空；
那么直接删除cur，让parent指向nullptr; -
2.目标节点cur只有一个左子树；
该节点cur的右子树为空，左子树不为空，依据搜索树规则有：
cur如果在parent的左子树，说明cur的左子树也在parent左边，则cur的左子树小于parent，让cur的左子树做parent的左子树；
cur如果在parent的右子树，说明cur的左子树也在parent右边，则cur的左子树大于parent，让cur的左子树做parent的右子树； -
3.目标节点cur只有一个右子树；
和上一情况类似； -
4.目标节点cur左右子树都不为空；
该节点cur的左右子树均不为空，则需要使用替换法；
将cur的左子树的最右节点或者右子树的最左节点替换cur；
这样既保持了二叉搜索树结构，也把删除问题转换为了上述情况，因为最左节点的左子树一定为空；最右节点的右子树一定为空；
总的来说，可以把1,2,3情况归为一类，将4转换为上述的一类情况；
动图演示：
代码实操：
public:bool Erase(const K& key){BSTNode* parent = nullptr;BSTNode* cur = _root;while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}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;return true;}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;return true;}BSTNode* replacement = cur;BSTNode* replaceparent = cur->_right;while (replacement->_left){replaceparent = replacement;replacement = replacement->_left;}cur->_key = replacement->_key;cur->_val = replacement->_val;if (replaceparent->_left == replacement){replaceparent->_left = replacement->_right;}else{replaceparent->_right = replacement->_right;}delete replacement;return true;}}return false;}
二叉搜索树的查找
逻辑过程：
在一颗二叉搜索树tree中查找一个节点Node;
如果tree为空，则查找失败；
如果tree为非空；
- 给cur记录当前节点，parent记录cur的父亲节点；
- 如果cur的key值小于Node的key值，让cur往右子树走；
- 如果cur的key值大于Node的key值，让cur往左子树走；
- 如果等于，查找成功；
- 如果cur走到空节点，查找失败；
查找和插入类似，所以不做动图演示了；
代码实操：
public:BSTNode* Find(const K& key){BSTNode* cur = _root;while (cur){if (key > cur->_key){cur = cur->_right;}else if (key < cur->_key){cur = cur->_left;}else{return cur;}}return nullptr;}
二叉搜索树的遍历
逻辑过程：
二叉搜索树最明显的特征就是中序遍历的结果是递增；
遇到根先打印左子树，然后再打印根，然后再打印右子树；
动图演示：
private:void _Inorder(BSTNode* _root){if (_root){_Inorder(_root->_left);cout << _root->_key << ":" << _root->_val << endl;_Inorder(_root->_right);}}
二叉搜索树的实现
#pragma once
#include<iostream>
#include<string>
using namespace std;template<class K, class V>
class BSTNode
{
public:K _key;V _val;BSTNode<K, V>* _left;BSTNode<K, V>* _right;BSTNode(const K& key = K(), const V& val = V()){_key = key;_val = val;_left = _right = nullptr;}
};template<class K,class V>
class BSTree
{typedef BSTNode<K, V> BSTNode;
public:BSTree() = default;BSTree(const BSTree& tree){_root = copy(tree._root);}BSTree& operator=(BSTree tree){std::swap(_root, tree._root);return *this;}bool Insert(const K& key,const V& val){BSTNode* node = new BSTNode(key, val);if (_root == nullptr){_root = node;return true;}else{BSTNode* cur = _root;BSTNode* parent = nullptr;while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}else{return false;}}if (key > parent->_key){parent->_right = node;}else{parent->_left = node;}return true;}}bool Erase(const K& key){BSTNode* parent = nullptr;BSTNode* cur = _root;while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}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;return true;}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;return true;}BSTNode* replacement = cur;BSTNode* replaceparent = cur->_right;while (replacement->_left){replaceparent = replacement;replacement = replacement->_left;}cur->_key = replacement->_key;cur->_val = replacement->_val;if (replaceparent->_left == replacement){replaceparent->_left = replacement->_right;}else{replaceparent->_right = replacement->_right;}delete replacement;return true;}}return false;}BSTNode* Find(const K& key){BSTNode* cur = _root;while (cur){if (key > cur->_key){cur = cur->_right;}else if (key < cur->_key){cur = cur->_left;}else{return cur;}}return nullptr;}void Inorder(){_Inorder(_root);}~BSTree(){_destory(_root);_root = nullptr;}
private:BSTNode* _root = nullptr;void _Inorder(BSTNode* _root){if (_root){_Inorder(_root->_left);cout << _root->_key << ":" << _root->_val << endl;_Inorder(_root->_right);}}void _destory(BSTNode* _root){if (_root){_destory(_root->_left);_destory(_root->_right);delete _root;}}BSTNode* copy(BSTNode* _root){if (_root == nullptr)return nullptr;BSTNode* newroot = new BSTNode(_root->_key, _root->_val);newroot->_left = copy(_root->_left);newroot->_right = copy(_root->_right);return newroot;}
};
希望本片文章对您有帮助，请点赞支持一下吧😘💕