系列文章目录

一：概念
二：实现
2.1 二叉搜索树的查找
2.2 二叉搜索树的插入
2.3 二叉搜索树的删除

---

一、搜索二叉树是什么？

二叉搜索树又称为二叉排序树或者是一棵空树。
性质
1.若它的左子树不为空，则左子树上所有节点都小于根节点。
2.若它的右子树不为空，则右子树的所有结点都大于根节点
3.它的左右子树称为二叉搜索树。

二、具体实现

1.二叉搜索树的查找

伪代码：
若果根节点不为空
如果根节点key=要查找的key,则返回true
如果根根节点key>要查找的key,在其左子树查找
如果根节点key<要查找的key,在其右子树查找
否则返回false;

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 false;}

2.二叉搜索树的插入

具体步骤：
1.树为空，则直接插入。

         2.树不空，按照二叉搜索树的性质查找插入位置，插入新节点。

代码实现：

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 < cur->_key){parent->_right = cur;}else{parent->_left = cur;}return true;}

3.二叉搜索树的删除
具体实现：
首先查找要删除的元素是否在搜索二叉树中，不存在则返回，否则删除分为以下情况。
1.要删除的节点没有孩子节点，
2.要删除的节点只有左孩子节点，
3.要删除的节点只有右孩子节点，
4.要删除的节点有左右孩子节点。

           其中有两个孩子的，删除的思路：找一个能代替删除的，这个代替删除的节点要比左边的值更大，比删除节点的右边值要大。找这个值的时候找左边的最大节点或右树的最小节点。右树的最左节点，左树的最又节点。

代码如下（示例）：
图解：

代码实现：

bool Erase(const k& key){Node* cur = _root;Node* parent = nullptr;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 (cur == parent->_left){parent->_left = cur->_right;}else{parent->_left = cur->_left;}delete cur;}else if (cur->_right == nullptr){parent->_left = cur->_left;}else{parent->_right = cur->_left;}delete cur;}else{找到右树最小节点去替代删除Node* minRightParent = cur;Node* minRight = cur->_right;while (minRight->_left){minRightParent = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;if (minRight == minRightparent->_left){minRightparent->_left = minRight->_right;}else{minRightparent->_right = minRight->_right;}delete minRight;}}}

# 总结
二叉搜索树可以应用到key模型中，K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。比如：给一个单词word，判断该单词是否拼写正确性能分析：插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平 均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：log2N最差情况下，二叉搜索树退化为单支树，其平均比较次数为：N/2