目录二叉搜索树的概念性能分析二叉搜索树的插入二叉搜索树的查找二叉搜索树的删除情形 1N 的左右孩子均为空叶结点情形 2N 的左孩子为空右孩子不为空情形 3N 的右孩子为空左孩子不为空情形 4N 的左右孩子均不为空​编辑完整的删除代码二叉搜索树的应用场景key的应用场景场景1小区车库自动抬杆场景2英文单词拼写检查场景3禁止名单/白名单系统Key/Value 场景键值对映射场景1中英互译字典场景2商场车库收费系统场景3统计文章中单词出现次数场景4电话簿/通讯录代码的具体实现二叉搜索树的概念二叉搜索树又称为搜索二叉树特点若根节点的左子树不为空其左子树的所有结点都小于根节点的值。若根节点的右子树不为空其左子树的所有结点都大于根节点的值。同时左子树和右子树的为根的时候也同时满足上述的条件。性能分析最优情况下搜索二叉树的为完全二叉树或者接近完全二叉树他的高度是。最差情况下搜索二叉树退化成链表的时候他的高度是。综上取最差的情况他的时间复杂度是O(N)。二叉搜索树的插入1、先看这棵树是不是空树是就直接插入给_root2、不是空树看插入的key是否插入到左子树还是右子树根据搜索二叉树的特点比根大的都是在右边的比跟小的在左边以此类推。3、如果插入的值和树内的某一个结点相同那么可以往左走也可以往右边走具体看需求而定。bool Insert(const K key) { if (_root nullptr)//判断树是不是空的 { _rootnew Node(key); return true; } Node* cur _root; Node* parent nullptr; //建立两个指针记录前后 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);//建立节点这个时候cur是nullptr刚好可以用 if (parent-_key key)//找插入的位置这个时候就是一个简单的二层二叉树 { parent-_right cur; } else { parent-_left cur; } delete cur;//释放资源 return true; }二叉搜索树的查找从根开始比较查找x根据特点要找的值比根大往右边找要找的值比根小往左边找。走到空没有找到就是不存在如果这个树不支持插入相等的值找到x就返回因为x是唯一的如果支持插入相等的值那么他要找往深处的。bool Find(const K key) { if (_root nullptr) { return false; } Node* cur _root; while (cur) { if (cur-_key key)//大于根节点往右边走 { cur cur-_right; } else if (cur-_key key)//小于根节点往左边走 { cur cur-_left; } else//和节点相同的值不插入 { return true; } } return false; }二叉搜索树的删除前置条件给定一个值key首先在二叉搜索树BST中查找该值对应的结点。若该值不存在于树中则删除操作失败返回false。若该值存在则找到要删除的结点记为N并根据其子结点情况分以下四种情形处理。情形 1N 的左右孩子均为空叶结点描述N 没有子结点。处理方式将 N 的父结点中指向 N 的指针左或右置为nullptr。直接删除结点 N。备注此情形也可以归入情形 2 或 3 处理将空孩子视为不存在效果相同。情形 2N 的左孩子为空右孩子不为空描述N 只有右子树。处理方式将 N 的父结点中指向 N 的指针改为指向 N 的右孩子。直接删除结点 N。情形 3N 的右孩子为空左孩子不为空描述N 只有左子树。处理方式将 N 的父结点中指向 N 的指针改为指向 N 的左孩子。直接删除结点 N。情形 4N 的左右孩子均不为空描述N 同时拥有左子树和右子树。问题不能直接删除 N因为它的两个子树都无法简单“上移”并保持 BST 的性质。解决方案使用替换法替代删除。详细步骤选择替代结点 R二选一选择N 左子树中的最大值结点即左子树中最右侧的结点或选择N 右子树中的最小值结点即右子树中最左侧的结点。这两个结点都满足 BST 的排序规则且可以安全地放到 N 的位置。交换值将 N 与 R 的数据值key进行交换或直接将 R 的值覆盖 N 的值。转换删除目标经过交换后原先 R 结点中的值现在位于 N 结点而R 结点中存储的是 N 的旧值。现在问题转化为删除原来的 R 结点此时 R 结点存储的是 N 的旧值。删除 R 结点由于 R 是左子树的最大值或右子树的最小值它不可能同时拥有左右两个孩子如果是左子树最大值则它没有右孩子符合情形 2 或 3。如果是右子树最小值则它没有左孩子符合情形 2 或 3。因此可以直接按照情形 2 或 3 的方式删除 R 结点将其父结点指针指向它的唯一孩子或空。完成删除此时树中已没有重复的 keyBST 性质保持完整删除成功返回true。情况1和情况2if (cur-_left nullptr)//左子树为空那么只能让右子树来继承反过来也一样 { if (cur _root) { _root cur-_right;//没有左子树那么就让右子树的根继承 } else { if (cur parent-_left) { parent-left cur-_right; } else if(curparent-_right) { parent-_right cur-_right; } } delete cur; }情况3else if (cur-_right nullptr) { if (cur _root) { _root cur-_left;//没有右子树那么就让左子树的根继承 } else { if (cur parent-_left) { parent-left cur-_left; } else if (cur parent-_right) { parent-_right cur-_left; } } delete cur; }情况4左右子树都不为空下面是找右子树最小的值来替代else//情况四左右子树都不为空找右子树最小的替代或者找左子树最大的替代这里是右子树最小的替代 { Node* replaceparent cur; Node* replace cur-_right; while (replace-_left) { replaceparent replace; replace replace-_left; } cur-_key replace-_key; if (replaceparent-_left replace) replaceparent-_left replace-_right; else replaceparent-_right replace-_right; delete replace; }完整的删除代码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 (cur _root) { _root cur-_right;//没有左子树那么就让右子树的根继承 } else { if (cur parent-_left) { parent-left cur-_right; } else if(curparent-_right) { parent-_right cur-_right; } } delete cur; } else if (cur-_right nullptr) { if (cur _root) { _root cur-_left;//没有右子树那么就让左子树的根继承 } else { if (cur parent-_left) { parent-left cur-_left; } else if (cur parent-_right) { parent-_right cur-_left; } } delete cur; } else//情况四左右子树都不为空找右子树最小的替代或者找左子树最大的替代这里是右子树最小的替代 { Node* replaceparent cur; Node* replace cur-_right; while (replace-_left) { replaceparent replace; replace replace-_left; } cur-_key replace-_key; if (replaceparent-_left replace) replaceparent-_left replace-_right; else replaceparent-_right replace-_right; delete replace; } return true; } } }二叉搜索树的应用场景key的应用场景场景1小区车库自动抬杆物业把买了车位业主的车牌号录入系统存进 BST车辆到达入口摄像头扫描车牌系统查找这个车牌在不在BST 中在 → 抬杆放行 不在 → 提示“非本小区车辆”场景2英文单词拼写检查把词库中所有正确单词放入 BST读取文章中的每个单词去 BST 中查找找不到 → 该单词拼写可能有误标红波浪线提示场景3禁止名单/白名单系统把黑名单用户 ID 存入 BST每次请求到来先查 ID 是否在 BST 中在 → 拒绝访问不在 → 允许访问特点只存 key插入和查找都是 O(logN)比遍历数组快得多。Key/Value 场景键值对映射特点存 key value通过 key 查找对应的 value。场景1中英互译字典树中存英文单词, 中文含义用户输入apple系统找到对应的苹果这是最经典的键值对应用场景2商场车库收费系统入口扫描车牌记录车牌号, 入场时间出口再次扫描车牌查找该车牌对应的入场时间用当前时间 - 入场时间 停车时长 → 计算停车费缴费后抬杆放行场景3统计文章中单词出现次数树中存单词, 出现次数每读到一个单词在 BST 中查找该单词找不到 → 插入单词, 1第一次出现找到 → 将对应的次数 1最后中序遍历输出就是按字母顺序统计的单词词频场景4电话簿/通讯录存姓名, 电话号码输入姓名快速查到对应的号码代码的具体实现namespace keyval { template class K,class V struct BSTNode { K _key; V _value; BSTNodeK, V* _left; BSTNodeK, 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 BSTNodeK, V Node; public: BSTree() default;//key的情况不写是因为他没有写构造函数所有自动生成 BSTree(const Node t) { _root Copy(t._root); } Node* Copy(Node* root) { if (nullptr root) return nullptr; Node* newroot new Node(root-_key, root-_value); newroot-_leftCopy(root-_left); newroot-_right Copy(root-_right); return newroot; } private: }; }注意下述图片不显示value不影响递归。8的左子树递归8的右子树递归template class K,class V struct BSTNode { K _key; V _value; BSTNodeK, V* _left; BSTNodeK, 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 BSTNodeK, V Node; public: BSTree() default;//key的情况不写是因为他没有写构造函数所有自动生成 BSTree(const BSTreeK,V t) { _root Copy(t._root); } ~BSTree() { Destroy(_root); _root nullptr; } void InOrder(const Node _root) { _InOrder(_root); cout endl; } bool Insert(const K key,const V value) { if (_root nullptr)//判断树是不是空的 { _root new Node(key,value); return true; } Node* cur _root; Node* parent nullptr; //建立两个指针记录前后 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);//建立节点这个时候cur是nullptr刚好可以用 if (parent-_key key)//找插入的位置这个时候就是一个简单的二层二叉树 { parent-_right cur; } else { parent-_left cur; } delete cur;//释放资源 return true; } Node* Find(const K key)//要返回节点 { if (_root nullptr) { return nullptr; } 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; } private: void _InOrder(Node* root) { if (root nullptr) return; _InOrder(root-_left); cout root-_key :root-_value endl; _InOrder(root-_right); } Node* Copy(Node* root) { if (nullptr root) return nullptr; Node* newroot new Node(root-_key, root-_value); newroot-_leftCopy(root-_left); newroot-_right Copy(root-_right); return newroot; } void Destroy(Node* root) { if (root nullptr) return; Destroy(root-_left); Destroy(root-_right); delete root; } private: Node* _root nullptr; };Key/Value的场景和单独Key的区别并没有特别大毕竟Value是Key的映射稍微有点不同的就是Find函数要有返回值构造的时候要多写Value要自己写构造函数因为拷贝构造函数的存在编译器就不会生成普通的构造函数了还要单独销毁递归的思想和拷贝相同。