企业官网建设流程全解析

五金网站建设,虹桥街道网站建设,怎么自己开一个平台,高德vr全景地图⼆叉搜索树的概念 ⼆叉搜索树⼜称⼆叉排序树#xff0c;它或者是⼀棵空树#xff0c;或者是具有以下性质的⼆叉树: 若它的左⼦树不为空#xff0c;则左⼦树上所有结点的值都⼩于等于根结点的值若它的右⼦树不为空#xff0c;则右⼦树上所有结点的值都⼤于等于根结点的值它的…⼆叉搜索树的概念⼆叉搜索树⼜称⼆叉排序树它或者是⼀棵空树或者是具有以下性质的⼆叉树:若它的左⼦树不为空则左⼦树上所有结点的值都⼩于等于根结点的值若它的右⼦树不为空则右⼦树上所有结点的值都⼤于等于根结点的值它的左右⼦树也分别为⼆叉搜索树⼆叉搜索树中可以⽀持插⼊相等的值也可以不⽀持插⼊相等的值具体看使⽤场景定义map/set/multimap/multiset系列容器底层就是⼆叉搜索树其中map/set不⽀持插⼊相等值multimap/multiset⽀持插⼊相等值⼆叉搜索树的性能分析最优情况下⼆叉搜索树为完全⼆叉树(或者接近完全⼆叉树)其⾼度为log2Nlog_{2} Nlog2​N最差情况下⼆叉搜索树退化为单⽀树(或者类似单⽀)其⾼度为N所以综合⽽⾔⼆叉搜索树增删查改时间复杂度为O(N)那么这样的效率显然是⽆法满⾜我们需求的平衡⼆叉搜索树AVL树和红⿊树才能适⽤于我们在内存中存储和搜索数据。另外需要说明的是⼆分查找也可以实现O(log2N)O(log_{2} N)O(log2​N)级别的查找效率但是⼆分查找有两⼤缺陷需要存储在⽀持下标随机访问的结构中并且有序。插⼊和删除数据效率很低因为存储在下标随机访问的结构中插⼊和删除数据⼀般需要挪动数据。这⾥也就体现出了平衡⼆叉搜索树的价值。⼆叉搜索树的插⼊插⼊的具体过程如下树为空则直接新增结点赋值给root指针树不空按⼆叉搜索树性质插⼊值⽐当前结点⼤往右⾛插⼊值⽐当前结点⼩往左⾛找到空位置插⼊新结点。如果⽀持插⼊相等的值插⼊值跟当前结点相等的值可以往右⾛也可以往左⾛找到空位置插⼊新结点。要注意的是要保持逻辑⼀致性插⼊相等的值不要⼀会往右⾛⼀会往左⾛int a[] {8, 3, 1, 10, 6, 4, 7, 14, 13};⼆叉搜索树的查找从根开始⽐较查找xx⽐根的值⼤则往右边⾛查找x⽐根值⼩则往左边⾛查找。最多查找⾼度次⾛到到空还没找到这个值不存在。如果不⽀持插⼊相等的值找到x即可返回如果⽀持插⼊相等的值意味着有多个x存在⼀般要求查找中序的第⼀个x。如下图查找3要找到1的右孩⼦的那个3返回⼆叉搜索树的删除⾸先查找元素是否在⼆叉搜索树中如果不存在则返回false。如果查找元素存在则分以下四种情况分别处理假设要删除的结点为N要删除结点N左右孩⼦均为空要删除的结点N左孩⼦位空右孩⼦结点不为空要删除的结点N右孩⼦位空左孩⼦结点不为空要删除的结点N左右孩⼦结点均不为空对应以上四种情况的解决⽅案把N结点的⽗亲对应孩⼦指针指向空直接删除N结点情况1可以当成2或者3处理效果是⼀样的把N结点的⽗亲对应孩⼦指针指向N的右孩⼦直接删除N结点把N结点的⽗亲对应孩⼦指针指向N的左孩⼦直接删除N结点⽆法直接删除N结点因为N的两个孩⼦⽆处安放只能⽤替换法删除。找N左⼦树的值最⼤结点R(最右结点)或者N右⼦树的值最⼩结点R(最左结点)替代N因为这两个结点中任意⼀个放到N的位置都满⾜⼆叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换转⽽变成删除R结点R结点符合情况2或情况3可以直接删除。⼆叉搜索树的实现代码templateclass K struct BSTNode { K _key; BSTNodeK* _left; BSTNodeK* _right; BSTNode(const K key) :_key(key) , _left(nullptr) , _right(nullptr) {} }; // Binary Search Tree templateclass K class BSTree { typedef BSTNodeK Node; public: // 强制生成默认构造 BSTree() default; BSTree(const BSTreeK t) { _root Copy(t._root); } BSTreeK operator(BSTreeK t) { swap(_root, t._root); return *this; } ~BSTree() { Destroy(_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; } 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; } } return false; } 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 { // 0-1个孩⼦的情况 // 删除情况1 2 3均可以直接删除改变⽗亲对应孩⼦指针指向即可 if (cur-_left nullptr) { if (parent nullptr) { _root cur-_right; } else { if (parent-_left cur) parent-_left cur-_right; else parent-_right cur-_right; } delete cur; return true; } else if (cur-_right nullptr) { if (parent nullptr) { _root cur-_left; } else { if (parent-_left cur) parent-_left cur-_left; else parent-_right cur-_left; } delete cur; return true; } else { // 2个孩⼦的情况 // 删除情况4替换法删除 // 假设这⾥我们取右⼦树的最⼩结点作为替代结点去删除 // 这⾥尤其要注意右⼦树的根就是最⼩情况的情况的处理对应图中删除8的情况 // ⼀定要把cur给rightMinP否会报错。 Node* rightMinP cur; Node* rightMin cur-_right; while (rightMin-_left) { rightMinP rightMin; rightMin rightMin-_left; } cur-_key rightMin-_key; if (rightMinP-_left rightMin) rightMinP-_left rightMin-_right; else rightMinP-_right rightMin-_right; delete rightMin; return true; } } } return false; } void InOrder() { _InOrder(_root); cout endl; } ////////////////////////////////////////////////////////////////// bool FindR(const K key) { return _FindR(_root, key); } bool InsertR(const K key) { return _InsertR(_root, key); } bool EraseR(const K key) { return _EraseR(_root, key); } private: void Destroy(Node* root) { if (root nullptr) return; Destroy(root-_left); Destroy(root-_right); delete 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); return newRoot; } 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; } } 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 _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; } } void _InOrder(Node* root) { if (root nullptr) { return; } _InOrder(root-_left); cout root-_key ; _InOrder(root-_right); } private: Node* _root nullptr; };⼆叉搜索树key和key/value使⽤场景key搜索场景只有key作为关键码结构中只需要存储key即可关键码即为需要搜索到的值搜索场景只需要判断key在不在。key的搜索场景实现的⼆叉树搜索树⽀持增删查但是不⽀持修改修改key破坏搜索树结构了。场景1⼩区⽆⼈值守⻋库⼩区⻋库买了⻋位的业主⻋才能进⼩区那么物业会把买了⻋位的业主的⻋牌号录⼊后台系统⻋辆进⼊时扫描⻋牌在不在系统中在则抬杆不在则提⽰⾮本⼩区⻋辆⽆法进⼊。场景2检查⼀篇英⽂⽂章单词拼写是否正确将词库中所有单词放⼊⼆叉搜索树读取⽂章中的单词查找是否在⼆叉搜索树中不在则波浪线标红提⽰。key/value搜索场景每⼀个关键码key都有与之对应的值valuevalue可以任意类型对象。树的结构中(结点)除了需要存储key还要存储对应的value增/删/查还是以key为关键字⾛⼆叉搜索树的规则进⾏⽐较可以快速查找到key对应的value。key/value的搜索场景实现的⼆叉树搜索树⽀持修改但是不⽀持修改key修改key破坏搜索树性质了可以修改value。场景1简单中英互译字典树的结构中(结点)存储key(英⽂)和vlaue(中⽂)搜索时输⼊英⽂则同时查找到了英⽂对应的中⽂。场景2商场⽆⼈值守⻋库⼊⼝进场时扫描⻋牌记录⻋牌和⼊场时间出⼝离场时扫描⻋牌查找⼊场时间⽤当前时间-⼊场时间计算出停⻋时⻓计算出停⻋费⽤缴费后抬杆⻋辆离场。场景3统计⼀篇⽂章中单词出现的次数读取⼀个单词查找单词是否存在不存在这个说明第⼀次出现单词1单词存在则单词对应的次数。key/value⼆叉搜索树代码实现templateclass K, class V struct BSTNode { // pairK, V _kv; 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) {} }; templateclass K, class V class BSTree { typedef BSTNodeK, V Node; public: BSTree() default; BSTree(const BSTreeK, V t) { _root Copy(t._root); } BSTreeK, V operator(BSTreeK, V t) { 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; } else { return false; } } cur new Node(key, value); if (parent-_key key) { parent-_right cur; } else { parent-_left cur; } return true; } Node* 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 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 nullptr) { if (parent nullptr) { _root cur-_right; } else { if (parent-_left cur) parent-_left cur-_right; else parent-_right cur-_right; } delete cur; return true; } else if (cur-_right nullptr) { if (parent nullptr) { _root cur-_left; } else { if (parent-_left cur) parent-_left cur-_left; else parent-_right cur-_left; } delete cur; return true; } else { Node* rightMinP cur; Node* rightMin cur-_right; while (rightMin-_left) { rightMinP rightMin; rightMin rightMin-_left; } cur-_key rightMin-_key; if (rightMinP-_left rightMin) rightMinP-_left rightMin-_right; else rightMinP-_right rightMin-_right; delete rightMin; return true; } } } return false; } void InOrder() { _InOrder(_root); cout endl; } private: void _InOrder(Node* root) { if (root nullptr) { return; } _InOrder(root-_left); cout root-_key : root-_value endl; _InOrder(root-_right); } void Destroy(Node* root) { if (root nullptr) return; Destroy(root-_left); Destroy(root-_right); delete root; } Node* Copy(Node* root) { if (root nullptr) return nullptr; Node* newRoot new Node(root-_key, root-_value); newRoot-_left Copy(root-_left); newRoot-_right Copy(root-_right); return newRoot; } private: Node* _root nullptr; }; int main() { BSTreestring, string dict; //BSTreestring, string copy dict; dict.Insert(left, 左边); dict.Insert(right, 右边); dict.Insert(insert, 插⼊); dict.Insert(string, 字符串); string str; while (cinstr) { auto ret dict.Find(str); if (ret) { cout - ret-_value endl; } else { cout ⽆此单词请重新输⼊ endl; } } return 0; } int main() { string arr[] { 苹果, 西⽠, 苹果, 西⽠, 苹果, 苹果, 西⽠, 苹果, ⾹蕉, 苹果, ⾹蕉 }; BSTreestring, int countTree; for (const auto str : arr) { // 先查找⽔果在不在搜索树中 // 1、不在说明⽔果第⼀次出现则插⼊⽔果, 1 // 2、在则查找到的结点中⽔果对应的次数 //BSTreeNodestring, int* ret countTree.Find(str); auto ret countTree.Find(str); if (ret NULL) { countTree.Insert(str, 1); } else { ret-_value; } } countTree.InOrder(); return 0; }