目录
一、二叉搜索树
🍔二叉搜索树概念
二叉搜索树又称二叉排序树，具有以下性质：
1️⃣若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
2️⃣若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
3️⃣左右子树也分别为二叉搜索树
🍟二叉搜索树的操作
1️⃣二叉搜索树的查找：
a.从根开始比较，比根大就走右子树查找，比根小就走左子树查找
b.最多查找高度次，走到空如果没找到，这个值就不存在
2️⃣二叉搜索树的插入：
a.树为空，则直接新增节点，赋值给root指针
b.树不空，按二叉搜索树的性质查找插入位置，插入新节点
3️⃣二叉搜索树的删除：
首先查找元素是否存在，如果不存在，则直接返回，否则有下面4种情况
a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点
其中，情况a可以与情况b和情况c合并起来
🌮二叉搜索树的实现
template<class T> struct BSTNode { BSTNode(const T& data = T()) :_pleft(nullptr) ,_pright(nullptr) ,_data(data) {} BSTNode<T>* _pleft; BSTNode<T>* _pright; T _data; }; template<class T> class BSTree { typedef BSTNode<T> Node; typedef BSTNode<T>* pNode; public: BSTree() :_proot(nullptr) {} ~BSTree() { _delete(_proot); } //查找 pNode Find(const T& data) { if (_proot == nullptr) return nullptr; pNode cur = _proot; while (cur) { if (data < cur->_data) cur = cur->_pleft; else if (data > cur->_data) cur = cur->_pright; else return cur; } return cur; } //插入 bool Insert(const T& data) { //情况a if (_proot == nullptr) { _proot = new Node(data); return true; } pNode cur = _proot; pNode parent = nullptr; while (cur) { parent = cur; if (data < cur->_data) cur = cur->_pleft; else if (data > cur->_data) cur = cur->_pright; else return false; } //插入新元素 cur = new Node(data); if (data < parent->_data) parent->_pleft = cur; else parent->_pright = cur; return true; } //删除 bool Erase(const T& data) { //空树直接返回空 if (_proot == nullptr) return false; //只有一个节点 if (_proot->_data == data &&nullptr==_proot->_pleft&&nullptr==_proot->_pright) { delete _proot; _proot = nullptr; return true; } //找到删除位置 pNode cur = _proot; pNode parent = nullptr; while (cur) { if (data < cur->_data) { parent = cur; cur = cur->_pleft; } else if (data > cur->_data) { parent = cur; cur = cur->_pright; } else break; } //查找不到返回失败 if (nullptr == cur) return false; //分情况删除 //只有右节点 if (nullptr == cur->_pleft) { if (cur == parent->_pleft) parent->_pleft = cur->_pright; else parent->_pright = cur->_pright; delete cur; } //只有左节点 else if (nullptr == cur->_pright) { if (cur == parent->_pleft) parent->_pleft = cur->_pleft; else parent->_pright = cur->_pleft; delete cur; } else { //查找右子树中最小的节点(或左子树中最大的节点) pNode del = cur->_pright; parent = cur; while (del) { if (nullptr == del->_pleft) break; else { parent = del; del = del->_pleft; } } std::swap(cur->_data, del->_data); if (del == parent->_pleft) { if (nullptr != del->_pright) parent->_pleft = del->_pright; else parent->_pleft = nullptr; } else { if (nullptr != del->_pright) parent->_pright = del->_pright; else parent->_pright = nullptr; } delete del; } return true; } void Inorder() { _Inorder(_proot); } private: void _delete(pNode _root) { if (nullptr == _root) return; _delete(_root->_pleft); _delete(_root->_pright); delete _root; } void _Inorder(pNode root) { if (root == nullptr) return; _Inorder(root->_pleft); cout << root->_data << " "; _Inorder(root->_pright); } pNode _proot; };
🥪二叉搜索树的应用
🔥K模型：K模型即只有key作为关键码，结构中只需要存储Key即可
例如：给一个单词word，判断单词是否拼写正确，具体方式如下：
以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误
🔥KV模型：每一个关键码key，都有与之对应的值Value，即键值对
该种方式在现实生活中非常常见:比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文就构成一种键值对
💧代码改造为KV模型template<class K,class V> struct BSTNode { BSTNode(const K&key=K(),const V& value = V()) :_pleft(nullptr) ,_pright(nullptr) ,_key(key) ,_value(value) {} BSTNode<K, V>* _pleft; BSTNode<K, V>* _pright; K _key; V _value; }; template<class K,class V> class BSTree { typedef BSTNode<K, V> Node; typedef BSTNode<K, V>* pNode; public: BSTree() :_proot(nullptr) {} void Inorder() { _Inorder(_proot); } //查找 pNode Find(const K& key) { pNode cur = _proot; while (cur) { if (cur->_key == key) break; else if (cur->_key < key) cur = cur->_pright; else if (cur ->_key>key) cur = cur->_pleft; } return cur; } //插入 bool Insert(const K& key, const V& value) { if (nullptr == _proot) { pNode newNode = new Node(key, value); _proot = newNode; return true; } //找插入位置 pNode cur = _proot; pNode parent = nullptr; while (cur) { //跳过重复 if (cur->_key == key) return false; else if (cur->_key > key) { parent = cur; cur = cur->_pleft; } else { parent = cur; cur = cur->_pright; } } cur = new Node(key, value); if (key < parent->_key) { parent->_pleft = cur; } else { parent->_pright = cur; } return true; } //删除 bool Erase(const K& key) { //空树直接返回错误 if (_proot == nullptr) return false; //只有一个节点 if (_proot->_key == key && nullptr == _proot->_pleft && nullptr == _proot->_pright) { delete _proot; _proot = nullptr; return true; } //找到删除位置 pNode cur = _proot; pNode parent = nullptr; while (cur) { if(key < cur->_key) { parent = cur; cur = cur->_pleft; } else if (key > cur->_key) { parent = cur; cur = cur->_pright; } else break; } //查找不到返回失败 if (nullptr == cur) return false; //分情况删除 //只有右节点 if (nullptr == cur->_pleft) { if (cur == parent->_pleft) parent->_pleft = cur->_pright; else parent->_pright = cur->_pright; delete cur; } //只有左节点 else if (nullptr == cur->_pright) { if (cur == parent->_pleft) parent->_pleft = cur->_pleft; else parent->_pright = cur->_pleft; delete cur; } else { //查找右子树中最小的节点(或左子树中最大的节点) pNode del = cur->_pright; parent = cur; while (del) { if (nullptr == del->_pleft) break; else { parent = del; del = del->_pleft; } } std::swap(cur->_key, del->_key); std::swap(cur->_value, del->_value); if (del == parent->_pleft) { if (nullptr != del->_pright) parent->_pleft = del->_pright; else parent->_pleft = nullptr; } else { if (nullptr != del->_pright) parent->_pright = del->_pright; else parent->_pright = nullptr; } delete del; } return true; } private: void _Inorder(pNode root) { if (root == nullptr) return; _Inorder(root->_pleft); cout << root->_key << ":" << root->_value << " "; _Inorder(root->_pright); } pNode _proot; };
🥙二叉搜索树的效率分析
🔥插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入次序不同，可能得到不同结构的二叉搜索树：
最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)
最差情况下，二叉搜索树退化为单支树(或者类似单支)
二、结语
🫡你的点赞和关注是作者前进的动力！
🌞最后，作者主页有许多有趣的知识，欢迎大家关注作者，作者会持续更新有意思的代码，在有趣的玩意儿中成长！
