引子:
二叉树作为一种常见的一种数据结构,我们也经常使用,有以下几种类型:满二叉树(Full Binary Tree):所有节点都恰好有两个子节点或没有子节点。完全二叉树(Complete Binary Tree):如果一个二叉树的深度为h
,除了最后一层外,所有层的节点数都是最大(即每个层都是满的),并且最后一层的节点尽可能地集中在左侧。平衡二叉树(Balanced Binary Tree):任何两个子树的高度差不超过1。二叉搜索树(Binary Search Tree, BST):对于每个节点,左子树上的所有节点的值都小于该节点的值,右子树上的所有节点的值都大于该节点的值,今天我们就来讲一讲搜索二叉树的实现!
set底层略介绍:
set
的底层实现通常依赖于哈希表(Hash Table)或平衡二叉搜索树(如红黑树)。以下是两种常见的实现方式
应用场景
- 去重:快速检查元素是否已经存在于集合中。
- 集合操作:执行并集、交集、差集等操作,常用于数据分析和统计。
- 快速查找:在大量数据中快速定位元素
以下是cplusplus中的介绍:
故,与我们今天要讲的搜索二叉树有相通之处!
正文(基本思路与代码实现):
基本思路:
什么是二叉搜索树:
二叉搜索树(Binary Search Tree,简称BST)是一种特殊的二叉树,它具有以下性质:
- 有序性:对于树中的每个节点,其左子树上的所有节点的值都小于该节点的值,其右子树上的所有节点的值都大于该节点的值。
- 唯一性:树中没有重复的节点。
基本操作
-
插入(Insertion):
- 从根节点开始,比较新节点的值与当前节点的值。
- 如果新节点的值小于当前节点的值,则移动到当前节点的左子节点;否则,移动到右子节点。
- 重复上述步骤,直到找到一个空的子节点位置,将新节点插入。
-
删除(Deletion):
- 首先找到要删除的节点。
- 如果该节点没有子节点,直接删除它。
- 如果该节点只有一个子节点,删除该节点,并用其子节点替换它。
- 如果该节点有两个子节点,找到其右子树的最小节点(或左子树的最大节点),将这个节点的值复制到要删除的节点,然后删除这个最小(或最大)节点。
-
搜索(Search):
- 从根节点开始,比较要搜索的值与当前节点的值。
- 如果值小于当前节点的值,则移动到左子节点;否则,移动到右子节点。
- 重复上述步骤,直到找到目标值或到达空的子节点。
特点
- 时间复杂度:在最坏的情况下(树退化为链表),插入、删除和搜索的时间复杂度为 O(n)。在最好的情况下(树完全平衡),这些操作的时间复杂度为 O(log n)。
- 空间复杂度:O(n),其中 n 是树中节点的数量。
最坏情况:
应用
- 数据存储和检索:由于其有序性,二叉搜索树常用于存储和检索数据。
- 排序算法:如归并排序和快速排序中的分治策略。
- 动态数据集:在需要频繁插入和删除数据的场景中,二叉搜索树是一个有效的数据结构。
变种
- 平衡二叉搜索树(如AVL树):通过保持树的高度平衡,确保所有操作的时间复杂度为 O(log n)。
- 红黑树:通过引入颜色标记和旋转操作,保持树的大致平衡,确保操作的时间复杂度为 O(log n)。
代码实现:
template<class T>
struct SBTreeNode //默认是公有的
{
T _key;
SBTreeNode<T>* _left;
SBTreeNode<T>* _right;
SBTreeNode(const T& key)
:_key(key)
,_left(nullptr)
,_right(nullptr)
{}
};
template<class T>
class SBtree
{
typedef SBTreeNode<T> Node;
public:
bool insert(const T& key)
{
//没有值就添加
if (_root==nullptr)
{
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* current = _root;
while (current)
{
if (current->_key < key)
{
parent = current;
current = current->_right;
}
else if (current->_key > key)
{
parent = current;
current = current->_left;
}
else
{
return false;
}
}
//新增节点再链接上去
current = new Node(key);
if (key > (parent->_key))
{
parent->_right = current;
}
else if (key < (parent->_key))
{
parent->_left = current;
}
return true;
}
bool find(const T&key)
{
Node* current = _root;
while (current)
{
if (current->_key < key)
{
current = current->_right;
}
else if(current->_key>key)
{
current = current->_left;
}
else
{
return true;
}
}
return false;
}
//中序有序,避免了_root是内部private的加密
void _InOrder()
{
_InOrder(_root);
printf("\n");
}
删除有3种情况:
bool Erase(const T& 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
{
if (cur->_left == nullptr)
{
if (parent == nullptr)
_root = cur->_right;
else
{
if (parent->_right == cur)
parent->_right = cur->_right;
else
parent->_left = cur->_right;
}
delete cur;
return true;
}
else if(cur->_right == nullptr)
{
if (parent == nullptr)
_root = cur->_left;
else
{
if (parent->_right == cur)
parent->_right = cur->_left;
else
parent->_left = cur->_left;
}
delete cur;
return true;
}
//二个孩子的节点
else
{
Node* rightMinParent = cur;
Node* rightMin = cur->_right;
while (rightMin->_left)
{
rightMinParent = rightMin;
rightMin = rightMin->_left;
}
cur->_key = rightMin->_key;
if (rightMinParent->_left == rightMin)
rightMinParent->_left = rightMin->_right;
else
rightMinParent->_right = rightMin->_right;
delete rightMin;
return true;
}
}
}
return false;
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
//左根右;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
//要赋予初始值
Node* _root=nullptr;
};
int main()
{
SBtree<int> high;
int a[] = { 12,32,54,75,342,7567,2, 2};
for (auto e : a)
{
high.insert(e);
}
high._InOrder();
high.Erase(32);
high._InOrder();
high.Erase(75);
high._InOrder();
high.Erase(54);
return 0;
}