美文网首页
2022-08-12 算法学习——二叉搜索树BST

2022-08-12 算法学习——二叉搜索树BST

作者: Lovevivi | 来源:发表于2024-03-23 02:18 被阅读0次

    首先有插入查找排名x的数,查找x数字的排名,查找x

    排名的前驱或者后驱的数字,删除等操作
    所以可以用stl的multiset来完成(好东西)

    #include <bits/stdc++.h>
    using namespace std;
    typedef multiset<int>::iterator sett;//每次都写太长了,typedef一下 
    sett c,d;//定义2个迭代器 
    int main()
    {
        int n,a,x;
        multiset<int> s1;
        cin>>n;
        s1.insert(2147483647);//为防止没有后继,手动添加一个最大值 
        while(n--)
        {
            cin>>a>>x;
            switch(a){
                case 1:{//查询 x数的排名 
                    c=s1.lower_bound(x);//二分查找第一个x出现的位置 
                    int num=1;//计数器 
                    for(d=s1.begin();d!=c;++d)//从第一个开始跑,直到到了第一个x 
                    ++num;
                    cout<<num<<"\n";//输出num 
                    break;
                }
                case 2:{//查询排名为x的数
                    int num=1;
                    for(d=s1.begin();num<x;++num)//不会pbds,只能手动一个一个加了 
                    ++d;
                    cout<<*d<<"\n";
                    break;
                }
                case 3:{//求x的前驱 
                    c=s1.lower_bound(x);//二分查找第一个x出现的位置 
                    --c;//那他前面一个必然是前驱 
                    cout<<*c<<"\n";
                    break;
                }
                case 4:{//求x的后继
                    c=s1.upper_bound(x);//二分查找第一个大于x的位置 
                    cout<<*c<<"\n";
                    break;
                }
                case 5:{//插入一个数x
                    s1.insert(x);//插入元素 
                    break;
                }
            }
        }
        return 0;
    }
    

    相关文章

      网友评论

          本文标题:2022-08-12 算法学习——二叉搜索树BST

          本文链接:https://www.haomeiwen.com/subject/oamfgrtx.html