二叉搜索树，它或者是一棵空树，或者是具有以下性质的二叉树:
二叉搜索树的性质保证了其中序遍历是有序的，同时还天然去重，所以也称为二叉排序树
a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
b、最多查找高度次，走到到空，还没找到，这个值不存在。
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key > cur->_key)
{
cur = cur->_right;
}
else if (key < cur->_key)
{
cur = cur->_left;
}
else // 找到了
{
return cur;
}
}
// 没找到
return nullptr;
}
a. 树为空，则直接新增节点，赋值给root指针
b. 树不空，按二叉搜索树性质查找插入位置，插入新节点
// 非递归插入
bool Insert(const K& key)
{
if (_root == nullptr) // 空树
{
_root = new Node*(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
parent = cur;
if (cur->_key > key)
{
cur = cur->_left;
}
else if (cur->_key < key)
{
cur = cur->_right;
}
else // 找到了，插入失败
{
return false;
}
}
// 正常插入
Node* newNode = new Node(key, value);
if (key > parent->_key)
parent->_right = newNode;
else
parent->_left = newNode;
return true;
}
// 递归插入
bool InsertR(K key)
{
return _InsertR(_root, key);
}
// 注意需要传引用
bool _InsertR(Node*& root, K key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (key > root->_key)
return _InsertR(root->_right, key);
else if (key < root->_key)
return _InsertR(root->_left, key);
else
return false;
}
首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：
a. 要删除的结点无孩子结点
b. 要删除的结点只有左孩子结点
c. 要删除的结点只有右孩子结点
d. 要删除的结点有左、右孩子结点
看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程
如下：
// 非递归删除
bool Erase(K key)
{
Node* cur = _root;
Node* parent = nullptr;
while (cur) // 寻找需要删除的节点
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
{
break;
}
}
if (!cur) return false; // 没有找到
// 找到开始删除
// 1. 删除根节点
// 2. 删除普通节点
// 细分：
// 1. 左边没有节点
// 2. 右边没有节点
// 3. 左右都有节点：
// 1. 找到右子树的最左节点或者右子树的最右节点作为替换节点
// 2. 交换删除节点和替换节点的值
// 3. 更新链接关系
// 4. 删除替换节点
if (cur == _root) // 删除根节点
{
if (cur->_left == nullptr)
{
_root = cur->_right;
delete cur;
}
else if (cur->_right == nullptr)
{
_root = cur->_left;
delete cur;
}
else
{
Node* min = cur->_right;
Node* minParent = cur;
while (min->_left)
{
minParent = min;
min = min->_left;
}
::swap(cur->_key, min->_key);
if (min == minParent->_left)
{
minParent->_left = min->_right;
}
else
{
minParent->_right = min->_right;
}
delete min;
}
}
else // 删除非根节点
{
if (cur->_left == nullptr)
{
if (parent->_right == cur)
{
parent->_right = cur->_right;
}
else
{
parent->_left = cur->_right;
}
}
else if (cur->_right == nullptr)
{
if (parent->_right == cur)
{
parent->_right = cur->_left;
}
else
{
parent->_left = cur->_left;
}
}
else
{
Node* min = cur->_right;
Node* minParent = cur;
while (min->_left)
{
minParent = min;
min = min->_left;
}
swap(cur->_key, min->_key);
if (min == minParent->_left)
{
minParent->_left = min->_right;
}
else
{
minParent->_right = min->_right;
}
delete min;
}
}
return true;
}
// 递归删除
bool EraseR(K key)
{
return _EraseR(_root, key);
}
bool _EraseR(Node*& root, K key)
{
if (root == nullptr) return false;
if (key > root->_key)
return _EraseR(root->_right, key);
else if (key < root->_key)
return _EraseR(root->_left, key);
else
{
if (root->_right == nullptr) // 右为空
{
Node* del = root;
root = root->_left;
delete del;
return true;
}
else if (root->_left == nullptr) // 左为空
{
Node* del = root;
root = root->_right;
delete del;
return true;
}
else // 左右都不为空
{
Node* min = root->_right;
while (min->_left)
{
min = min->_left;
}
::swap(root->_key, min->_key);
return _EraseR(root->_right, key); // 转换为左右有一个为空的情况
}
}
}
二叉搜索树的所有操作都是基于查找上进行的，查找效率代表了二叉搜索树中各个操作的性能。
查找的效率是树的深度： O ( h ) O(h) O(h)
根据不同的数据，能得到结构不同的二叉搜索树：
最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为： O ( l o g 2 N ) O(log_2^N) O(log2N)
最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为： O ( N 2 ) O(\frac{N}{2}) O(2N)
后面我们学习的红黑树和AVL树就是在二叉搜索树的基础上通过旋转进行优化的。