[자료구조 및 알고리즘] [자료구조 및 알고리즘] Treaps

등록일 2002.12.24 MS 워드 (doc) | 23페이지 | 가격 1,100원

소개글

자료구조 및 알고리즘
서울대학교 전기공학부
심규석 교수님 강좌
2002년도 2학기

정답이 아닐 수 있으니 참고만 하시고
프로그래밍은 스스로 하시길 ^^

목차

- CLRS book의 296~298쪽에 있는 (a), (b), (c), (d), (f) 해결 -
a. Show that given a set of nodes x1, x2, …, xn, with associated keys and priorities (all distinct), there is a unique treap associated with these nodes.

b. Show that the expected height of a treap is THETA(lg n), and hence the time to search for a value in the treap is THETA(lg n).

c. Explain how TREAP-INSERT works. Explain the idea in English and give pseudocode. (Hint: Execute the usual binary-search-tree insertion procedure and then perform rotations to restore the min-heap property.)

d. Show that the expected running time of TREAP-INSERT is THETA(lg n).

f. Show that = 1 if and only if priority[y]>priority[x], key[y]<key[x], and, for every z such that key[y]<key[z]<key[x], we have priority[y]<priority[z].

- [NOTE 3] Pseudo code of insert algorithm for Treaps -

a. 알고리즘의 개요
b. Pseudo code
c. JAVA code

본문내용

수학적 귀납법으로 접근해 보자. 먼저 우리는 node가 0개인 treap과 1개인 treap은 unique하다는 사실을 직관적으로 안다. 이제 distinct한 key와 priotity를 가진 node k개의 treap이 unique하다는 가정하에서 node (k+1)개인 treap이 unique하다는 것을 보이면, 수학적 귀납법에 의한 증명이 끝난다.
각각 distinct한 key와 priority를 가진 (k+1)개의 node가 있고, 그 node들이 아직 treap을 형성하지는 않았다고 하자. min-heap property를 위해서는 가장 priority가 작은 node가 root에 들어가야 할 것이다. 그러면 binary search tree 특징에 의해 root의 left subtree에는 최소 0개에서 최대 k개의 node가, root의 right subtree에는 최소 0개에서 최대 k개의 node가 각각 존재한다. 물론 여기서 양쪽의 subtree에 속한 node의 개수를 합하면 k가 되어야 할 것이다. 다시 말해 root를 제외한 나머지 node들은, 그 key가 root의 key보다 작으면 root의 left subtree에, 그 key가 root의 key보다 크면 root의 right subtree에 속하게 된다는 것이다.
*원하는 자료를 검색 해 보세요.
  • 시스템프로그래밍 Lecture3,4 Using VI, Running a C program 12페이지
    $ ls –F : ls 명령어에 –F라는 option을 주어 directory file은 파일명 뒤에 /, 링크파일은 @, 실행파일은 *, FIFO 파일은 |, 일반파일은 아무것도 없도록 하여 표시하였다. $ cd 12091637 → cd 명령어를 이용하여 12091..
  • [재료열역학-KU] 열역학 개념 및 Gaskell(가스켈) 1~3장 문제풀이 18페이지
    [문제 1] 다음 열역학 용어 각각의 의미를 정리하라. (a) state (b) state variables (c) reversible process (a) state A thermodynamic state is a set of values of properties o..
  • [DSP기초설계]Unit 3. Discrete-time System 13페이지
    1(a) 수식적으로 푼 convolution 식을 matlab에서 conv_m() function을 이용하여 그래프 상으로 구현한 것이다.1(b) Matlab에 있는 filter() function을 이용하여 x(n)*x(n)을 계산한 것이다. Variable의 값을 ..
  • 시간복잡도 구하는 문제 및 코드 작성 foundation of algorithmn 10페이지
    알고리즘 설명1. n개의 숫자로 이루어진 크기n의 배열이 있으면 2개씩 짝지어서 순차적으로 대소 비교를한다.2.새로생성한 크기가 n인 배열에 앞부분은 비교연산결과 큰값들을 모아놓고 뒷부분에는 연산결과 작은값 들끼리 모아놓는다. (뒷부분이라 함은 중간부분이..
  • [전자기학] 전자기학 McGrawHill 연습문제풀이7장 9페이지
    7.9.The functions V 1 (┭,┵,z )and V 2 (┭,┵,z )both satisfy Laplace ’s equation in the region a <┭
  • 맨큐의 경제학 6판 < 14장 > 연습문제(복습,연습) 영어풀이(원페이지레포트) 1페이지
    Q. Draw the cost curves for a typical firm. For a given price, explain how the firm chooses the level of output that maximizes. At that level of outpu..
  • [네트워크]DataCommunication and Networking (forouzan) 4페이지
    1. Which type of user needs PPP?▸ 집에서 인터넷을 사용하는 수백만의 인터넷 사용자3. Name three protocols that make up the PPP stack.(1) LCP : 링크의 설정, 유지, 형성과 해제를 담당한다. 또한 ..
더보기

이 자료와 함께 구매한 자료

      최근 구매한 회원 학교정보 보기
      1. 최근 2주간 다운받은 회원수와 학교정보이며
         구매한 본인의 구매정보도 함께 표시됩니다.
      2. 매시 정각마다 업데이트 됩니다. (02:00 ~ 21:00)
      3. 구매자의 학교정보가 없는 경우 기타로 표시됩니다.
      최근 본 자료더보기
      추천도서