目录一、二叉搜索树概念二、二叉搜索树的性能三、二叉搜索树的代码实现实现key和key/value插入key版本key/value版本查询key版本key/value版本删除key版本key/value版本完整代码key版本key/value版本四、二叉搜索树的应用一、二叉搜索树概念⼆叉搜索树⼜称⼆叉排序树它或者是⼀棵空树或者是具有以下性质的⼆叉树: 1.若它的左⼦树不为空则左⼦树上所有结点的值都⼩于等于根结点的值。2.若它的右⼦树不为空则右⼦树上所有结点的值都⼤于等于根结点的值它的左右⼦树也分别为⼆叉搜索树。二、二叉搜索树的性能如果是最优情况下接近完全二叉树下高度接近为使得复杂度为O()。而当情况为最差情况下就是单支树高度为n复杂度就是O(n)。所以综合二叉树的增删查改的时间复杂度为O(n)。它和二分查找查询差不多二分查找也可以实现O()的查找效率但是二分查找有一个缺陷就是内部支持下标随机访问的且有序删除和插入需要挪动数据效率很低所以二叉搜索树就是在插入和删除要优与二分查找。三、二叉搜索树的代码实现实现key和key/value插入key版本//插入(默认左边小于根右边大于根) bool insert(const K key) { //判断是否有根节点 if (_root nullptr) { _root new Node(key); return true; } Node* cur _root; Node* parent nullptr; while(cur) { //比根小 if (cur-_key key) { parent cur; cur cur-_left; } //比根大 else if (cur-_key key) { parent cur; cur cur-_right; } //相同 else { return false; } } //寻找到空位置 Node* node new Node(key); //比父大 if (parent-_key key) { parent-_right node; } //比父小 else { parent-_left node; } //插入成功 return true; }key/value版本//插入(默认左边小于根右边大于根) bool insert(const pairK,V kv) { //判断是否有根节点 if (_root nullptr) { _root new Node(kv); return true; } Node* cur _root; Node* parent nullptr; while (cur) { //比根小 if (cur-_kv.first kv.first) { parent cur; cur cur-_left; } //比根大 else if (cur-_kv.first kv.first) { parent cur; cur cur-_right; } //相同 else { return false; } }查询key版本//查询 Node* find(const K key) { if (_root nullptr) { return nullptr; } 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; }key/value版本//查询 Node* find(const K key) { if (_root nullptr) { return nullptr; } Node* cur _root; while (cur) { if (cur-_kv.first key) { cur cur-_left; } else if (cur-_kv.first key) { cur cur-_right; } //找到了 else { return cur; } } //没找到 return nullptr; }删除key版本总结代码实现删除可以看成3种类型1.左孩子不存在将右结点存在和不存在结合在一起//左孩子为空(结合右孩子为空和不为空的情况) if (cur-_left nullptr) { //先判断是否为根节点 if (cur _root) { _root _root-_right; } else { //判断是parent左右孩子 if (parent-_left cur) { parent-_left cur-_right; } else { parent-_right cur-_right; } } delete cur; cur nullptr; }2.右孩子不存在将左孩子存在和左孩子不存在结合在一起//右孩子为空 else if (cur-_right nullptr) { //先判断该删除结点是否为根结点 if (cur _root) { _root _root-_left; } else { //判断是parent的左右孩子 if (parent-_left cur) { parent-_left cur-_left; } else { parent-_right cur-_left; } } delete cur; cur nullptr; }3.都存在第三种情况较为复杂就是左右孩子都存在这就需要寻找一个代替结点去继承该删除结点我们可以选择左子树中的最右结点也就是左子树中最大结点或者我们选择右子树中的最左结点也就是右子树中最小结点这两个操作都可以实现目的是为了满足根结点一定要小于右子树/大于左子树即可。//左右孩子不为空 else { //这里我以左子树中最大结点作为删除结点的替换 Node* midrootparent cur; Node* midroot cur-_left; //寻找最右结点 while (midroot-_right) { midrootparent midroot; midroot midroot-_right; } //找到 //交换key swap(cur-_key, midroot-_key); if (midrootparent-_left midroot) { midrootparent-_left midroot-_left;//因为我们找的是cur左子树中的最右结点可能最大值的左孩子存在 } else { midrootparent-_right midroot-_left; } //删除midroot delete midroot; midroot nullptr; } return true;key/value版本key/value版本和key的思路都一样bool erase(const K key) { Node* parent nullptr; Node* cur _root; if (cur nullptr) { return false; } while (cur) { if (cur-_kv.first key) { parent cur; cur cur-_left; } else if (cur-_kv.first key) { parent cur; cur cur-_right; } //找到了 else { //左孩子为空(结合右孩子为空和不为空的情况) if (cur-_left nullptr) { //先判断是否为根节点 if (cur _root) { _root _root-_right; } else { //判断是parent左右孩子 if (parent-_left cur) { parent-_left cur-_right; } else { parent-_right cur-_right; } } delete cur; cur nullptr; } //右孩子为空 else if (cur-_right nullptr) { //先判断该删除结点是否为根结点 if (cur _root) { _root _root-_left; } else { //判断是parent的左右孩子 if (parent-_left cur) { parent-_left cur-_left; } else { parent-_right cur-_left; } } delete cur; cur nullptr; } //左右孩子不为空 else { //这里我以左子树中最大结点作为删除结点的替换 Node* midrootparent cur; Node* midroot cur-_left; //寻找最右结点 while (midroot-_right) { midrootparent midroot; midroot midroot-_right; } //找到 //交换key swap(cur-_kv, midroot-_kv); if (midrootparent-_left midroot) { midrootparent-_left midroot-_left;//因为我们找的是cur左子树中的最右结点可能最大值的左孩子存在 } else { midrootparent-_right midroot-_left; } //删除midroot delete midroot; midroot nullptr; } return true; } } return false; }完整代码key版本namespace bear1 { templateclass K struct BSTNode { K _key; BSTNodeK* _left; BSTNodeK* _right; //初始化构造 BSTNode(K key) :_key(key) ,_left(nullptr) ,_right(nullptr) {} }; templateclass K class BSTree { typedef BSTNodeK Node; public: //构造 BSTree(Node* root nullptr) :_root(root) {} //插入(默认左边小于根右边大于根) bool insert(const K key) { //判断是否有根节点 if (_root nullptr) { _root new Node(key); return true; } Node* cur _root; Node* parent nullptr; while(cur) { //比根小 if (cur-_key key) { parent cur; cur cur-_left; } //比根大 else if (cur-_key key) { parent cur; cur cur-_right; } //相同 else { return false; } } //寻找到空位置 Node* node new Node(key); //比父大 if (parent-_key key) { parent-_right node; } //比父小 else { parent-_left node; } //插入成功 return true; } //查询 Node* find(const K key) { if (_root nullptr) { return nullptr; } 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; if (cur nullptr) { return false; } while (cur) { if (cur-_key key) { parent cur; cur cur-_left; } else if (cur-_key key) { parent cur; cur cur-_right; } //找到了 else { //左孩子为空(结合右孩子为空和不为空的情况) if (cur-_left nullptr) { //先判断是否为根节点 if (cur _root) { _root _root-_right; } else { //判断是parent左右孩子 if (parent-_left cur) { parent-_left cur-_right; } else { parent-_right cur-_right; } } delete cur; cur nullptr; } //右孩子为空 else if (cur-_right nullptr) { //先判断该删除结点是否为根结点 if (cur _root) { _root _root-_left; } else { //判断是parent的左右孩子 if (parent-_left cur) { parent-_left cur-_left; } else { parent-_right cur-_left; } } delete cur; cur nullptr; } //左右孩子不为空 else { //这里我以左子树中最大结点作为删除结点的替换 Node* midrootparent cur; Node* midroot cur-_left; //寻找最右结点 while (midroot-_right) { midrootparent midroot; midroot midroot-_right; } //找到 //交换key swap(cur-_key, midroot-_key); if (midrootparent-_left midroot) { midrootparent-_left midroot-_left;//因为我们找的是cur左子树中的最右结点可能最大值的左孩子存在 } else { midrootparent-_right midroot-_left; } //删除midroot delete midroot; midroot nullptr; } return true; } } return false; } //中序遍历 void _Order() { Order(_root); cout endl; } private: void Order(Node* root) { //利用递归进行中序遍历 if (root nullptr) { return; } //左根右 Order(root-_left); cout root-_key ; Order(root-_right); } Node* _root; }; }key/value版本namespace bear2 { templateclass K,class V struct BSTNode { pairK, V _kv; BSTNodeK,V* _left; BSTNodeK,V* _right; //初始化构造 BSTNode(pairK,V kv) :_kv(kv) , _left(nullptr) , _right(nullptr) { } }; templateclass K,class V class BSTree { typedef BSTNodeK,V Node; public: //构造 BSTree(Node* root nullptr) :_root(root) { } //插入(默认左边小于根右边大于根) bool insert(const pairK,V kv) { //判断是否有根节点 if (_root nullptr) { _root new Node(kv); return true; } Node* cur _root; Node* parent nullptr; while (cur) { //比根小 if (cur-_kv.first kv.first) { parent cur; cur cur-_left; } //比根大 else if (cur-_kv.first kv.first) { parent cur; cur cur-_right; } //相同 else { return false; } } //寻找到空位置 Node* node new Node(kv); //比父大 if (parent-_kv.first kv.first) { parent-_right node; } //比父小 else { parent-_left node; } //插入成功 return true; } //查询 Node* find(const K key) { if (_root nullptr) { return nullptr; } Node* cur _root; while (cur) { if (cur-_kv.first key) { cur cur-_left; } else if (cur-_kv.first key) { cur cur-_right; } //找到了 else { return cur; } } //没找到 return nullptr; } bool erase(const K key) { Node* parent nullptr; Node* cur _root; if (cur nullptr) { return false; } while (cur) { if (cur-_kv.first key) { parent cur; cur cur-_left; } else if (cur-_kv.first key) { parent cur; cur cur-_right; } //找到了 else { //左孩子为空(结合右孩子为空和不为空的情况) if (cur-_left nullptr) { //先判断是否为根节点 if (cur _root) { _root _root-_right; } else { //判断是parent左右孩子 if (parent-_left cur) { parent-_left cur-_right; } else { parent-_right cur-_right; } } delete cur; cur nullptr; } //右孩子为空 else if (cur-_right nullptr) { //先判断该删除结点是否为根结点 if (cur _root) { _root _root-_left; } else { //判断是parent的左右孩子 if (parent-_left cur) { parent-_left cur-_left; } else { parent-_right cur-_left; } } delete cur; cur nullptr; } //左右孩子不为空 else { //这里我以左子树中最大结点作为删除结点的替换 Node* midrootparent cur; Node* midroot cur-_left; //寻找最右结点 while (midroot-_right) { midrootparent midroot; midroot midroot-_right; } //找到 //交换key swap(cur-_kv, midroot-_kv); if (midrootparent-_left midroot) { midrootparent-_left midroot-_left;//因为我们找的是cur左子树中的最右结点可能最大值的左孩子存在 } else { midrootparent-_right midroot-_left; } //删除midroot delete midroot; midroot nullptr; } return true; } } return false; } //中序遍历 void _Order() { Order(_root); cout endl; } private: void Order(Node* root) { //利用递归进行中序遍历 if (root nullptr) { return; } //左根右 Order(root-_left); cout root-_kv.first : root-_kv.second endl; Order(root-_right); } Node* _root; }; }四、二叉搜索树的应用二叉搜索树的应用场景在生活中很场景例如在搜索单词是否正确时候我们会用到二叉搜索树来查询是否有这个单词从而来判断单词的正确性还有就是小区门口用于防外来车俩占用业主车库的识别杠这个时候用二叉搜索树来查询就会很方便查询到是业主车牌就会开杠入进。而还有一个针对于key/value的应用场景可以是中英互译知道key中文/英文就能得到value(英文/中文)还有就是统计一篇文章中单词出现次数用二叉搜索树就很方便类似哈希表后面我们会将和哈希表的联系。