LCT (Link Cut Tree) 학습 후기

1925 단어 데이터 구조동적 트 리LCT
동적 트 리 (Dynamic Tree) 이전에 나 는 이것 이 데이터 구조 라 고 생각 했 는데 최근 에 야 이것 이 문 제 를 가리 키 는 것 이라는 것 을 알 게 되 었 다.
엘 시 티 를 공부 하기 전에 먼저 트 리 체인 분할 을 배 워 야 한다.나무 사슬 의 분할 은 한 그루 의 나 무 를 여러 개의 체인 으로 나 누고 데이터 구조 로 모든 체인 을 유지 하 는 것 이다. 복잡 도 는 O (logN) 이다.
트 리 체인 분할 은 나무의 모양 이 변 하지 않 는 나 무 를 대상 으로 하지만 나무의 모양 이 변 할 수 있다 면 (나 무 를 분리, 통합 하 는 작업 을 지원 하려 면) LCT (Link Cut Tree) 를 사용 해 야 한다.
LCT 의 대략적인 사고방식 은 splay 로 모든 체인 을 유지 하고 다음 과 같은 조작 을 지원 하 는 것 이다. 1. Access (x): x 에서 루트 노드 까지 의 경 로 를 하나의 트 리 체인 (p. s. Access 는 모든 조작의 기초) 으로 바 꾸 는 것 이다. 2. MakeRoot (x): x 를 x 가 있 는 트 리 의 루트 노드 로 바 꾸 는 것 이다. 3. Link (x, y): x 와 y 사 이 를 4, Cut (x, y): x 와 y 사 이 를 삭제 하 는 것 이다.
코드 는 다음 과 같 습 니 다. 1. Access (x): x 에서 루트 노드 까지 의 경 로 를 트 리 체인 으로 바 꿉 니 다 (p. s. Access 는 모든 작업 의 기초 입 니 다)
void access(int x){
    for(int t=0;x;t=x,x=fa[x])
    splay(x),s[x][1]=t,update(x);
}

2. MakeRoot (x): x 를 x 가 있 는 나무의 뿌리 노드 로 바 꿉 니 다.
void makeroot(int x){
    access(x),splay(x),rev[x]^=1;
}

3. Link (x, y): x 와 y 사이 에 한 변 을 연결 합 니 다.
void link(int x,int y){
    makeroot(x);
    fa[x]=y;
}

4. Cut (x, y): x 와 y 사이 의 변 을 삭제 합 니 다.
void cut(int x,int y){
    makeroot(x);
    access(y);
    splay(y);
    s[y][0]=fa[x]=0;
    update(y);
}

코드 가 비교적 간단 해서 독자 스스로 이해한다.
Java 학습-다중 스레드 고전 사례의 거북이 토끼 달리기
S/MIME로 암호화

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage