【数据结构】二叉搜索树

 引入

当我们用有序数组储存数据时，查找某个数据可以用折半查找，时间复杂度为LogN；但是当我们要插入或删除数据时需要一步一步挪动数据，消耗非常大。为此引入了二叉搜索树这个数据结构。

二叉搜索树的规则

二叉搜索树又称二叉排序树，只要它不是空树，就满足一下规则：

1.若左子树不为空，则左子树上的所有节点值都小于等于根节点的值

2.若右子树不为空，则右子树上的所有节点值都大于等于根节点的值

3.它的左右子树也分别为二叉搜索树

4.二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看应用场景。

二叉搜索树的性能

最优情况下，二叉搜索树为完全二叉树，高度为log2N。

最差情况下，二叉树搜索树为单只树，高度为N。

所以综合来看，二叉搜索树的增删查改时间复杂度为：O(N)

这样的效率和数组相比优势不明显，无法满足我们的需求，后面将会学习 AVL和红黑树来解决效率问题。这两种二叉搜索树的增删查改的时间复杂度为：O(logN)。二分查找也能达到这个时间复杂度；为什么还要用二叉搜索树呢？这里就要提到能用二分查找的前提条件了：1.要保证有序2.要支持下标随机访问。而且用二分的结构大多在插入删除时需要挪动数据，消耗非常大。

二叉搜索树的插入

1.插入前树为空：
直接新增一个节点，赋值给root指针。

2.插入前树不为空：

插入值和当前节点值进行比较，比当前节点值小则与左子树值比较，为空时插入；比当前节点值大则与右子树值比较，为空时插入。

当插入值与当前节点值相等时，自由安排往左往右都可以；但是要注意逻辑连贯性，第一次往左了下次也得往左。

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->_right = cur;}else{parent->_left = cur;}return true;
}

二叉搜索树的查找

1.从根节点开始比较，查找x，比查找值大则往右走，反之往左走。

2.若最后找到空节点则未找到。

3.如果未支持插入相等值，找到第一个就返回

4.如果支持插入相等的值，那么可能存在多个要查找的x，返回中序的第一个x。

如果要查找3，找到第一个3后，继续向下查找，直至找到空节点，返回最后一个找到的值为3的节点，为中序的第一个节点。

代码实现：

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;}
}

二叉搜索树的删除

要删除二叉搜索树中的元素，首先要找到查找二叉搜索树中的元素，如果找不到，即不存在，返回false。因为一个节点有两个子节点，排列组合就有四种情况。

1.要删除的节点左右孩子都为空

这种情况最简单，直接删除就可以（把该节点的父节点指向此节点的路径指向空），不会影响整棵树的访问顺序。

2.节点左孩子为空，右孩子不为空

把父节点指向此节点的右孩子，直接删除此节点。

3.节点右孩子为空，左孩子不为空

把父节点指向左节点，直接删除该节点。

4.左右均不为空

这种情况最难处理，此节点的两个孩子要想办法安放。在讲堆和top-k问题时【数据结构】 -- 堆 （堆排序）（TOP-K问题）_高度为 k的二叉树最大的结点数为( )。-CSDN博客，我们插入一个元素，可以插入到末尾，然后再向上调整。其实这里有点类似这个的逆过程。

按照中序遍历，访问此节点前访问的元素时左子树中最大的元素，访问此节点后访问的第一个元素是右子树中最小的元素。用他俩中任意一个来替换此节点，中序遍历的结果都一样（具体用哪一个替换看自己喜好）。替换之后，此节点左右都为空，满足情况1，直接删除就好了。

bool Erase(const K& key){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//cur->_key == key{//左右至少有一个为空的情况，直接改变指向if (cur->_left == nullptr){if (parent == nullptr){_root = cur->_right;}else{if (parent->_left == cur)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;return true;}else if (cur->_right == nullptr){if (parent == nullptr){_root = cur->_left;}else{if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;}delete cur;return true;}else {//两个子树都有孩子的情况，用右子树最小或左子树最大来替换// ⼀定要把cur给rightMinP，否会报错。//注意右子树的第一个值就是最小值的情况Node* rightMinP = cur;Node* rightMin = cur->_right;while (rightMin->_left)//找出最左边的，就是右子树最小的{rightMinP = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;//把右子树中最小值替换到cur->_keyif (rightMinP->_left == rightMin)rightMinP->_left = rightMin->_right;else//右子树的第一个值就是最小值的情况rightMinP->_right = rightMin->_right;delete rightMin;return true;}}}return false;}

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

key搜索场景

一个节点只储存key这一个数据，这样实现的二叉搜索树只能实现增删查，不支持改动。

key/value搜索场景

每一个key,都有与之对应的值value，value可以是任意类型对象。树的结构中纪要储存key，也要储存value。这种二叉搜索树，还是按照key值来建立和搜索，key的值同样不能改变，但是value的值是可以改变的。就像按学号生成一个班级的二叉树，一个节点代表一个同学，就可以用这个节点的value记录该同学的成绩，每次考试成绩是可以改变的，value就更新。

代码实现：

#include<iostream>using namespace std;
#include<string>template < class K, class V>struct BSTNode{// pair<K, V> _kv;K _key;V _value;BSTNode<K, V>* _left;BSTNode<K, V>* _right;BSTNode(const K & key, const V & 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>& t){_root = Copy(t._root);}BSTree<K, V>& operator=(BSTree<K, V> t){swap(_root, t._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->_right;}else if (cur->_key > key){cur = cur->_left;}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->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{if (cur->_left == nullptr){if (parent == nullptr){_root = cur->_right;}else{if (parent->_left == cur)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;return true;}else if (cur->_right == nullptr){if (parent == nullptr){_root = cur->_left;}else{if (parent->_left == cur)parent->_left = cur->_left;elseparent->_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;elserightMinP->_right = rightMin->_right;delete rightMin;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 << ":" << 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 (root == nullptr)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;
};
//int main()
//{
//	BSTree<string, string> dict;
//	//BSTree<string, string> copy = dict;
//	dict.Insert("left", "左边");
//	dict.Insert("right", "右边");
//	dict.Insert("insert", "插⼊");
//	dict.Insert("string", "字符串");
//	string str;
//	while (cin >> str)
//	{
//		auto ret = dict.Find(str);
//		if (ret)
//		{
//			cout << "->" << ret->_value << endl;
//		}
//		else
//		{
//			cout << "无此单词，请重新输⼊" << endl;
//		}
//	}
//	return 0;
//}int main()
{string arr[] = { "蔡徐坤","陈立农","宋亚轩","范丞丞","黄明昊" };BSTree<string, int> countTree;for (const auto& str : arr){// 先查找idol在不在搜索树中// 1、不在，说明idol第⼀次出现，则插⼊<idol, 1>// 2、在，则查找到的结点中idol对应的次数++//BSTreeNode<string, int>* ret = countTree.Find(str);auto ret = countTree.Find(str);if (ret == NULL)countTree.Insert(str, 1);else{ret->_value++;}countTree.InOrder();return 0;}
}