POJ-2201 카 르 테 시안 트 리[피리 칼 트 리]
1726 단어 데이터 구조
제목 의 대의:
피리 칼 나 무 를 만들어 보라 고 한다.
피리 칼 트 리 의 노드 는 2 개의 값,1 개의 key,1 개의 value 를 포함 하 는데 그 중에서 key 는 메 인 키 이 고 value 는 보조 키 이다.피리 칼 나 무 는 키 의 오름차,value 의 오름차 또는 내림차 이다.유사 더미.
treap 와 의 차이 점 은 treap 의 value 는 무 작위 값 으로 나 무 를 더욱 균형 있 게 도입 하기 위 한 것 이 고 피리 칼 트 리 의 value 는 확실한 값 입 니 다.
구조 가 완전히 같 고 기능 이 다르다.이 점 을 이해 하면 트 리 프 를 언제 쓰 고 피리 칼 나 무 를 언제 쓰 는 지 알 수 있다.
피리 칼 트 리 관련 링크:
http://www.hhanger.com/?p=134
http://zh.wikipedia.org/wiki/%E7%AC%9B%E5%8D%A1%E5%B0%94%E6%A0%91
http://en.wikipedia.org/wiki/Cartesian_tree
코드 는 다음 과 같 습 니 다:
#include
#include
#include
#include
#include
using namespace std;
const int N = 50010;
int stack[N];
int pre[N], lson[N], rson[N];
struct node{
int key, value, id;
}st[N];
bool operator = 0 && st[stack[k] + 1].value > st[i + 1].value) // i
--k;
if(k != -1)
{
pre[st[i + 1].id] = st[stack[k] + 1].id;
rson[st[stack[k] + 1].id] = st[i + 1].id;
}
if(k < top) //
{
pre[st[stack[k + 1] + 1].id] = st[i + 1].id;
lson[st[i + 1].id] = st[stack[k + 1] + 1].id;
}
stack[++k] = i;
top = k;
}
pre[st[stack[0] + 1].id]= 0; //
}
int main()
{
int num;
while(scanf("%d", &num) != EOF)
{
init(num);
for(int i = 1; i <= num; ++i)
{
scanf("%d%d", &st[i].key, &st[i].value);
st[i].id = i;
}
sort(st + 1, st + num + 1); // key
Build_Cartesian_Tree(num);
printf("YES
");
for(int i = 1; i <= num; ++i)
printf("%d %d %d
", pre[i], lson[i], rson[i]);
}
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
