阅读量:2
目录
🌈前言🌈
欢迎观看本期博文，这期内容讲解二叉搜索树，包括了什么是二叉搜索树，如何实现二叉搜索树，以及二叉搜索树的应用，此外还会分析二叉搜索树的性能。
在二叉搜索树应用中，会包含K模型，对应的是STL中set容器;KV模型，对应的是STL中的map容器。
📁 二叉搜索树的概念
二叉搜索树又称为二叉排序树，它或是一颗空树，或者具有以下性质的二叉树：
1. 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值。
2. 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值。
3. 它的左右子树也称为二叉搜索树。
📁 二叉搜索树的操作
📂 二叉搜索树的查找
1. 从根开始比较查找，比根大的往右查找，比根小的往左边查找。
2. 最多查找高度次，走到为空，还没找到，则这个值不存在。
📂 二叉搜索树的插入
1. 树为空，则直接新增节点，赋值给root指针。
2. 树不为空，按二叉搜索树性质查找插入位置，插入新节点。
📂 二叉搜书树的删除
首先查找元素是否在二叉搜索树总，如果不存在，则返回，否则要删除的节点可能分为下面四种情况：
1. 要删除的节点无孩子节点
2. 要删除的节点只有左孩子节点
3. 要删除的节点只有右孩子节点
4. 要删除的节点有左右孩子节点。
开起来有四种情况，实际情况1可以与情况2或者3结合起来，因此真正的删除过程如下：
情况A：删除该节点且使被删除节点的双亲节点指向被删除节点的左孩子节点 --> 直接删除。
情况B：删除该节点且使被删除节点的双亲节点指向被删除节点的右孩子节点--> 直接删除。
情况C：在它的右子树中寻找中序心爱的第一个节点（Key值最小），用它的值填补被删除节点中，再来处理该节点的删除问题 ---> 替换法删除。
📁 二叉搜索树的应用
1. K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到 的值。 比如：给一个单词word，判断该单词是否拼写正确，具体方式如下： 以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
2. KV模型：每一个关键码key，都有与之对应的值Value，即的键值对。该种方 式在现实生活中非常常见： 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英 文单词与其对应的中文就构成一种键值对； 再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出 现次数就是就构成一种键值对。
📁 二叉搜索树的实现
1. K模型：
template <class K> struct BSTreeNode { BSTreeNode(K key) : _key(key),_left(nullptr), _right(nullptr) {} K _key; BSTreeNode* _left; BSTreeNode* _right; }; template<class K> class BSTree { typedef BSTreeNode<K> Node; void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); } public: //插入 bool Insert(K key) { if (_root == nullptr) { _root = new Node(key); return true; } Node* cur = _root; Node* parent = cur; while (cur) { if (cur->_key > key) { parent = cur; cur = cur->_left; } else if (cur->_key < key) { parent = cur; cur = cur->_right; } else { return false; } } if (key > parent->_key) { cur = new Node(key); parent->_right = cur; } else { cur = new Node(key); parent->_left = cur; } return true; } //删除 bool Erase(const K& key) { Node* cur = _root; Node* parent = _root; while (cur) { if (cur->_key > key) { parent = cur; cur = cur->_left; } else if (cur->_key < key) { parent = cur; cur = cur->_right; } else { if (cur->_right == nullptr) { if (cur == _root) { _root = cur->_left; } else { if (cur == parent->_left) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } } delete cur; } else if (cur->_left == nullptr) { if (cur == _root) { _root = cur->_right; } else { if (cur == parent->_left) { 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(RightMin == RightMinParent->_left) RightMinParent->_left = RightMin->_right; else RightMinParent->_right = RightMin->_right; delete RightMin; } return true; } } return false; } //查找 Node* Find(const K& key) { Node* cur = _root; while (cur) { if (cur->_key > key) { cur = cur->_left; } else if (cur->_key < key) { cur = cur->_right; } else { cout << cur->_key << endl; return cur; } } cout << "Not Find" << endl; return cur; } //遍历 void InOrder() { _InOrder(_root); cout << endl; } protected: Node* _root = nullptr; }; 2. KV模型：
template <class K,class V> struct BSTreeNode { BSTreeNode(K key, V val) : _key(key), _value(val), _left(nullptr), _right(nullptr) {} K _key; V _value; BSTreeNode* _left; BSTreeNode* _right; }; template<class K,class V> class BSTree { typedef BSTreeNode<K,V> Node; void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_key << ":" << root->_value << endl; _InOrder(root->_right); } public: //插入 bool Insert(const K& key,const V& val) { if (_root == nullptr) { _root = new Node(key,val); return true; } Node* cur = _root; Node* parent = cur; while (cur) { if (cur->_key > key) { parent = cur; cur = cur->_left; } else if (cur->_key < key) { parent = cur; cur = cur->_right; } else { return false; } } if (key > parent->_key) { cur = new Node(key,val); parent->_right = cur; } else { cur = new Node(key,val); parent->_left = cur; } return true; } //删除 bool Erase(const K& key) { Node* cur = _root; Node* parent = _root; while (cur) { if (cur->_key > key) { parent = cur; cur = cur->_left; } else if (cur->_key < key) { parent = cur; cur = cur->_right; } else { if (cur->_right == nullptr) { if (cur == _root) { _root = cur->_left; } else { if (cur == parent->_left) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } } delete cur; } else if (cur->_left == nullptr) { if (cur == _root) { _root = cur->_right; } else { if (cur == parent->_left) { 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 (RightMin == RightMinParent->_left) RightMinParent->_left = RightMin->_right; else RightMinParent->_right = RightMin->_right; delete RightMin; } return true; } } return false; } //查找 Node* Find(const K& key) { Node* cur = _root; while (cur) { if (cur->_key > key) { cur = cur->_left; } else if (cur->_key < key) { cur = cur->_right; } else { return cur; } } return cur; } //遍历 void InOrder() { _InOrder(_root); cout << endl; } protected: Node* _root = nullptr; };📁 二叉搜索树的性能分析
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二 叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：log_2 N 最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：N
问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插 入关键码，二叉搜索树的性能都能达到最优？那么我们后续章节学习的AVL树和红黑树就可以上场了。
📁 总结
以上就是二叉搜索树的所有内容了，讲解了什么是二叉搜索树，二叉搜索树的操作，如何实现二叉搜索树，以及二叉搜索树的应用，K模模型，对应的是STL中的set，KV模型，对应的是map容器。掌握了二叉搜索树，方便日后我们更好的学习ALV树，红黑树。
如果感觉本期内容对你有帮助，欢迎点赞，关注，收藏Thanks♪(･ω･)ﾉ
