震惊,搜索二叉树告诉我们不要生二胎?本篇(带图)让你轻松拿下

引子:

二叉树作为一种常见的一种数据结构,我们也经常使用,有以下几种类型:满二叉树(Full Binary Tree):所有节点都恰好有两个子节点或没有子节点。完全二叉树(Complete Binary Tree):如果一个二叉树的深度为h,除了最后一层外,所有层的节点数都是最大(即每个层都是满的),并且最后一层的节点尽可能地集中在左侧。平衡二叉树(Balanced Binary Tree):任何两个子树的高度差不超过1。二叉搜索树(Binary Search Tree, BST):对于每个节点,左子树上的所有节点的值都小于该节点的值,右子树上的所有节点的值都大于该节点的值,今天我们就来讲一讲搜索二叉树的实现!

set底层略介绍:

set 的底层实现通常依赖于哈希表(Hash Table)或平衡二叉搜索树(如红黑树)。以下是两种常见的实现方式

应用场景

  • 去重:快速检查元素是否已经存在于集合中。
  • 集合操作:执行并集、交集、差集等操作,常用于数据分析和统计。
  • 快速查找:在大量数据中快速定位元素

以下是cplusplus中的介绍:

 

故,与我们今天要讲的搜索二叉树有相通之处!

正文(基本思路与代码实现):

基本思路:

什么是二叉搜索树:

二叉搜索树(Binary Search Tree,简称BST)是一种特殊的二叉树,它具有以下性质:

  1. 有序性:对于树中的每个节点,其左子树上的所有节点的值都小于该节点的值,其右子树上的所有节点的值都大于该节点的值。
  2. 唯一性:树中没有重复的节点。

基本操作

  1. 插入(Insertion)

    • 从根节点开始,比较新节点的值与当前节点的值。
    • 如果新节点的值小于当前节点的值,则移动到当前节点的左子节点;否则,移动到右子节点。
    • 重复上述步骤,直到找到一个空的子节点位置,将新节点插入。
  2. 删除(Deletion)

    • 首先找到要删除的节点。
    • 如果该节点没有子节点,直接删除它。
    • 如果该节点只有一个子节点,删除该节点,并用其子节点替换它。
    • 如果该节点有两个子节点,找到其右子树的最小节点(或左子树的最大节点),将这个节点的值复制到要删除的节点,然后删除这个最小(或最大)节点。
  3. 搜索(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;
}

"感谢您花时间阅读这篇文章。我希望它能给您带来一些有价值的见解和启发。如果您有任何想法或问题,请在评论区告诉我,我很乐意听到您的声音。别忘了点赞我的博客,哈哈哈!"

上一篇:【BUG】已解决:java.lang.reflect.InvocationTargetException


下一篇:Oracle TDE(Transparent Data Encryption) 常见问题解答 - 官网-标准与合规性