Documents

lec8.pdf

Description
Description:
Categories
Published
of 33
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Transcript
  Page 1 of 33 CSE 100, UCSD: LEC8 Lecture 8 ✔ Treaps ✔ Find, insert, delete, split, and join in treaps ✔ Randomized search trees ✔ Randomized search tree time costsReading: “Randomized Search Trees” paper (Aragon & Seidel):  http://people.ischool.berkeley.edu/~aragon/pubs/rst96.pdf  Weiss, Chapter 12 section 5  Page 2 of 33 CSE 100, UCSD: LEC8 Trees, heaps, and treaps ✔ A binary search tree (BST) is a binary tree:  ✗ Each Node in a BST contains a key; key values are comparable to each other  ✗ A BST has the BST ordering property: For every node X, the key in X is greater than all keys in the left subtree of X, and less than all keys in the right subtree of X ✔ A heap is a binary tree:  ✗ Each Node in a heap contains a priority; priority values are comparable to each other  ✗ A heap has the heap ordering property: For every node X, the priority in X is greater than or equal to all priorities in the left and right subtrees of X ✔ A treap is a binary tree:  ✗ Nodes in a treap contain both a key, and a priority  ✗ A treap has the BST ordering property with respect to its keys, and the heap ordering property with respect to its priorities  Page 3 of 33 CSE 100, UCSD: LEC8 Treaps: an example ✔ Suppose keys are letters, with alphabetic ordering; priorities are integers, with numeric ordering. This tree is a treap: G,50C,35B,24A,21E,33H,29I,25L,16J,13K,9D,8  Page 4 of 33 CSE 100, UCSD: LEC8 Uniqueness of treaps ✔ Given a set of (key,priority) pairs, with all the key values unique, you could always construct a treap containing those (key,priority) pairs:  ✗ Start with an empty treap  ✗ Insert the (key,priority) pairs in decreasing order of priority, using the usual binary search tree insert algorithm that pays attention to the key values only  ✗ The result is a treap: BST ordering of keys is enforced by the BST insert, heap ordering of priorities is enforced by inserting in priority sorted order ✔ If the priority values as well as the key values are unique, the treap containing the (key,priority) pairs is unique ✔ For example, the treap on the previous page is the unique treap containing these pairs:(G,50),(C,35),(E,33),(H,29),(I,25),(B,24),(A,21),(L,16),(J,13),(K,9),(D,8) ✔ Of course we will really be interested in algorithms that create a treap from (key,priority) pairs no matter what order they are inserted in.

Docie camaçari

Sep 14, 2019
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x