目录

一、二叉搜索树概念

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

三、二叉搜索树的构建

---

一、二叉搜索树概念

二叉搜索树又叫做二叉排序树，它可以是一颗空树，或者是具有以下性质的二叉树：

• 若该树的左子树不为空，那么左子树上的任一节点都小于等于根节点的值。
• 若该树的右子树不为空，那么右子树上的任一节点都大于等于根节点的值。
• 该树的左右子树也为二叉搜索树。
• 二叉搜索树可以支持插入相等的值，也可以不支持插入相等的值。

如上图，为一个基本的二叉搜索树。本文将以不插入相等的值的二叉搜索树为例。

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

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其高度为(log2 N)，例如上方的二叉搜索树。

最差情况下，二叉搜索树退化为单支树(或者类似单支)，其高度为(N/2 ~ N)，例如：

综上所述，二叉搜索树的增删查改的时间复杂度为:O(N)。

三、二叉搜索树的构建

1. 基本框架

template<class K>
struct BSNode
{BSNode(const K& key):_key(key), _left(nullptr), _right(nullptr){}K _key;BSNode<K>* _left;BSNode<K>* _right;
};template<class K>
class BSTree
{
public:using Node = BSNode<K>;
private:Node* _root = nullptr;int _num = 0;
};

我们以BSNode类，来构建二叉搜索树的每一个节点，这个节点有指向左右子树的指针_left和_right，并且每个节点都有一个值被_key所存储。

然后在BSTree类，是我们二叉搜索树的大框架，里面有着根节点_root，并且有着节点的数量_num。

2. 二叉搜索树的插入

bool _Insert(const K& key)
{Node* newnode = new Node(key);if (_root == nullptr){_root = newnode;_num++;return true;}else{Node* parent = nullptr;Node* cur = _root;while (cur){if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}elsereturn false;}if (key < parent->_key){_num++;parent->_left = newnode;}if (key > parent->_key){_num++;parent->_right = newnode;}return true;}return false;
}

二叉搜索树的插入还是比较简单的，首先，我们要以传入的key值创建一个newnode的节点，如果根节点为空，那么直接把newnode给根节点，然后返回即可。

因为二叉搜索树的特殊性，所有左子树节点的值小于根节点，所有右子树节点的值大于根节点。因此当我们插入一个值(cur)时，首先要对到达的节点的值比较，如果跟该节点的值相等，因为我们讨论的是不支持有重复的值，返回false即可。

如果key小于该节点的值，那么我们就向该节点的左子树走，反之向该节点的右子树走，cur走到空，说明此处就是我们要插入的地方。因为我们提前已经创建parent指针来记录cur的父亲，所以此时我们只需要比较key的值和parent的值，然后决定插入在parent的左子树还是右子树即可。

3. 二叉树的查找

bool Find(const K& key)
{assert(_root != nullptr);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;
}

查找还是比较简单的，首先根节点不能为空，否则查找无意义。然后我们就和插入一样，从根节点开始，将我们要查找的key值与此时节点的值比较，key小就向节点的左子树走，key大就向节点的右子树走，若相等就返回true即找到了。如果cur都走到空了，那么就返回false即树中没有key值。

4. 二叉树的删除

二叉树的删除还是比较麻烦的，要分为以下四种情况：

1. 该节点的左右子树均为空。
2. 该节点的左子树为空，右子树不为空。
3. 该节点的右子树为空，左子树不为空。
4. 该节点的左右子树军不为空。

Node* cur = _root;
Node* parent = cur;
while (cur != nullptr && cur->_key != key)
{if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}	
}
//先找到要删除的cur节点，并记录该节点的父节点。

对于情况1，比较好处理，因为我们完全可以找到该节点，并记录该节点的父节点，然后直接删除该节点并且让父节点的对应指针指向空即可。

if (cur->_left == nullptr && cur->_right == nullptr)
{if (cur->_key < parent->_key)parent->_left = nullptr;elseparent->_right = nullptr;delete cur;_num--;return true;
}

对于情况2，3我们可以同样地处理，以2为例。如果该节点的左子树为空，那么我们找到该节点后，并且记录了父节点，直接将父节点指向该节点的指针，指向该节点的右子树，然后直接删除该节点即可。情况3相同，只是注意左右子树不同。

else if(cur->_left == nullptr)
{Node* r_parent = cur;Node* r_root = cur->_right;while (r_root->_left){r_parent = r_root;r_root = r_root->_left;}if (r_parent->_key > r_root->_key)r_parent->_left = r_root->_right;else if (r_parent->_key < r_root->_key)r_parent->_right = r_root->_right;cur->_key = r_root->_key;delete r_root;_num--;return true;
}
else if (cur->_right == nullptr)
{Node* l_parent = cur;Node* l_root = cur->_left;while (l_root->_right){l_parent = l_root;l_root = l_root->_right;}if (l_parent->_key > l_root->_key)l_parent->_left = l_root->_left;else if (l_parent->_key < l_root->_key)l_parent->_right = l_root->_left;cur->_key = l_root->_key;delete l_root;_num--;return true;
}

对于情况4，我们不能直接删除该节点，因为该节点左右子树均不为空。我们此时就可以使用替换法。找到该节点(N)左子树的最大节点(L)或者右子树的最小节点(R)来替换该节点的值，因为这两个节点中的任意一个，放到N的位置，都不会破坏整个二叉搜索树的性质，然后我们删除交换后废弃的节点即可。例如：

我们要删除3这个节点，3的左子树根节点为1，右子树根节点为6，那么左子树最大的值为2，右子树最小的值为4，所以我们将2/4与3交换后不会改变整个二叉搜索树的性质。我们以交换4为例：

这样就实现了二叉搜索树的删除，也没有破坏本来的性质，注意如果4的右子树还有节点，那么交换后3的右子树就会有节点，那么我们只需要将6的左指针指向3的右子树即可。

else
{/*Node* parent = cur;Node* root = cur->_right;*/Node* r_parent = cur;Node* r_root = cur->_right;while (r_root->_left){r_parent = r_root;r_root = r_root->_left;}if (r_parent->_key > r_root->_key)r_parent->_left = r_root->_right;else if (r_parent->_key < r_root->_key)r_parent->_right = r_root->_right;cur->_key = r_root->_key;delete r_root;_num--;return true;
}

注意，如果一开始根节点本来就为空，那么我们不需要删除，直接返回false即可，如果树只有一个节点，也就是_num为1，我们直接将_root给为nullptr即可：

if (cur == nullptr)
{return false;
}
if (_num == 1)
{_root = nullptr;_num = 0;return true;
}

整个删除的框架如下，最终只需将上述所以删除代码加入即可：

bool _Erase(const K& key)
{Node* cur = _root;Node* parent = cur;while (cur != nullptr && cur->_key != key){//查找要删除的节点位置，并且记录父节点}if (cur == nullptr){return false;//如果树为空或者没找到，直接返回false}if (_num == 1){//只有一个节点情况}if (cur->_left == nullptr && cur->_right == nullptr){//该节点左右子树均为空}else if(cur->_left == nullptr){//该节点左子树为空}else if (cur->_right == nullptr){//该节点右子树为空}else{该节点左右子树均不为空}return false;
}

以上内容如有错误，欢迎批评指正！！！