1. 二叉搜索树的概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：
- 若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值。
- 若它的右子树不为空，则右子树上所有结点的值都大于等于根结点的值。
- 它的左右子树也分别为二叉搜索树。
- 二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义。后续我们学习 map/set/multimap/multiset 系列容器底层就是二叉搜索树，其中 map/set 不支持插入相等值，multimap/multiset 支持插入相等值。
主要功能是搜索、排序。
那么我们怎么进行查找操作呢？
因为我们这里的是搜索二叉树，左子树比根节点小，右子树比根节点大。我们现在想去找这个 4，4 比 8 小，那么我们就没必要去右子树进行查找了，我们直接在左子树进行查找就行了。然后 4 比 3 大，那么我们直接在右子树上面找。4 比 6 小，直接在左子树上找，然后就找到了。
那么我们在搜索二叉树中进行数据的查找的话，那么我们只需要寻找高度次就可以找到对应的数据了。有点像之前学习的二分查找，效率是 logN。
但是存在缺陷：
- 要求有序。
- 底层结构要求是数组，头部或者中间插入删除数据效率很低。
排序的话那么就是按照中序遍历的话，那么整个排序出来的数组就是升序的，所以搜索二叉树的功能之一是排序。
2. 二叉搜索树的性能分析
最优情况下，二叉搜索树为完全二叉树 (或者接近完全二叉树)，其高度为：log₂N。 最差情况下，二叉搜索树退化为单支树 (或者类似单支)，其高度为：N。
所以综合而言二叉搜索树增删查改时间复杂度为：O(N)。
那么这样的效率显然是无法满足我们需求的，我们后续课程需要继续讲解二叉搜索树的变形，平衡二叉搜索树 AVL 树和红黑树，才能适用于我们在内存中存储和搜索数据。另外需要说明的是，二分查找也可以实现 O(log₂N) 级别的查找效率，但是二分查找有两大缺陷：
- 需要存储在支持下标随机访问的结构中，并且有序。
- 插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据。
这里也就体现出了平衡二叉搜索树的价值。
二叉树效率不错的前提是左右节点比较均衡接近完全二叉树。
3. 二叉搜索树的插入
插入的具体过程如下：
- 树为空，则直接新增结点，赋值给 root 指针。
- 树不空，按二叉搜索树性质，插入值比当前结点大往右走，插入值比当前结点小往左走，找到空位置，插入新结点。
- 如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点（要注意的是要保持逻辑一致性，插入相等的值不要一会往右走，一会往左走）。
4. 二叉搜索树的查找
- 从根开始比较，查找 x，x 比根的值大则往右边走查找，x 比根值小则往左边走查找。
- 最多查找高度次，走到到空，还没找到，这个值不存在。
- 如果不支持插入相等的值，找到 x 即可返回。
- 如果支持插入相等的值，意味着有多个 x 存在，一般要求查找中序的第一个 x。
#pragma once
#include<iostream>
using namespace std;
template<class k>
struct BSTNode {
k _key;
BSTNode<k>* _left;
BSTNode<k>* _right;
BSTNode(const k& key) :_key(key), _left(), _right() {}
};
< >
{
BSTNode<k> Node;
:
{
(_root == ) {
_root = (key);
;
}
Node* parent = ;
Node* cur = _root;
(cur) {
(cur->_key < key) {
parent = cur;
cur = cur->_right;
} (cur->_key > key) {
parent = cur;
cur = cur->_left;
} {
;
}
}
cur = (key);
(parent->_key < key) {
parent->_right = cur;
} {
parent->_left = cur;
}
;
}
{
Node* cur = _root;
(cur) {
(cur->_key < key) {
cur = cur->_right;
} (cur->_key > key) {
cur = cur->_left;
} {
;
}
}
;
}
:
_InOrder(Node* root) {
(root == ) ;
_InOrder(root->_left);
cout << root->_key << ;
_InOrder(root->_right);
}
Node* _root = ;
};
