데이터 구조 연구 의 10 고등 데이터 구조

1. 상호 질량 집합:
a. 정의: Disjoint Sets 는 상호 집합 으로 데 이 터 를 분류 관리 하 는 데이터 구조 이다.
b. 코드:

//
// Created by    on 2018/2/6.
//      
//

#include "iostream"
#include "vector"

using namespace std;

class DisjointSet{
public :
    vector rank,p;

    DisjointSet(){}
    DisjointSet(int size) {
        rank.resize(size, 0);
        p.resize(size, 0);
        for (int i = 0; i < size; i++) makeSet(i);
    }

    void makeSet(int x) {
        p[x] = x;
        rank[x] = 0;
    }

    bool same(int x, int y) {
        return findSet(x) == findSet(y);
    }

    void unite(int x,int y){
        link(findSet(x) ,findSet(y));
    }

    void link(int x,int y){
        if ( rank[x] > rank[y] ){
            p[y] = x;
        }else{
            p[x] = y;
            if ( rank[x] == rank[y]){
                rank[y] ++;
            }
        }
    }

    int findSet(int x){
        if ( x!= p[x]){
            p[x] = findSet(p[x]);
        }
        return p[x];
    }
};

int main(){
    int n,a,b,q,t;

    cin >> n >> q;
    DisjointSet ds = DisjointSet(n);

    for ( int i = 0 ; i < q ; i ++){
        cin >> t >> a >> b;
        if ( t == 0) ds.unite(a,b);
        else if ( t == 1 ){
            if ( ds.same(a,b) ) cout << 1 << endl;
            else cout << 0 << endl;
        }
    }
}

2. 범위 검색:
a. 제목: 주어진 점 이 주어진 사각형 안에 있 는 지 판단 합 니 다.
b. 분석:
1) 2 차원 공간의 점 을 1 차원 좌표계 로 낮 춘 다.
2) 이 점 들 을 각각 같은 이 진 트 리 의 다른 세로 좌표 와 가로 좌표 에 넣는다.
c. 코드:

//
// Created by    on 2018/2/6.
//        ，              
//

#include "cstdio"
#include "algorithm"
#include "vector"
using namespace std;

class Node{
public :
    int location;
    int p,l,r;
    Node(){}
};

class Point{
public:
    int id,x,y;
    Point(){}
    Point(int id,int x,int y):id(id),x(x),y(y){}
    bool operator < ( const Point &p) const {
        return id  & ans){
    int x = P[T[v].location].x;
    int y = P[T[v].location].y;

    if ( sx <= x && sy <= y && y <= ty ){
        ans.push_back(P[T[v].location]);
    }

    if ( depth % 2 == 0){
        if ( T[v].l != NIL){
            if ( sx <= x ) find(T[v].l ,sx,tx,sy,ty,depth+1,ans);
        }
        if ( T[v].r != NIL){
            if ( x <= tx ) find(T[v].r ,sx,tx,sy,ty,depth+1,ans);
        }
    }else{
        if ( T[v].l != NIL){
            if ( sy <= y ) find(T[v].l ,sx,tx,sy,ty,depth+1,ans);
        }
        if ( T[v].r != NIL){
            if ( y <= ty ) find(T[v].r ,sx,tx,sy,ty,depth+1,ans);
        }
    }
}

int main(){
    int x,y;
    scanf("%d",&N);
    for ( int i = 0 ; i < N ; i ++){
        scanf("%d %d",&x,&y);
        P[i] = Point(i,x,y);
        T[i].l = T[i].r = T[i].p = NIL;
    }

    np = 0 ;

    int root = makeKDTree(0,N,0);

    int q;
    scanf("%d",&q);
    int sx,tx,sy,ty;
    vector ans;
    for ( int i = 0 ; i < q ; i ++){
        scanf("%d %d %d %d",&sx,&tx,&sy,&ty);
        ans.clear();
        find(root,sx,tx,sy,ty,0,ans);
        sort(ans.begin(),ans.end());
        for ( int j = 0 ; j < ans.size() ; j ++){
            ans[j].print();
        }
        printf("
");
    }

    return 0;
}