【C++】二叉搜索树

一、二叉搜索树

🍔二叉搜索树概念

🍟二叉搜索树的操作

🌮二叉搜索树的实现

🥪二叉搜索树的应用

🥙二叉搜索树的效率分析

二、结语

一、二叉搜索树

🍔二叉搜索树概念

二叉搜索树又称二叉排序树，具有以下性质：

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;elsereturn cur;}return cur;}//插入bool Insert(const T& data){//情况aif (_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;elsereturn false;}//插入新元素cur  = new Node(data);if (data < parent->_data)parent->_pleft = cur;elseparent->_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;}elsebreak;}//查找不到返回失败if (nullptr == cur)return false;//分情况删除//只有右节点if (nullptr == cur->_pleft){if (cur == parent->_pleft)parent->_pleft = cur->_pright;elseparent->_pright = cur->_pright;delete cur;}//只有左节点else if (nullptr == cur->_pright){if (cur == parent->_pleft)parent->_pleft = cur->_pleft;elseparent->_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;elseparent->_pleft = nullptr;}else{if (nullptr != del->_pright)parent->_pright = del->_pright;elseparent->_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;}elsebreak;}//查找不到返回失败if (nullptr == cur)return false;//分情况删除//只有右节点if (nullptr == cur->_pleft){if (cur == parent->_pleft)parent->_pleft = cur->_pright;elseparent->_pright = cur->_pright;delete cur;}//只有左节点else if (nullptr == cur->_pright){if (cur == parent->_pleft)parent->_pleft = cur->_pleft;elseparent->_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;elseparent->_pleft = nullptr;}else{if (nullptr != del->_pright)parent->_pright = del->_pright;elseparent->_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个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。

但对于同一个关键码集合，如果各关键码插入次序不同，可能得到不同结构的二叉搜索树：

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)

最差情况下，二叉搜索树退化为单支树(或者类似单支)