C++进阶(3): 二叉搜索树

二叉搜索树的概念

二叉搜索树又称二叉排序树，它或者是一颗空树，或者具有以下性质的二叉树：

若它的左子树不为空，则左子树上所有的节点的值都小于等于 根节点的值
若它的右子树不为空，则右子树上所有的节点的值都大于等于 根节点的值
它的左右子树也分别为二叉搜索树
二叉搜索树可以支持插入相同的值(multimap/multiset)，也可以不支持插入相等的值(map/set)

二叉搜索树的性能分析

最优的情况：二叉搜索树为完全二叉树(或者接近完全二叉树)，它的高度是：O(log2 N)
最坏的情况：二叉搜索树退化为单支树(类似于单支)，它的高度是：O(N/2)

所以综合而言二叉搜索树增删改时间复杂度是：O(N)
但是这样的效率显然无法满足我们的需求，后续的博客我将介绍二叉搜索树的变形，平衡二叉树AVL树和红黑树，才能适用于我们在内存在存储和搜索数据。

最好的情况
最坏的情况

二叉搜索树的插入

不用递归，采用更简单的循环

插入的具体步骤如下：

树为空，则直接新增节点，赋值给root指针
树不为空，按照二叉搜索树性质，插入值比当前节点大往右走，插入值比当前节点小往左走，找到空位置，插入新节点。
如果支持插入相同的值，插入值跟当前节点相等的值可以往右走，也可以往走左走，找到空位置，插入新节点(要注意保持逻辑的一致性，插入相同的值不要一会向右走，一会向左走)

二叉搜索树的查找

从根节点开始比较，查找x，x比根节点的值大则向右边走查找，x比根节点的值小则向左边走查找
最多查找高度次，走到空时，还没找到x，那么这个值在这个二叉搜索树中不存在
如果不支持插入相同的值，则找到x后可以直接返回
如果支持插入相同的值，则意味着可能存在多个x，一般要求查找中序的第一个x

二叉搜索树的删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回false
如果查找元素存在则分为以下四个情况进行分别处理：(假设要删除的节点为N)(分类依据：孩子的个数)

要删除的节点N左右孩子均为空(即N为叶子节点)
要删除的节点N左孩子为空，右孩子不为空
要删除的节点N左孩子不为空，右孩子为空
要删除的节点N左右孩子均不为空

对于以上四种情况的解决办法：

把N节点的父亲对应孩子指针指向空，直接删除N节点(1可以和2.3一起处理)
把N节点的父亲对应孩子指针指向N的右孩子，直接删除N节点
把N节点的父亲对应孩子指针指向N的左孩子，直接删除N节点
无法直接删除N节点，因为N的两个孩子无处安放，只能采用替代法将其删除：将N左子树的最大值的节点R(最右节点)或者N右子树的最小值的节点R(最左节点)代替N，因为这两个节点中任意一个，放到N的节点，都满足二叉搜索树的规则。代替N的意思就是N和R的两个节点的值交换，转而变成删除R节点，R节点符合情况2或者情况3，可以直接删除

实现代码

template<class K>struct BSTNode
{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(const K& key):_key(key), _left(nullptr), _right(nullptr){}
};//搜索二叉树：
template<class K>class BSTree
{typedef BSTNode<K> Node;public:bool Insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;//记录之前的数据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->_left = cur;}else{parent->_right = cur;}return true;}bool 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 true;}return false;}}bool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{if (nullptr == cur->_left){if (parent == nullptr){_root = cur->_right;}else{if (parent->_left == cur){parent->_left = cur->_right;}else if (parent->_right = cur){parent->_right = cur->_right;}}delete cur;return true;}else if (nullptr == cur->_right){if (nullptr == parent){_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;return true;}else{Node* leftMaxP = cur;Node* leftMax = cur->_left;while (leftMax->right){leftMaxP = leftMax;leftMax = leftMax->_right;}cur->_key = leftMax->_key;if (leftMaxP->_left == leftMax){leftMaxP->_left = leftMax->_left;}else{leftMaxP->_right = leftMax->_left;}delete leftMax;return true;}}}return false;}void InOrder(){_InOrder(_root);cout << endl;}
private:void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}private:Node* _root = nullptr;
};

二叉搜索树key和key/value使用场景

key搜索场景

只有key作为关键码，在二叉树结构中只需要存储key即可，搜索场景只需要判断key在不在。key的搜索场景支持二叉树的增删查，而不支持二叉树的修改，会破坏二叉树的结构。

key/value搜索场景

每一个关键码key，都有与它对应的值value，value可以是任何类型对象。树的结构中(每个节点)除了需要存储key，还需要存储value，增/删/查还是以key为关键字走二叉树的规则进行比较，可以快速找到与key对应的value。并且key/value的搜索场景支持了二叉树的修改，但是仍然不可以修改key，只可以修改value。

key/value二叉搜索树代码实现

	template<class K, class V>struct BSTNode{K _key;V _value;BSTNode<K, V>* _left;BSTNode<K, V>* _right;BSTNode(const K& key, const K& value):_key(key), _value(value), _left(nullptr), _right(nullptr){}};//搜索二叉树：template<class K, class V>class BSTree{typedef BSTNode<K, V> Node;public:BSTree() = default;BSTree(const BSTree<K, V>& m){_root = Copy(m._root);}BSTree<K, V>& operator=(BSTree<K, V> m){swap(_root, m._root);return *this;}~BSTree(){Destroy(_root);_root = nullptr;}bool Insert(const K& key, const V& value){if (_root == nullptr){_root = new Node(key, value);return true;}Node* parent = nullptr;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{parent->_left = cur;}return true;}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 nullptr;}bool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{if (nullptr == cur->_left){if (nullptr == parent){_root = cur->_right;}else{if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;return true;}else if (nullptr == cur->_right){if (nullptr == parent){_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;return true;}else{Node* rightMinP = cur;Node* rightMin = cur->_right;while (rightMin->_left){rightMinP = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;if (rightMinP->_left == rightMin){rightMinP->_left = rightMin->_right;}else{rightMinP->_right = rightMin->_right;}delete rightMin;return true;}}}return false;}void InOrder(){_InOrder(_root);cout << endl;}private:void _InOrder(Node* root){if (nullptr == root){return;}_InOrder(root->_left);cout << root->_key << ':' << root->_value << endl;_InOrder(root->right);}void Destroy(Node* root){if (root == nullptr){return;}Destroy(root->_left);Destroy(root->_right);delete root;}Node* Copy(Node* root){if (nullptr == root){return nullptr;}Node* newRoot = new Node(root->_key, root->_value);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}private:Node* _root = nullptr;};