【知识讲解】 二叉搜索树的相关知识与实现

目录前言Part1. 二叉搜索树核心定义Part1.1. 查找效率特性Part1.2. 不同查找容器对比Part1.3. 重复键值两种处理策略Part2. 二叉搜索树四大核心操作Part2.1. 节点插入Part2.1. 中序遍历特性Part2.2. 节点删除Part3. key/value二叉搜索树Part4. 结语前言二叉搜索树作为二叉树的特化升级版在查找上有着很大的优势但同时也有着不小的问题接下来让我们来看看吧。lets go!!!!!!!!!Part1. 二叉搜索树核心定义二叉搜索树Binary Search Tree简称 BST是满足特殊排序规则的二叉树规则1节点左子树所有节点值 ≤ 当前根节点值。规则2节点右子树所有节点值 ≥ 当前根节点值。规则3左右子树本身也必须是二叉搜索树。Part1.1. 查找效率特性》理想平衡 BST查找次数等于树的高度 h时间复杂度O(logN)》极端不平衡 BST链式退化最坏退化成单链表查找复杂度劣化为O(N)。优化方案平衡二叉搜索树AVL树、红黑树C STL 的 map/set 底层为红黑树多叉平衡树 B 树企业级通常会有一千多个分支。Part1.2. 不同查找容器对比除 BST 外常用查找容器1.哈希表查询速度极快O1级别。2. 有序数组二分查找OlogN查找插入、删除操作效率极低不适合频繁增删场景。Part1.3. 重复键值两种处理策略二叉搜索树对相同数值节点分两种实现方案对应 STL 容器1.去重模式不允许插入重复值对应 std::set / std::map2.允许重复支持存储多个相同 key对应 std::multiset / std::multimapPart2. 二叉搜索树四大核心操作完整实现需要封装四大接口插入、查找、遍历、删除Part2.1. 节点插入节点的插入遵循二叉搜索树的规则来插入就好接下来来看看代码吧bool Insert(const K key) { 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-_left; } else if (cur-_key key) { parent cur; cur cur-_right; } else//去重操作 { return false; } } cur new Node(key); if (parent-_key key) { parent-_left cur; } else { parent-_right cur; } return true; }Part2.1. 中序遍历特性二叉搜索树中序遍历左→根→右结果严格升序升序顺序完全取决于插入数据的大小关系与插入先后顺序无关。void InOrder()const//由于递归需要根节点 但是由于封装又不能暴露 于是就搞一个中介函数来作为其访问根节点的媒介 { _InOrder(_root); std::cout std::endl; } void _InOrder(Node* root)const { if (root nullptr) { return; } _InOrder(root-_left); std::cout root-_key ; _InOrder(root-_right); }Part2.2. 节点删除删除是 BST 最难实现的接口按待删除节点的子树存在情况分为 4 类分别是1. 左右子树均为空。 2. 只有右子树左子树为空。3. 只有左子树右子树为空。 4. 左右子树均不为空。p.s.其中1可以归属与2或者3就当成其有一个为nullptr的左或者右节点就好了。对于2我们使用parent指向待删除结点的父亲节点cur则指向待删除结点我们先判断cur是parent的左子还是右子在让parent连接cur的右节点。3同理。对于4,我们有两种方案(替换法)》方案A取左子树最大值左树最右节点替换待删节点的值再删除该最大值节点》方案B取右子树最小值右树最左节点替换待删节点的值再删除该最小值节点我们来看看代码同时看看其中的细节吧bool erase(const K key) { Node* parent nullptr; Node* cur _root; 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 cur-_right; } else { if (parent-_left cur) { parent-_left cur-_right; } else { parent-_right cur-_right; } } delete cur; } else if (cur-_right nullptr)//无右节点场景 { if (cur _root) { _root cur-_left; } else { if (parent-_left cur) { parent-_left cur-_left; } else { parent-_right cur-_left; } } delete cur; } else { Node* repalce cur-_right; Node* repalce_parent cur;//将这个设为cur为根节点的场景 while (repalce-_left ! nullptr) { repalce_parent repalce; repalce repalce-_left; } cur-_key repalce-_key;//替代 if (repalce_parent-_left repalce)//看看这个是左还是右 在连接 { repalce_parent-_left repalce-_right; } else { repalce_parent-_right repalce-_right; } delete repalce; } return true; } } return false; }Part3. key/value二叉搜索树普通 BST 只存储单个数值对应 set而 map 采用 key-value 模型适配业务中「唯一标识附属数据」场景1.key唯一排序标识树的排序、查找、去重全部基于 keykey 不可修改作为数据唯一区分依据。2.value附属业务数据可自由修改仅作为 key 附带的存储内容不参与树的排序逻辑。这个的实现与上述相似只是多了一个value数值我们来看看代码吧namespace Key_Value { templateclass K,class V struct BSTNode { K _key; V _value; BSTNodeK,V* _left; BSTNodeK,V* _right; BSTNode() :_key(K()) ,_value(V()) , _left(nullptr) , _right(nullptr) { } BSTNode(const K key,const V value) :_key(key) , _value(value) , _left(nullptr) , _right(nullptr) { } }; templateclass K,class V class BSTree { public: using Node BSTNodeK,V; BSTree() default; ~BSTree() { Destroy(_root); _root nullptr; } BSTree(const BSTree Tree) { _root Copy(Tree._root); } BSTree operator(BSTree tem) { std::swap(_root, tem._root); return *this; } 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-_left; } else if (cur-_key key) { parent cur; cur cur-_right; } else { return false; } } cur new Node(key,value); if (parent-_key key) { parent-_left cur; } else { parent-_right cur; } return true; } bool Find(const K key)const { Node* cur _root; while (cur) { if (cur-_key key) { cur cur-_left; } else if (cur-_key key) { cur cur-_right; } else { return true; } } return false; } void InOrder()const { _InOrder(_root); std::cout std::endl; } bool erase(const K key) { Node* parent nullptr; Node* cur _root; 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 cur-_right; } else { if (parent-_left cur) { parent-_left cur-_right; } else { parent-_right cur-_right; } } delete cur; } else if (cur-_right nullptr) { if (cur _root) { _root cur-_left; } else { if (parent-_left cur) { parent-_left cur-_left; } else { parent-_right cur-_left; } } delete cur; } else { Node* repalce cur-_right; Node* repalce_parent cur; while (repalce-_left ! nullptr) { repalce_parent repalce; repalce repalce-_left; } cur-_key repalce-_key; if (repalce_parent-_left repalce) { repalce_parent-_left repalce-_right; } else { repalce_parent-_right repalce-_right; } delete repalce; } return true; } } return false; } private: void _InOrder(Node* root)const { if (root nullptr) { return; } _InOrder(root-_left); std::cout root-_key :root-_value ; _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; } Node* new_node new Node(root-_key); Copy(root-_left); Copy(root-_right); return new_node; } Node* _root nullptr; }; }Part4. 结语二叉搜索树作为未来学习AVL数、红黑树的基石了解它的删除、插入等的逻辑还是非常有必要的。最后祝大家可以春风得意马蹄疾一日看尽长安花最后的最后要是觉得本文还可以的话可以点点赞关注小编一波谢谢大家~