目录

一、搜索二叉树的概念

二、搜索二叉树的基本结构 

 三、搜索二叉树的插入

四、搜索二叉树的查找

五 、搜索二叉树的删除

---

一、搜索二叉树的概念

⼆叉搜索树⼜称⼆叉排序树，它或者是⼀棵空树，或者是具有以下性质的⼆叉树：

• 若它的左子树不为空，则左子树上所有结点的值都⼩于等于根结点的值
• 若它的右子树不为空，则右子树上所有结点的值都⼤于等于根结点的值
• 它的左右子树也分别为⼆叉搜索树
• 最优情况下，⼆叉搜索树为完全⼆叉树(或者接近完全⼆叉树)，其⾼度为：O() 
• 最差情况下，⼆叉搜索树退化为单⽀树(或者类似单⽀)，其⾼度为：O()
• 综合而言⼆叉搜索树增删查改时间复杂度为：O(N) 

二、搜索二叉树的基本结构 

 搜索二叉树的结构跟二叉树差不多——两个指针来指向左右子树，一个对象来存放数据。

template<class K>
struct BSTNode
{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(const K& key):_key(key), _left(nullptr), _right(nullptr){}
};template<class K>
class BSTree
{
typedef BSTNode<K> Node;
public:……
preivate:Node* _root = nullptr;
}

---

 三、搜索二叉树的插入

1. 树为空树，new一个节点，然后赋值给_root。
2. 树不为空树，按⼆叉搜索树性质，插⼊值比当前结点大往右走，插⼊值比当前结点小往左走，找到空位置，插⼊新结点。

注：这里不考虑插入值与节点的值相等的情况。

bool Insert(const K& key)
{//当_root为空树if (_root == nullptr){_root = new Node(key);return true;} //当_root不为空树//创建一个parent节点来记录上一层的位置//创建一个cur节点来判断插入位置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;}    
}

---

四、搜索二叉树的查找

1. 从根开始比较，查找x，x比根的值大则往右边走查找，x比根值小则往左边走查找。
2. 最多查找⾼度次，⾛到到空，还没找到，这个值不存在。

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

 注：若支持插入相同的值，⼀般要求查找中序的第⼀个x，像下面这样↓，有多个值6，返回中序查找的第一个6。

---

五 、搜索二叉树的删除

        搜索二叉树的删除就复杂多了，会有下面四种情况：

1. 要删除结点N左右孩子均为空。
2. 要删除的结点N左孩子位空，右孩子结点不为空。
3. 要删除的结点N右孩子位空，左孩子结点不为空。
4. 要删除的结点N左右孩子结点均不为空。

 对应以上四种情况的解决⽅案：

1. 把N结点的父亲对应孩子指针指向空，直接删除N结点（情况1可以当成2或者3处理，效果是⼀样的）
2. 把N结点的父亲对应孩子指针指向N的右孩子，直接删除N结点
3. 把N结点的父亲对应孩子指针指向N的左孩子，直接删除N结点
4. 无法直接删除N结点，因为N的两个孩子无处安放，只能用替换法删除。找N左子树的值最大结点R(最右结点)或者N右子树的值最小结点R(最左结点)替代N，因为这两个结点中任意⼀个，放到N的位置，都满足⼆叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换，转而变成删除R结点，R结点符合情况2或情况3，可以直接删除。

注(4)：这里使用找N左子树的值最大结点R(最右结点)

bool Erase(const K& key)
{Node* cur = _root;Node* prev = nullptr;while(cur){ if (key < cur->_key){prev = cur;cur = cur->_left;}else if (cur->_key < key){prev = cur;cur = cur->_right;}else{//找到了//只有一边或没有子叶if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (prev->_right == cur){prev->_right = cur->_left;}else{prev->_left = cur->_left;}}delete cur;}else if(cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (prev->_right == cur){prev->_right = cur->_right;}else{prev->_left = cur->_right;}}delete cur;}else{//找到了有两个子叶Node* treep = cur;Node* treec = cur->_right;while (treec->_left){treep = treec;treec = treec->_left;}cur->_key = treec->_key;if (treep->_left == treec)treep->_left = treec->_right;elsetreep->_right = treec->_right;delete treec;}return true;}}return false;
}