当前位置：首页 > news >正文

《数据结构：二叉搜索树（Binary Search Tree）》

news 2026/5/28 23:59:19

《数据结构：二叉搜索树（Binary Search Tree）》

**作者的个人gitee**
作者的算法讲解主页▶️
每日一言：“人生如逆旅，我亦是行人。🌸🌸”

🔴一、二叉搜索树的概念

二叉搜索树（Binary Search Tree，BST）是一种特殊的二叉树，具有以下性质：

若左子树不为空，则左子树上所有结点的值都小于等于根结点的值。
若右子树不为空，则右子树上所有结点的值都大于等于根结点的值。
左右子树也分别为二叉搜索树。
二叉搜索树中可以支持插入相等的值，也可以不支持，具体取决于使用场景的定义。如，在C++标准模板库中，map和set不支持插入相等值，而multimap和multiset支持插入相等值。

🔴二、二叉搜索树的性能分析

二叉搜索树的性能主要取决于其高度。以下是不同情况下的性能分析：

情况	高度	增删查改时间复杂度
最优	logN	O(logN)
最差	N	O(N)
平均	取决于插入顺序	取决于插入顺序

最优情况：当二叉搜索树为完全二叉树或接近完全二叉树时，其高度为log2N。此时增删查改的时间复杂度为 O(log2N)。
最差情况：当二叉搜索树退化为单支树或类似单支时，其高度为N。此时增删查改的时间复杂度为O(N)。
平均情况：在实际应用中，二叉搜索树的高度取决于插入数据的顺序。如果插入数据是随机的，那么平均情况下二叉搜索树的性能接近最优情况；但如果插入数据是有序的，那么二叉搜索树可能会退化为单支树，性能接近最差情况。

🔴三、二叉搜索树的操作

（一）插入

插入操作的步骤如下：

树为空：如果二叉搜索树为空，则直接创建一个新的结点，并将其赋值给根指针。
树不为空：从根结点开始，按照二叉搜索树的性质进行比较：
- 如果插入值小于当前结点的值，则向左子树移动。
- 如果插入值大于当前结点的值，则向右子树移动。
- 如果插入值等于当前结点的值（支持插入相等值的情况），可以选择向左或向右移动，但需要保持逻辑一致性。
找到空位置：当找到一个空位置时，创建一个新的结点，并将其插入到该位置。

（二）查找

查找操作的步骤如下：

从根开始：从根结点开始，将目标值与当前结点的值进行比较。
比较并移动：
- 如果目标值小于当前结点的值，则向左子树移动。
- 如果目标值大于当前结点的值，则向右子树移动。
查找结果：
- 如果在某个结点找到目标值，则返回该结点。
- 如果走到空结点仍未找到目标值，则说明目标值不存在。

（三）删除

删除操作相对复杂，需要分情况处理：

查找目标结点：首先查找要删除的结点是否存在。如果不存在，则返回false。
删除目标结点：如果目标结点存在，根据其子树情况分以下四种情况处理：
- 情况1：目标结点左右孩子均为空。
  - 直接删除该结点，并将其父结点对应的孩子指针置为空。
- 情况2：目标结点左孩子为空，右孩子不为空。
  - 将目标结点的父结点对应的孩子指针指向目标结点的右孩子，然后删除目标结点。
- 情况3：目标结点右孩子为空，左孩子不为空。
  - 将目标结点的父结点对应的孩子指针指向目标结点的左孩子，然后删除目标结点。
- 情况4：目标结点左右孩子均不为空。
  - 使用替换法删除。可以找目标结点左子树的最大值结点（最右结点）或者右子树的最小值结点（最左结点）替代目标结点。替代后，将问题转化为删除替代结点（替代结点符合情况2或情况3，可以直接删除）。

🔴四、二叉搜索树的实现代码

（一）结构体`BSTNode`

template<classK>structBSTNode{K _key;BSTNode<K>*_left;BSTNode<K>*_right;BSTNode(constK&key):_key(key),_left(nullptr),_right(nullptr){}};

（二）类`BSTree`

template<classK>classBSTree{typedefBSTNode<K>Node;public:boolInsert(constK&key){if(_root==nullptr){_root=newNode(key);returntrue;}Node*parent=nullptr;Node*cur=_root;while(cur){if(cur->_key<key){parent=cur;cur=cur->_right;}elseif(cur->_key>key){parent=cur;cur=cur->_left;}else{returnfalse;// 不允许插入重复值}}cur=newNode(key);if(parent->_key<key){parent->_right=cur;}else{parent->_left=cur;}returntrue;}boolFind(constK&key){Node*cur=_root;while(cur){if(cur->_key<key){cur=cur->_right;}elseif(cur->_key>key){cur=cur->_left;}else{returntrue;// 找到目标值}}returnfalse;// 未找到目标值}boolErase(constK&key){Node*parent=nullptr;Node*cur=_root;while(cur){if(cur->_key<key){parent=cur;cur=cur->_right;}elseif(cur->_key>key){parent=cur;cur=cur->_left;}else{// 情况1：左右孩子均为空if(cur->_left==nullptr&&cur->_right==nullptr){if(parent==nullptr){_root=nullptr;}else{if(parent->_left==cur)parent->_left=nullptr;elseparent->_right=nullptr;}deletecur;returntrue;}// 情况2：左孩子为空，右孩子不为空elseif(cur->_left==nullptr){if(parent==nullptr){_root=cur->_right;}else{if(parent->_left==cur)parent->_left=cur->_right;elseparent->_right=cur->_right;}deletecur;returntrue;}// 情况3：右孩子为空，左孩子不为空elseif(cur->_right==nullptr){if(parent==nullptr){_root=cur->_left;}else{if(parent->_left==cur)parent->_left=cur->_left;elseparent->_right=cur->_left;}deletecur;returntrue;}// 情况4：左右孩子均不为空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;elserightMinP->_right=rightMin->_right;deleterightMin;returntrue;}}}returnfalse;// 未找到目标值}voidInOrder(){_InOrder(_root);cout<<endl;}private:void_InOrder(Node*root){if(root==nullptr){return;}_InOrder(root->_left);cout<<root->_key<<" ";_InOrder(root->_right);}Node*_root=nullptr;};