二叉搜索树
二叉搜索树： 又为搜索二叉树，一般具有以下的性质
- 若它的左子树不为空，则左子树上所有的节点的值都小于父亲节点
- 若它的右子树不为空，则右子树上所有的节点的值都大于父亲节点
- 它的左右子树也都为二叉搜索树
二叉搜索树操作：
以下面图示例子
int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
1、二叉搜索树的查找
- 从根开始比较，查找，比根大就往右子树走，比根小就往左子树走
- 最多查找树的高度，如果走到空，就说明没有这个值，查找失败
bool Find(const K& key)
{
Node* cur = _root;
if(cur->_key> key)
{
cur = cur->_left;
}
else if(cur->_key < key)
{
cur = cur->_right;
}
else
{
return true;
}
return false;
}
2、二叉搜索树的插入
插入的具体过程如下：
- 树为空，则直接新增节点，赋值给root指针
- 树不为空，按二叉搜索树性质查找新增位置，插入新增节点
- 如果插入的值与它本身的值相等，就失败，二叉搜索树中不能有相同的值
bool Insert(const K& key)
{
//判断是不是空
if(_root == nullptr)
{
_root = new Node(key);
return true;
}
//不是空，就插入
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
{
return false;
}
}
//到这里说明是空
cur = new Node(key);
//链接
if(parent->_key > key)
parent->_left = cur;
else parent->_right = cur;
return true;
}
3、二叉搜索树的删除
首先查找元素是否存在二叉搜索树中，如果不存在，则返回，否则要删除的节点要分以下四种情况：
- 要删除的节点无孩子节点
- 要删除的节点只有左孩子
- 要删除的节点只有右孩子
- 要删除的节点有左右孩子
首先这里可以说是三种情况，因为如果没有孩子节点，那么就会进入到只有左孩子或者只有右孩子的节点的情况。
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while(cur)
{
if(cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if(cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
{
//cur的左为空
if(cur->_left == nullptr)
{
if(cur == _root)
_root = cur->_right;
else
{
if(cur == parent->_left)
{
parent->_left = cur->_right;
}
else if(cur == parent->_right)
{
parent->_right = cur->_right;
}
}
delete cur;
return true;
}
else if(cur->_right == nullptr)// cur->_right为空
{
if(cur == _root)
_root = cur->_right;
else
{
if(cur == parent->_left)
parent->_left = cur->_left;
else if(cur == parent->_right)
parent->_right = cur->_left;
}
delete cur;
return true;
}
else
{
//替换法 右数最小节点或者左树最大节点,然后赋值，删除最小/最大节点
//如果都不为空
Node* rightMinParent = cur; //这里必须赋值为cur，因为如果是头删这里就会有问题
Node* rightMin = cur->_right;
//找右数中最小的值
while(rightMin->_left)
{
rightMinParent = rightMin;
rightMin = rightMin->_left;
}
cur->_key = rightMin->_key;
//此时rightMin的左子树为空，右子树可能有值
if(rightMin == rightMinParent->_left)
rightMinParent->_left = rightMin->_right;
else rightMinParent->_right = rightMin->_right;
delete rightMin;
return true;
}
}
}
return false;
}
二叉搜索树的性能分析：
二叉搜索树的插入和删除操作都需要查找，所以查找是二查搜索树中的性能关键。
如果有n个节点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树的平均查找长度的关键就在于树的深度。
如果树是一颗二叉平衡搜索二叉树，那么查找的效率就是O（logN）
当然也有特殊的场景，如下图所示，它的查找效率就会变得非常慢，平均比较次数就达到了O（N^2）
