引入

1.二叉搜索树的概念及优缺点

1.1二叉搜索树的概念

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

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

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

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

左子树的值<根的值<右子树的值

int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

搜索二叉树通过二分查找可以轻松找到目标值，避免了暴力遍历的方式。

根据搜索二叉树的性质，目标值会出现在左子树，右子树则是比目标值大的值。因此，搜索二叉树查找一个值的最坏情况只需要查找树的高度次 

既然提到了最坏情况，那么搜索二叉树的时间复杂度是多少呢？

搜索二叉树的增删查改的时间复杂度实际上是O（N），因为这棵树有可能会蜕化成一个 "单边树"(也就是只往一边存，另外一边没有节点)。

 1.2二叉搜索树的部分使用及其实现

 二叉搜索树的查找

//查找bool 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 true;}}//while循环走到头(遇到空节点)那就说明没找到return false;}

二叉搜索树的插入

插入的具体过程如下：

树为空，则直接新增节点，赋值给root指针

树不空，按二叉搜索树性质查找插入位置，插入新节点

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

二叉搜索树的删除

要删除的结点无孩子结点

要删除的结点只有左孩子结点

要删除的结点只有右孩子结点

要删除的结点有左、右孩子结点

删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除

如果原本4节点还有还记记得托付给其父节点 （由于替换法删除是取左子树的最右(右子树的最左)节点，所以哪怕4节点还有子节点，那也只能有一个)，比如：

	//删除bool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;//先找到要删的那个值while (cur){if (cur->_key < key){//cur走parent也要走parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{//找到了，准备删除//要删除的节点的左孩子节点为空if (cur->_left == nullptr){if (cur == _root){//要删的值在根节点，那直接把根节点给右节点就行了(左为空嘛)_root = cur->_right;}else{if (cur == parent->_right){//cur左孩子节点为空，若cur在其父节点的右边，那么其右孩子一定大于cur的父节点//右边托付parent->_right = cur->_right;}else{//左边托付parent->_left = cur->_right;}}//托付完删除delete cur;return true;}//要删除的节点的右孩子节点为空else if(cur->_right == nullptr){if (cur == _root){//要删的值在根节点，那直接把根节点给左节点就行了_root = cur->_left;}else{if (cur == parent->_right){//若cur在其父节点的右边，那么其左孩子一定大于于cur的父节点parent->_right = cur->_left;}else{//左边托付parent->_left = cur->_left;}}//托付完删除delete cur;return true;}else{//cur左右都非空Node* rightMin = cur->_right;//右边最小节点Node* rightMinParent = cur;//右边最小节点的父节点//找右边的最小节点while (rightMin->_left){rightMinParent = rightMin;rightMin = rightMin->_left;}//找到就替换一下cur->_key = rightMin->_key;//最小节点的孩子得判断是rightMin父亲的哪一边接收if (rightMin == rightMinParent->_left){rightMinParent->_left = rightMin->_right;}else{rightMinParent->_right = rightMin->_right;}delete rightMin;return true;}}}//找不到return false;}

 2.二叉搜索树的实现

2.1上述补充

节点

template<class K>
struct BSTreeNode
{typedef BSTreeNode<K> Node;Node* _left;Node* _right;K _key;BSTreeNode(const K& key):_left(nullptr),_right(nullptr),_key(key){}
};

二叉树的 

template<class K>
struct BSTree
{typedef BSTreeNode<K> Node;
public://强制生成默认构造BSTree() = default;BSTree(const BSTree<K>& t){_root = Copy(t._root);}Node* Copy(Node* root)//前序遍历构造(生成){if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_key);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);}BSTree<K>& operator=(BSTree<K> t){swap(_root, t._root);return *this;}~BSTree(){Destroy(_root);}void Destroy(Node* root)//后序遍历析构(销毁){if (root == nullptr){return;}Destroy(root->_left);Destroy(root->_right);delete root;}private:Node* _root = nullptr;
};

2.2查找、插入、删除递归实现

查找递归

因为无法传递根节点，所以要封装一层。

bool FindR(const K& key){return _FindR(_root, key);}bool _FindR(Node* root, const K& key){if (root == nullptr)return false;if (root->_key < key){return _FindR(root->_right, key);}else if (root->_key > key){return _FindR(root->_left, key);}else{return true;

插入递归

注意：插入的值如何与父节点连接

可以在传(递归)的根节点上加引用，这样每深入一层，那么这层的root就是上一场root->left(right)的引用，也就是说最后一层他会自动连接新节点

	bool InsertR(const K& key){return _InsertR(_root, key);}bool _InsertR(Node*& root, const K& key){if (root == nullptr){root = new Node(key);return true;}if (root->_key < key){return _InsertR(root->_right, key);}else if (root->_key > key){return _InsertR(root->_left, key);}else{return false;}}

删除递归

这里的引用和上面一样

	bool EraseR(const K& key){return _EraseR(_root, key);}bool _EraseR(Node*& root, const K& key){if (root == nullptr)return false;if (root->_key < key){return _EraseR(root->_right, key);}else if (root->_key > key){return _EraseR(root->_left, key);}else{Node* del = root;if (root->_right == nullptr){root = root->_left;}else if (root->_left == nullptr){root = root->_right;}else{Node* rightMin = root->_right;while (rightMin->_left){rightMin = rightMin->_left;}swap(root->_key, rightMin->_key);return _EraseR(root->_right, key);}delete del;return true;}}

3. 搜索二叉树的应用

3.1K模型

3.2kv模型