二叉搜索树(全)

目录一. 二叉搜索树的概念二. 二叉搜索树的性能分析2.1 二分查找的局限性三. 实现二叉搜索树3.1 插入数据3.1.1 中序遍历3.1.2 隐藏的麻烦3.1.3 运行验证3.2 插入数据允许插入相同值3.2 查找数据3.3 删除数据3.3.1 删除数据的可能情况3.3.2 不同情况对应的解决办法3.3.3 示例3.3.4 代码实现四. 二叉搜索树key和key/value使用场景4.1 key使用场景4.2 key/value 的使用场景4.3 key/value 的代码实现一. 二叉搜索树的概念1若它的左子树不为空则左子树上所有结点的值都小于等于根结点的值2若它的右子树不为空则右子树上所有结点的值都大于等于根结点的值3它的左右子树也分别为二叉搜索树4二叉搜索树中可以支持插入相等的值也可以不支持插入相等的值具体看使用场景定义后续艾莉丝会介绍的map/set/multimap/multiset系列容器底层就是二叉搜索树其中map/set不支持插入相等值multimap/multiset支持插入相等值。二. 二叉搜索树的性能分析最优情况下二叉搜索树为完全二叉树或者接近完全二叉树其高度为logN最差情况下二叉搜索树退化为单支树或者类似单支其高度为N所以综合而言二叉搜索树增删查改时间复杂度为O(N)。那么这样的效率显然是无法满足我们需求的因此后面会介绍二叉搜索树的变形——平衡二叉搜索树AVL树和红黑树才能适用于我们在内存中存储和搜索数据。2.1 二分查找的局限性1需要存储在支持下标随机访问的结构中并且有序2插入和删除数据效率很低因为存储在下标随机访问的结构中插入和删除数据一般需要挪动数据。三. 实现二叉搜索树3.1 插入数据#define _CRT_SECURE_NO_WARNINGS #pragma once templateclass K class BTSNode { BTSNode(const K key) :_key(key) , _left(nullptr) , _right(nullptr) {} public: K _key; BTSNodeK* _left; BTSNodeK* _right; }; templateclass K class BSTree { public: typedef BTSNodeK Node; 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-_keykey) { parent cur; cur cur-_left; } else { return false; } } Node* newnode new Node(key); if (parent-_key key) { parent-_right newnode; } else { parent-_left newnode; } return true; } private: Node* _root nullptr; };3.1.1 中序遍历为什么选择中序遍历1中序遍历最简单的递归2中序遍历有序并且数据都在并且能够很好地验证功能。3.1.2 隐藏的麻烦如果我们想要调用中序遍历就需要传根但是根是私有的常用的办法就是提供一个get_root接口还有一种办法我们在_Inorder外面再套一层Inorder。3.1.3 运行验证#define _CRT_SECURE_NO_WARNINGS #pragma once #includeiostream using namespace std; templateclass K class BTSNode { public: BTSNode(const K key) :_key(key) , _left(nullptr) , _right(nullptr) {} public: K _key; BTSNodeK* _left; BTSNodeK* _right; }; templateclass K class BSTree { public: typedef BTSNodeK Node; 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-_keykey) { parent cur; cur cur-_left; } else { return false; } } Node* newnode new Node(key); if (parent-_key key) { parent-_right newnode; } else { parent-_left newnode; } return true; } public: void Inorder() { _Inorder(_root); cout endl; } private: void _Inorder(Node* root) { if (root nullptr) { return; } _Inorder(root-_left); cout root-_key ; _Inorder(root-_right); } private: Node* _root nullptr; };#includeBinarySearchTree.h; int main() { BSTreeint T; int a[] { 8,3,1,10,16,4,7,14,13 }; for (auto e : a) { T.Insert(e); } T.Inorder(); return 0; }3.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-_keykey) { parent cur; cur cur-_left; } } Node* newnode new Node(key); //判断修改 if (parent-_key key) { parent-_right newnode; } else { parent-_left newnode; } return true; }3.2 查找数据1从根开始比较查找xx比根的值大则往右边走查找x比根值小则往左边走查找2最多查找高度次走到到空还没找到这个值不存在3如果不支持插入相等的值找到x即可返回4如果支持插入相等的值意味着有多个x存在一般要求查找中序的第一个x。如下图查找3要找到1的右孩子的那个3返回。bool Find(const K key) { Node* cur root; while (cur) { if (cur-_key key) { cur cur-_left; } else if (cur-_key key) { curcur-_right } else { return true; } } return false; }3.3 删除数据3.3.1 删除数据的可能情况1要删除结点N左右孩子均为空2要删除的结点N左孩子位空右孩子结点不为空3要删除的结点N右孩子位空左孩子结点不为空4要删除的结点N左右孩子结点均不为空。3.3.2 不同情况对应的解决办法1把N结点的父亲对应孩子指针指向空直接删除N结点情况1可以当成2或者3进行处理效果是一样的2把N结点的父亲对应孩子指针指向N的右孩子直接删除N结点3把N结点的父亲对应孩子指针指向N的左孩子直接删除N结点4无法直接删除N结点因为N的两个孩子无处安放只能用替换法删除。找N左子树的值最大结点R最右结点或者N右子树的值最小结点R最左结点替代N因为这两个结点中任意一个放到N的位置都满足二叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换转而变成删除R结点R结点符合情况2或情况3可以直接删除。3.3.3 示例3.3.4 代码实现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) { //还有一个额外情况如果删除的节点就是根节点呢那就直接改变根节点的指向 if (cur _root) { _root cur-_right; } //搞清楚两件事1.cur的左边有孩子还是右边有孩子 // 2.parent的左边是cur还是右边是cur else { if (parent-_left cur) { parent-_left cur-_right; } else { parent-_right cur-_right; } } delete cur; } else if(!cur-_right) { if (cur _root) { _root cur-_left; } else { if (parent-_left cur) { parent-_left cur-_left; } else { 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; } } return false; }四. 二叉搜索树key和key/value使用场景4.1 key使用场景只有key作为关键码结构中只需要存储key即可关键码即为需要搜索到的值搜索场景只需要判断key在不在。key的搜索场景实现的二又树搜索树支持增删查但是不支持修改修改key破坏搜索树结构了。场景1小区无人值守车库小区车库买了车位的业主车才能进小区那么物业会把买了车位的业主的车牌号录入后台系统车辆进入时扫描车牌在不在系统中在则抬杆不在则提示非本小区车辆无法进入。场景2检查一篇英文文章单词拼写是否正确将词库中所有单词放入二叉搜索树读取文章中的单词查找是否在二叉搜索树中不在则波浪线标红提示。4.2 key/value 的使用场景每一个关键码key都有与之对应的值valuevalue可以任意类型对象。树的结构中结点除了需要存储key还要存储对应的value增/删/查还是以key为关键字走二叉搜索树的规则进行比较可以快速查找到key对应的value。key/value的搜索场景实现的二叉树搜索树支持修改但是不支持修改key修改key破坏搜索树性质了可以修改value。场景1简单中英互译字典树的结构中结点存储key(英文和vlaue中文搜索时输入英文则同时查找到了英文对应的中文场景2商场无人值守车库入口进场时扫描车牌记录车牌和入场时间出口离场时扫描车牌查找入场时间用当前时间-入场时间计算出停车时长计算出停车费用缴费后抬杆车辆离场——场景3统计一篇文章中单词出现的次数读取一个单词查找单词是否存在不存在这个说明第一次出现( 单词 , 1单词存在则单词对应的次数。4.3 key/value 的代码实现#define _CRT_SECURE_NO_WARNINGS #pragma once #includeiostream using namespace std; namespace key_value { templateclass K,class V class BTSNode { public: BTSNode(const K key,const V value) :_key(key) ,_value(value) , _left(nullptr) , _right(nullptr) {} public: K _key; V _value; BTSNodeK,V* _left; BTSNodeK,V* _right; }; templateclass K,class V class BSTree { public: typedef BTSNodeK,V Node; BSTree() default; BSTree(const BSTreeK, V t) { _root Copy(t._root); } BSTree operator(BSTree t) { std::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; } } Node* newnode new Node(key,value); if (parent-_key key) { parent-_right newnode; } else { parent-_left newnode; } return true; } void Inorder() { _Inorder(_root); cout endl; } Node* 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 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) { //还有一个额外情况如果删除的节点就是根节点呢那就直接改变根节点的指向 if (cur _root) { _root cur-_right; } //搞清楚两件事1.cur的左边有孩子还是右边有孩子 // 2.parent的左边是cur还是右边是cur else { if (parent-_left cur) { parent-_left cur-_right; } else { parent-_right cur-_right; } } delete cur; } else if (!cur-_right) { if (cur _root) { _root cur-_left; } else { if (parent-_left cur) { parent-_left cur-_left; } else { 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; } } return false; } private: Node* Copy(Node* root) { if (root nullptr) { return nullptr; } Node* newnode new Node(root-_key, root-_value); newnode-_left Copy(root-_left); newnode-_right Copy(root-_right); return newnode; } void Destroy(Node* root) { if (root nullptr) { return; } Destroy(root-_left); Destroy(root-_right); delete root; } void _Inorder(Node* root) { if (root nullptr) { return; } _Inorder(root-_left); cout root-_key : root-_value endl; _Inorder(root-_right); } private: Node* _root nullptr; }; }