一.二叉搜索树的基本概念二叉搜索树Binary Search Tree简称 BST是一种特殊的二叉树它满足以下性质 对于树中的每个节点其左子树中所有节点的值都小于该节点的值 对于树中的每个节点其右子树中所有节点的值都大于该节点的值 左右子树也分别是二叉搜索树 这种特性使得二叉搜索树在查找、插入和删除操作上具有较高的效率平均时间复杂度为 O (log n)。在这里插入图片描述二.二叉搜索树的性能分析最优情况下⼆叉搜索树为完全⼆叉树(或者接近完全⼆叉树)其⾼度为log2 N 最差情况下⼆叉搜索树退化为单⽀树(或者类似单⽀)其⾼度为N 所以综合⽽⾔⼆叉搜索树增删查改时间复杂度为O(N)⼆分查找也可以实现O(log2N) 级别的查找效率但是⼆分查找有两⼤缺陷需要存储在⽀持下标随机访问的结构中并且有序。插⼊和删除数据效率很低因为存储在下标随机访问的结构中插⼊和删除数据⼀般需要挪动数据。这⾥也就体现出了平衡⼆叉搜索树的价值。三.二叉搜索树的实现搜索二叉树的基本概念与特性搜索二叉树是一种特殊的二叉树它满足以下性质若任意节点的左子树不为空则左子树上所有节点的值均小于该节点的值若任意节点的右子树不为空则右子树上所有节点的值均大于该节点的值任意节点的左、右子树也分别为搜索二叉树没有键值相等的节点这些性质使得搜索二叉树在进行查找操作时具有天然的优势我们可以利用节点值的大小关系快速缩小查找范围类似于有序数组的二分查找。搜索二叉树的节点结构设计首先来看搜索二叉树的节点结构实现代码语言javascriptAI代码解释templateclass K struct BSTreeNode { K _key; BSTNodeK* _left; BSTNodeK* _right; BSTNode(const K key) :_key(key) , _left(nullptr) , _right(nullptr) { } };_key节点的关键字用于比较和查找_left指向左子节点的指针_right指向右子节点的指针构造函数初始化节点的关键字并将左右子节点指针置为nullptr节点采用模板设计使得该结构可以存储任意类型的数据只要该类型支持比较运算。搜索二叉树的类结构与核心操作类的基本结构代码语言javascriptAI代码解释templateclass K class BSTree { typedef BSTreeNodeK Node; public: // 构造、拷贝构造、赋值运算符、析构函数 BSTree() default; BSTree(const BSTreeK t); BSTreeK operator(BSTreeK t); ~BSTree(); // 核心操作 bool Insert(const K key); bool Find(const K key); bool Erase(const K key); // 中序遍历 void InOrder(); private: // 中序遍历的递归辅助函数 void _InOrder(Node* root); // 拷贝构造的递归辅助函数 Node* Copy(Node* root); // 析构函数的递归辅助函数 void Destory(Node* root); private: Node* _root nullptr; };构造与析构函数默认构造函数使用C11的default关键字生成默认的构造函数将根节点初始化为nullptr拷贝构造函数通过递归调用Copy函数实现深拷贝确保新对象与原对象相互独立赋值运算符采用拷贝交换技术先创建传入对象的副本然后交换当前对象与副本的根节点指针保证异常安全性析构函数调用Destory函数递归释放所有节点的内存防止内存泄漏插入操作Insert插入操作是构建搜索二叉树的基础其实现逻辑如下代码语言javascriptAI代码解释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-_left cur; } else { parent-_right cur; } return true; }插入操作的步骤如果树为空直接创建根节点否则从根节点开始比较当前节点值与插入值的大小若当前节点值小于插入值向右转若当前节点值大于插入值向左转若相等说明键值已存在插入失败找到合适的插入位置空指针处后创建新节点并连接到父节点查找操作Find查找是搜索二叉树的核心功能利用树的特性可以高效地定位目标节点代码语言javascriptAI代码解释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; // 未找到目标节点 }查找操作的逻辑非常直观与插入操作类似从根节点开始比较当前节点值与目标值根据大小关系决定向左还是向右查找若找到相等的值返回true若遍历完所有可能的节点仍未找到返回false删除操作Erase删除操作是搜索二叉树中最复杂的操作需要考虑多种情况代码语言javascriptAI代码解释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) { // 情况1左子树为空 if (cur _root) { _root _root-_right; } if (parent-_right cur) { parent-_right cur-_right; } else { parent-_left cur-_right; } delete cur; } else if(cur-_right nullptr) { // 情况2右子树为空 if (cur _root) { _root _root-_left; } if (parent-_right cur) { parent-_right cur-_left; } else { parent-_left cur-_left; } delete cur; } else { // 情况3左右子树都不为空 Node* pMinRight cur; Node* minRight cur-_right; while (minRight-_left) { pMinRight minRight; minRight minRight-_left; } // 找到右子树中的最小节点最左节点 swap(minRight-_key, cur-_key); // 删除右子树中的最小节点 if (pMinRight-_left minRight) { pMinRight-_left minRight-_right; } else { pMinRight-_right minRight-_right; } delete minRight; } return true; } } return false; // 未找到要删除的节点 }删除操作需要处理三种情况左子树为空直接用右子树替换当前节点右子树为空直接用左子树替换当前节点左右子树都不为空找到当前节点右子树中的最小节点最左节点将该最小节点的值与当前节点的值交换删除原来的最小节点此时该节点最多只有一个右子树这种处理方式确保了删除节点后搜索二叉树的性质仍然保持。