2018-12-05

오늘 대학원 에 진학 한 학우 가 나 에 게 그녀 에 게 데이터 구조 문 제 를 보 여 달라 고 했 는데 제목 은 다음 과 같다.
23, 12, 45, 36 으로 구 성 된 이 진 트 리 는 몇 개 () 가 있 는데 그 중에서 AVL 트 리 는 몇 개 () 가 있 습 니까?A. 13, 4; B. 13, 5; C. 14, 5; D. 14, 4; 정 답: D
이 문 제 를 본 첫 번 째 반응 은 먼저 서열 을 다음 과 같이 정렬 한 다음 에 매 거 법 을 사용 하 는 것 이다.물론 답 도 이렇게 주 었 다.
매 거 할 때 12 와 45 로 시작 하 는 AVL 트 리 가 존재 할 수 없 는 경우 가 있 으 므 로 23 과 36 으로 시작 하 는 경우 같은 나 무 를 제외 하면 된다.매 거 해 보 니 각각 2 개의 AVL 트 리 가 있 었 기 때문에 두 번 째 빈 것 은 4 였 다.
하지만 곰 곰 이 생각해 보면 이 진 트 리 는 반전 이 가능 하 다.즉, 사실 12 시작 (최소 치) 의 나 무 는 나무의 좌우 나 무 를 교환 하면 그녀의 구 조 는 45 시작 (최대 치) 의 나무 와 똑같다!23 과 36 으로 시작 하 는 나무 도 마찬가지다.따라서 하나의 짝수 서열 에 대해 답 은 반드시 두 개의 빈 공간 이 짝수 일 것 이다!
따라서 2k 비트 (1000000 개 라 도) 의 짝수 서열 을 제시 하면 그 가 답 을 내 는 방식 이 변 하지 않 는 다 면 어떠한 계산, 그림 그리 기, 매 거 를 하지 않 아 도 된다!!!그냥 두 개 다 짝수 답!!!답 을 내 는 방식 이 바 뀌 더 라 도 반 은 덜 계산 할 수 있다!!!!!!!!
2k + 1 홀수 서열 을 제시 하면 가장 중간 에 있 는 트 리 의 방안 만 계산 하면 됩 니 다.
이 문제 에서 가장 어 려 운 것 은 이렇게 낼 수 있다.
2k + 1 개 수 를 드 리 겠 습 니 다. 구 성 된 이 진 트 리 는 가 있 습 니 다.개, 그 중 AVL 나무 에 또개?
자, 모두 함께 빈 칸 을 채 웁 시다!위의 생각 이 있 으 면 나 는 다시 재 귀적 으로 돌아 가 규칙 을 찾 으 면 이 문 제 를 풀 수 있 을 것 이 라 고 믿는다.고등학교 의 탄탄 한 수학 기초 와 이 진 트 리 의 본질 에 대한 이해 만 있다 면 이 문 제 는 반드시 맞 출 수 있 을 것 이다!