二叉搜索树(Binary Search Tree)

1.二叉搜索树概念

二叉搜索树又称二叉排序树、二叉查找树，它或者是一棵空树，或者是具有以下性质的二叉树:
1. 非空左子树的所有键值小于其根节点的键值
2. 非空右子树的所有键值大于其根节点的键值
3. 左右子树也分别为二叉搜索树

二叉搜索树一般不支持key值冗余（不允许有重复的key值）
二叉搜索树的性质使搜索时非常方便高效，最多搜索高度次O(log N)（二叉树退化为O(N)，需要二叉搜索树平衡，使用AVL树或红黑树）
二叉搜索树的中序遍历能对key进行排序

二叉搜索树的应用：
K模型：K模型只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值
例如查找某个key值存不存在？
KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对
key值不能冗余，但value值可以相同
例如key值为单词，value为对应单词的英文

 2.二叉搜索树操作（K模型为例）

2.1 二叉搜索树的查找

1. 从根节点开始查找，查找的key比cur(当前节点)的key大，则cur向右查找；查找的key比cur的key小，则cur向左查找，直到找到key值相同或查找的key值不存在。
2. 最多查找高度次，cur走到空，就说明查找的key不存在。

Node* find(const T& data)
{Node* cur = _root;while (cur){//找到返回if (data == cur->_data)return cur;//大于cur，向右找else if (data > cur->_data)cur = cur->_right;//小于cur，向左找elsecur = cur->_left;}//没找到return nullptr;return nullptr;
}

 2.2 二叉搜索树的插入

1. 树为空树时，则直接新增节点，并作为该对象的根节点(_root)。
2. 树不为空树时，按二叉树的性质查找位置并插入

bool insert(const T& data)
{//树为空if (_root == nullptr){_root = new Node(data);return true;}//树不为空Node* cur = _root;Node* parent = nullptr;while (cur){if (data > cur->_data){parent = cur;cur = cur->_right;}else if (data < cur->_data){parent = cur;cur = cur->_left;}else//树中已经存在return false;}//插入cur = new Node(data);if (data > parent->_data)parent->_right = cur;elseparent->_left = cur;return true;
}

 2.3 二叉搜索树的删除

查找元素是否在二叉搜索树中，如果不存在，则返回，否则要删除的节点分四种情况：
1. 要删除的节点无孩子节点 -- 直接删除该节点
2. 要删除的节点只有左孩子节点 -- 让左孩子节点替代该节点位置，并删除该节点
3. 要删除的节点只有右孩子节点 -- 让右孩子节点替代该节点位置，并删除该节点
4. 要删除的节点有左右孩子节点 -- 由二叉树性质，查找删除节点的右子树key值最小节点，让最小节点的key覆盖掉删除节点的key，最小节点一定是只有一个右孩子节点或没有孩子节点的情况，按1或2删除最小节点。（最小节点不可能存在左孩子，不然就不是最小节点了，更不可能有两个孩子）

bool erase(const T& data)
{//空树，删除失败if (_root == nullptr)return false;Node* cur = _root;Node* parent = nullptr;while (cur){if (data > cur->_data){parent = cur;cur = cur->_right;}else if (data < cur->_data){parent = cur;cur = cur->_left;}else//此时cur就是需要删除都节点break;}//不存在if (cur == nullptr)return false;//存在if (cur->_left == nullptr){//cur是根节点if (parent == nullptr)_root = cur->_right;else{if (cur == parent->_left)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;return true;}else if (cur->_right == nullptr){//cur是根节点if (parent == nullptr)_root = cur->_left;else{if (cur == parent->_left)parent->_left = cur->_left;else if (cur == parent->_right)parent->_right = cur->_left;}delete cur;return true;}//删除节点有两个孩子节点else{Node* minNode = cur->_right;Node* minNodeParent = cur;while (minNode->_left != nullptr){//最左就是最小节点minNodeParent = minNode;minNode = minNode->_left;}//修改_datacur->_data = minNode->_data;//删除minNodeif (minNodeParent->_left == minNode)minNodeParent->_left = minNode->_right;else//注意这个情况minNodeParent->_right = minNode->_right;delete minNode;return true;}
}

2.4 二叉搜索树代码（K模型和KV模型）

KV模型与K模型类似，只是KV模型的data类型是pair类型，first是key，second是value。

K模型：

namespace myBSTree_K
{template <class T>struct BSTNode{BSTNode(const T& data = T()):_left(nullptr), _right(nullptr), _data(data){}BSTNode<T>* _left;BSTNode<T>* _right;T _data;};template <class T>class BSTree{typedef BSTNode<T> Node;public:BSTree():_root(nullptr){}BSTree(const BSTree& tree){_root = _Copy(tree._root);}//析构函数无法传参，只能调用子函数进行递归销毁~BSTree(){//后序遍历销毁_destory(_root);_root = nullptr;}Node* find(const T& data){Node* cur = _root;while (cur){//找到返回if (data == cur->_data)return cur;//大于cur，向右找else if (data > cur->_data)cur = cur->_right;//小于cur，向左找elsecur = cur->_left;}//没找到return nullptr;return nullptr;}bool insert(const T& data){//树为空if (_root == nullptr){_root = new Node(data);return true;}//树不为空Node* cur = _root;Node* parent = nullptr;while (cur){if (data > cur->_data){parent = cur;cur = cur->_right;}else if (data < cur->_data){parent = cur;cur = cur->_left;}else//树中已经存在return false;}//插入cur = new Node(data);if (data > parent->_data)parent->_right = cur;elseparent->_left = cur;return true;}bool erase(const T& data){//空树，删除失败if (_root == nullptr)return false;Node* cur = _root;Node* parent = nullptr;while (cur){if (data > cur->_data){parent = cur;cur = cur->_right;}else if (data < cur->_data){parent = cur;cur = cur->_left;}else//此时cur就是需要删除都节点break;}//不存在if (cur == nullptr)return false;//存在if (cur->_left == nullptr){//cur是根节点if (parent == nullptr)_root = cur->_right;else{if (cur == parent->_left)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;return true;}else if (cur->_right == nullptr){//cur是根节点if (parent == nullptr)_root = cur->_left;else{if (cur == parent->_left)parent->_left = cur->_left;else if (cur == parent->_right)parent->_right = cur->_left;}delete cur;return true;}//删除节点有两个孩子节点else{Node* minNode = cur->_right;Node* minNodeParent = cur;while (minNode->_left != nullptr){//最左就是最小节点minNodeParent = minNode;minNode = minNode->_left;}//修改_datacur->_data = minNode->_data;//删除minNodeif (minNodeParent->_left == minNode)minNodeParent->_left = minNode->_right;else//注意这个情况minNodeParent->_right = minNode->_right;delete minNode;return true;}}void InOrder(){_InOrder(_root);}private:void _destory(Node* root){if (root == nullptr){return;}_destory(root->_left);_destory(root->_right);delete root;root = nullptr;}Node* _Copy(const Node* root){if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_data);newRoot->_left = _Copy(root->_left);newRoot->_right = _Copy(root->_right);return newRoot;}//中序遍历void _InOrder(const Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_data << ' ';_InOrder(root->_right);}//成员变量Node* _root;};
}

KV模型：

namespace myBSTree_KV
{template <class K, class V>struct BSTNode{BSTNode(const pair<K,V>& data = pair<K,V>()):_left(nullptr), _right(nullptr), _data(data){}BSTNode<K,V>* _left;BSTNode<K,V>* _right;pair<K,V> _data;};template <class K, class V>class BSTree{typedef BSTNode<K,V> Node;public:BSTree():_root(nullptr){}BSTree(const BSTree& tree){_root = _Copy(tree._root);}//析构函数无法传参，只能调用子函数进行递归销毁~BSTree(){//后序遍历销毁_destory(_root);_root = nullptr;}Node* find(const K& key){Node* cur = _root;while (cur){//找到返回if (key == cur->_data.first)return cur;//大于cur，向右找else if (key > cur->_data.first)cur = cur->_right;//小于cur，向左找elsecur = cur->_left;}//没找到return nullptr;return nullptr;}bool insert(const pair<K, V>& data){//树为空if (_root == nullptr){_root = new Node(data);return true;}//树不为空Node* cur = _root;Node* parent = nullptr;while (cur){if (data.first > cur->_data.first){parent = cur;cur = cur->_right;}else if (data.first < cur->_data.first){parent = cur;cur = cur->_left;}else//树中已经存在return false;}//插入cur = new Node(data);if (data.first > parent->_data.first)parent->_right = cur;elseparent->_left = cur;return true;}bool erase(const K& key){//空树，删除失败if (_root == nullptr)return false;Node* cur = _root;Node* parent = nullptr;while (cur){if (key> cur->_data.first){parent = cur;cur = cur->_right;}else if (key < cur->_data.first){parent = cur;cur = cur->_left;}else//此时cur就是需要删除都节点break;}//不存在if (cur == nullptr)return false;//存在if (cur->_left == nullptr){//cur是根节点if (parent == nullptr)_root = cur->_right;else{if (cur == parent->_left)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;return true;}else if (cur->_right == nullptr){//cur是根节点if (parent == nullptr)_root = cur->_left;else{if (cur == parent->_left)parent->_left = cur->_left;else if (cur == parent->_right)parent->_right = cur->_left;}delete cur;return true;}//删除节点有两个孩子节点else{Node* minNode = cur->_right;Node* minNodeParent = cur;while (minNode->_left != nullptr){//最左就是最小节点minNodeParent = minNode;minNode = minNode->_left;}//修改_datacur->_data = minNode->_data;//删除minNodeif (minNodeParent->_left == minNode)minNodeParent->_left = minNode->_right;else//注意这个情况minNodeParent->_right = minNode->_right;delete minNode;return true;}}//改--如果key相同，改value，如果key不存在，不改bool update(const pair<K, V>& data){Node* cur = find(data.first);if (cur == nullptr)return false;else{cur->_data.second = data.second;return true;}}void InOrder(){_InOrder(_root);}private:void _destory(Node* root){if (root == nullptr){return;}_destory(root->_left);_destory(root->_right);delete root;root = nullptr;}Node* _Copy(const Node* root){if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_data);newRoot->_left = _Copy(root->_left);newRoot->_right = _Copy(root->_right);return newRoot;}//中序遍历void _InOrder(const Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_data.first << ':' << root->_data.second << endl;_InOrder(root->_right);}//成员变量Node* _root;};
}

3. 二叉搜索树的性能分析

插入和删除操作都必须先查找，查找效率代表二叉搜索树的各个操作的性能
对有n个节点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是节点在二
叉搜索树的深度的函数，即结点越深，则比较次数越多，但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：log2​N
最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：N/2

二叉搜索树退化，使二叉搜索树性能丢失，需要使二叉搜索树平衡，可以使用AVL树和红黑树。