美文网首页
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