何为二叉搜索树
二叉搜索 (排序) 树具有如下特征：
若它的左子树不为空，则**左子树上所有结点的值都小于等于根结点的值；若它的右⼦树不为空，则右子树上所有结点的值都大于等于根结点的值；它的左右⼦树也分别为二叉搜索树；二叉搜索树的中序遍历是有序的；**了解二叉搜索树是为了之后为 map/set/multimap/multiset 的关联式容器打下基础。特别地，二叉搜索树分为冗余和不冗余版本。(冗余即有相等值也可插入)
在冗余版本的二叉搜索树中，会出现如下两种情况，那这两都是正确的吗？
是的，并不影响搜索二叉树的性质。
性能分析
可以发现在该二叉搜索树较为平衡的情况下，即在最优情况下，找到指定结点的情况下，只需要访问高度 k 次，即高度为：log₂N；但在最差情况下，高度会达到 N。（在红黑树章节会有详解如何平衡高度差）
综合来讲，二叉搜索树增删查改时间复杂度为：O(N)。
二分查找也能达到 log₂N 级别的查找效率，为何不使用二分查找呢？二分查找有以下缺陷：**需要存储在支持下标随机访问的结构中，并且有序。插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据。**二叉搜索树在最差情况下能达到 O(N) 级别，那它能起到什么作用呢？二叉搜索树的引入是为了后续为平衡二叉树 AVL 树和红⿊树作铺垫，之后引入了旋转的概念，能够好维持二叉树的结构。
搜索树的结构
template<class K> struct BSTreeNode {
K _key;
BSTreeNode<K>* _left;
BSTreeNode<K>* _right;
BSTreeNode(const K& key) :_key(key) ,_left(nullptr) ,_right(nullptr) {}
};
插入和查找 (非冗余版本)
插入时分为以下情况：
- 树为空时，申请一个新结点赋值给根结点_root;
- 树不为空时，插⼊值⽐当前结点⼤往右⾛，插⼊值⽐当前结点⼩往左⾛，找到空位置，插⼊新结点。(如若支持冗余，则可往左走，也可往右走，确保逻辑一致性)
{
(_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->_left = cur;
} {
parent->_right = cur;
}
;
}
