1. 二叉搜索树的概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：
- 若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值。
- 若它的右子树不为空，则右子树上所有结点的值都大于等于根结点的值。
- 它的左右子树也分别为二叉搜索树。
二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义，map/set/multimap/multiset 系列容器底层就是二叉搜索树，其中 map/set 不支持插入相等值，multimap/multiset 支持插入相等值。
2. 二叉搜索树的性能分析
最优情况下，二叉搜索树为完全二叉树 (或者接近完全二叉树)，其高度为：log2 N 最差情况下，二叉搜索树退化为单支树 (或者类似单支)，其高度为：N 所以综合而二叉搜索树增删查改时间复杂度为：O(N)
二分查找也可以实现 O(log2 N) 级别的查找效率，但是二分查找有两大缺陷：
- 需要存储在支持下标随机访问的结构中，并且有序。
- 插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据。
这里也就体现出了平衡二叉搜索树的价值。
3. 二叉搜索树的插入
- 树为空，则直接新增结点，赋值给 root 指针
- 树不空，按二叉搜索树性质，插入值比当前结点大往右走，插入值比当前结点小往左走找到空位置，插入新结点。
- 如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点。（要注意的是要保持逻辑一致性，插入相等的值不要一会往右走，一会往左走）
4. 二叉搜索树的查找
- 从根开始比较，查找 x，x 比根的值大则往右边走查找，x 比根值小则往左边走查找。
- 最多查找高度次，走到到空，还没找到，这个值不存在。
- 如果不支持插入相等的值，找到 x 即可返回
- 如果支持插入相等的值，意味着有多个 x 存在，一般要求查找中序的第一个 x。
5. 二叉搜索树的删除
首先查找元素是否在二叉搜索树中，如果不存在，则返回 false。 如果查找元素存在则分以下四种情况分别处理：（假设要删除的结点为 N）
- 要删除结点 N 左右孩子均为空
- 要删除的结点 N 左孩子位空，右孩子结点不为空
- 要删除的结点 N 右孩子位空，左孩子结点不为空
- 要删除的结点 N 左右孩子结点均不为空
对应以上四种情况的解决方案：
- 把 N 结点的父亲对应孩子指针指向空，直接删除 N 结点（情况 1 可以当成 2 或者 3 处理，效果是一样的）
- 把 N 结点的父亲对应孩子指针指向 N 的右孩子，直接删除 N 结点
- 把 N 结点的父亲对应孩子指针指向 N 的左孩子，直接删除 N 结点
无法直接删除 N 结点，因为 N 的两个孩子无处安放，只能用替换法删除。找 N 左子树的值最大结点 R(最右结点) 或者 N 右子树的值最小结点 R(最左结点) 替代 N，因为这两个结点中任意一个，放到 N 的位置，都满足二叉搜索树的规则。替代 N 的意思就是 N 和 R 的两个结点的值交换，转二变成删除 R 结点，R 结点符合情况 2 或情况 3，可以直接删除。
6. 二叉搜索树的实现代码
template<class K>
struct BSTNode {
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;
BSTNode(const K& key) : _key(key), _left(nullptr), _right(nullptr) {}
};
// Binary Search Tree
template< >
{
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;
} {
;
}
}
;
}
{
Node* parent = ;
Node* cur = _root;
(cur) {
(cur->_key < key) {
parent = cur;
cur = cur->_right;
} (cur->_key > key) {
parent = cur;
cur = cur->_left;
} {
(cur->_left == ) {
(parent == ) {
_root = cur->_right;
} {
(parent->_left == cur) parent->_left = cur->_right;
parent->_right = cur->_right;
}
cur;
;
} (cur->_right == ) {
(parent == ) {
_root = cur->_left;
} {
(parent->_left == cur) parent->_left = cur->_left;
parent->_right = cur->_left;
}
cur;
;
} {
Node * rightMinP = cur;
Node* rightMin = cur->_right;
(rightMin->_left) {
rightMinP = rightMin;
rightMin = rightMin->_left;
}
cur->_key = rightMin->_key;
(rightMinP->_left == rightMin) rightMinP->_left = rightMin->_right;
rightMinP->_right = rightMin->_right;
rightMin;
;
}
}
}
;
}
{
_InOrder(_root);
cout << endl;
}
:
_InOrder(Node* root) {
(root == ) {
;
}
_InOrder(root->_left);
cout << root->_key << ;
_InOrder(root->_right);
}
:
Node * _root = ;
};
