DSC 395T Algorithms and Data Structures
report | 代写Data structure | 代写Algorithm | assignment作业 – 这是一个关于report的题目, 主要考察了关于report的内容,是一个比较经典的题目, 是比较有代表性的report/Data structure/Algorithm等代写方向, 这个项目是assignment代写的代写题目
DSC 395T Algorithms and Data Structures Spring 2022 March 11
Treaps Programming assignment #
In this assignment you will implement a map (associative lookup) using a Data structure called a treap, which is a combination of a tree and a heap. Your key challenge in this assignment will be to carefully and thoroughly test your data structure, so you should also design a testing program for your code. For this assignment, you should not discuss testing strategies with other teams.
1 Treaps
Atreapis a binary search tree that uses randomization to produce balanced trees. In addition to holding a key-value pair (a map entry), each node of a treap holds a randomly chosen priority value, such that the priority values satisfy the heap property: Each node other than the root has a priority that is at least as large as the priorities of its two children. An example treap is shown in Figure 1, where the keys are shown at the top of each node and the priorities are shown at the bottom of each node. Notice that the keys obey the binary search tree (BST) property and the priorities obey the heap property. Because the keys obey the BST property, a lookup operation can be performed just as with any BST. However, the insert and remove operations are slightly more complex.
4
4743
8
7336
6
9403
4407
5
1059
9
1936
2486
3
1
Figure 1: A treap for a map with key set{1, 3, 4, 5, 6, 8, 9}. For each node, the key is shown in the top half, while the priority is shown in the bottom half. The priority values are chosen at random, with larger numbers representing higher priorities. The values are not shown.
To insert a new nodexwith keyk, we first perform the insertion at the appropriate leaf position according to the BST property, exactly as in a binary search tree (See Figure 2). The node is assigned a randomly chosen priorityp, and becausexs parentymay have priority less thanp, the heap property may be violated. To restore the heap property, we perform a rotation, makingxthe parent ofy, as shown in Figure 2(b). Specifically, ifxis the left child ofy, then we rotate right aroundy, and ifxis the right child ofy, then we rotate left aroundy. Nodexnow has a new parent, and the heap property may still be violated, requiring another rotation. In general, the heap property is restored by rotating the new nodexup the treap as long as it has a parent with a lower priority. Figure 2 shows an insertion requiring 2 rotations. To remove a nodex, we reverse the insertion. We rotatexdown the treap until it becomes a leaf, and then we simply clip it off. At each step, the decision to rotate left or right is governed by the relative priorities of the children. The child with the higher priority should become the new parent. Thus, ifxs left child has higher priority thanxs right child, then we rotate right aroundx. Conversely, ifxs right child has higher priority thanxs left child, then we rotate left aroundx. Figure 3 illustrates a removal requiring 2 rotations. This removal reverses the insertion of Figure 2. All three map operationslookup, insert, and removerun in timeO(h), wherehis the height of the treap. It is not hard to show that a treap withnnodes has expected height(logn). Note that the root of a treap is determined by
8
7336
1059
5
6
9403
2486 1059
9
1936
1
6
9403
2486 4743
9
1936
1
6
9403
4407
5
1059
9
1936
2486
3
1
8
7336
3
4407
3
4407
8
7336
4
4743
5
y
x
4
y
x
z x
z
(a) (b) (c)
4743
4
Figure 2: Inserting new nodexinto a treap. (a) The new nodex, with keyk=4and priorityp=4743, is added as a leaf according to the BST property. The heap property with respect toxs parentyis violated. (b) The situation after a right rotation aroundy; the heap property with respect toxs new parentzis violated. (c) After a left rotation aroundz, the heap property is restored.
the randomly chosen priorities. The node with the highest priority is the root. Thus, the root node is equally likely to contain any of the map entries, regardless of the order in which the entries are inserted or removed. Consequently, we expect that half of the entries will be in the left subtreap and the other half in the right subtreap. The analysis of treap height is therefore similar to the analysis of recursion depth in quicksort.
2 Your Assignment
Implement a map using a treap. In particular, you should implement the following abstract base class. Your treap should store entries with keys that areComparableobjects and values that are any object. In both cases the Treap is generic on the exact type; keys have typeKTand values have typeVT. Thelookup(k)method should return None if no entry with keykis in the map.
class Treap(ABC, Generic[KT, VT], Iterable): def get_root_node(self) -> TreapNode: … def lookup(self, key: KT) -> Optional[VT]: … def insert(self, key: KT, value: VT) -> None: … def remove(self, key: KT) -> Optional[VT]: … def split(self, threshold: KT) -> "List[Treap[KT, VT]]": … def join(self, other: "Treap[KT, VT]") -> None: … def meld(self, other: "Treap[KT, VT]") -> None: … def difference(self, other: "Treap[KT, VT]") -> None: … def balance_factor(self) -> float: … def str(self) -> str: … def iter(self) -> Iterator: …
A more detailed description of the interface is intreap.py. Implement your treap-based map asTreapMap intreapmap.pyand make sure your implementation inherits fromTreap[KT, VT]. Please use the TreapNode defined intreapnode.pyand do not modify or rename the six existing fields in TreapNode. You only need to modifytreapmap.pyfor this assignment, but you are welcome to modifytreapnode.pyas well.
The insert method. Insertion into the treap should be implemented as outlined in Figure 2. You can assume that two nodes will never have an equal priority, which is enforced by the starter code.
8
7336
1059
5
(a) (b) (c)
6
9403
4407
5
1059
9
1936
2486
3
1
4
4743
x
z
6
9403
2486 4743
9
1936
1
3
4407
8
7336
4
y
x
z
6
9403
2486 1059
9
1936
1
8
7336
3
4407
5
y
x^4
4743
Figure 3: Removing a nodexfrom a treap. (a) Nodexhas two children, of which the left childzhas higher priority. (b) After a right rotation aroundx, nodexnow has only one child,y. (c) After a left rotation aroundx, nodexis now a leaf and can be clipped off like an excessively long toenail.
The remove method. Removal from the treap should be implemented as outlined in Figure 3.
The split method. A treapTcan besplit, using a keyk, to produce two treaps,T 1 andT 2 , such thatT 1 contains all of the entries inTwith key less thank, andT 2 contains all of the entries inTwith key greater than or equal tok. To perform the split, we insert intoTa new entryxwith keykand priorityp=MAXPRIORITY, forming a new treap T. (MAXPRIORITYis defined by theTreapabstract base class.) Becausexhas the highest possible priority,xis the root ofT, so the split has been accomplished withT 1 being the left subtreap andT 2 being the right subtreap. You should not lose any value associated withkifkis already in the treap, although it is ok if you destroy the old treap.
The join method. The inverse of a split isjoin, in which two treaps,T 1 andT 2 , with all keys inT 1 being smaller than all keys inT 2 , are merged to form a new treapT. To perform the join, we create a new treapTwith an arbitrary new root nodexand withT 1 andT 2 as the left and right subtreaps. We then removexfromTto form the joined resultT. Split and join both take timeO(h), wherehis the height of theT(the input to split or the result of join). The expected height is(logn), wherenis the size ofT, so split and join both run inO(logn)expected time. More interestingly, split and join can be used as subroutines tomeldtwo treaps or take thedifferencebetween two treaps. Those functions are described in the Karma section.
3 Testing
Since the treap in this assignment is not part of a larger application, you will not be able to use or test your treap without writing your own test program. Write a test suite to test your treap for correctness. You may use pytest or just write a program that manually runs the appropriate tests. We have provided a few starter test cases inside of the test/testtreaps.pyfile, which you can run with the commandpoetry run pytest -v. Please do not submit this test file.
4 Karma
Three of the operations in the interface (balancefactor(),meld()anddifference()) are optional. Im- plement them for extra karma. If you do not implement them, raise anAttributeError.
4.1 Meld
Ameldtakes two treaps,T 1 andT 2 and merges them into a new treapT, much like the Vulcan mind meld for which it is named^1. Unlike a join, a meld does not require any relationship between the keys inT 1 andT 2. Meld is a naturally recursive procedure and should be able to meld two treaps of sizenandm(mn) inO(mlog(n/m))time. Describe how you meld treaps and how your Algorithm meets the specified asymptotic time bound.
4.2 Difference
Thedifferencebetween two treaps,T 1 andT 2 , is a treapTcontaining the keys ofT 1 with any keys inT 2 removed. The difference can also be computed recursively and also runs inO(mlog(n/m))time. Describe how you take a difference and how your algorithm satisfies this time bound.
4.3 Diagnosing Problems Through Testing
Typically, the goal of a test program is to identify bugs. With some additional work, you can attempt to diagnose common problems by observing the behavior of the program. For example, if the iterator misses one key, it is likely that the missing key is the first or last key added. A test program can attempt to verify this hypothesis and provide a suggestion to the user. Can you use your test program to assist in finding common mistakes?
4.4 Balance Statistics
It would be useful to know how balanced or imbalanced your treap is. The balance factor is the ratio between the height of the treap and the minimum possible height. A perfectly balanced treap will have a balance factor of 1.0. Include observations on how well the treap seems to keep itself balanced in your report.
5 What to Turn in
Submit a single ZIP file containing your report and code. Make sure your code is packaged in a directory named pytreaps.
Acknowledgments. We thank Bobby Blumofe for the original version of this assignment, and we thank Walter Chang, Arthur Peters, and Ashlie Martinez for their subsequent modifications.
(^1) Not really.