[SOLVED] implementation of a treap bst

Can you help me understand this Computer Science question?

Struggling to find relevant content or pressed for time? – Don’t worry, we have a team of professionals to help you on
[SOLVED] implementation of a treap bst
Get a 15% Discount on this Paper
Order Now

Objectives

The objectives of this programming assignment are:

  • Practice constructing and using binary search trees.
  • Practice writing basic rebalancing routines (single rotations).

Introduction

A treap is a combination of a binary search tree (BST) and a heap. You should be very familiar with BSTs at this point in the semester, but you probably haven’t encountered heaps yet. For this project, you only need two concepts from heaps:

  • Each node of the tree, in addition to holding a data value, will also store an integer priority value. Priority values should be unique; that is, no two nodes should have the same priority.
  • The tree must have the Max-Heap Property: for any node ww in the tree, the priority of ww must be greater than the priorities of its two children.

The following figure shows a treap in which the data are letters (or strings) and the priorities are integers.

Sample Treap with String Data and Integer Priorities
(Image source: http://cseweb.ucsd.edu/~kube/cls/100/Lectures/lec5/lec5-2.html#pgfId-955731)

A treap must be both a BST and have the max-heap property, which means insertions and deletions must check that the max-heap property holds and fix the tree if it does not. It will turn out that this is not as bad as it sounds. The max-heap property can always be repaired by applying single rotations.

Tree Rotations

Single tree rotations are local modification to a tree that can be used to repair violations of the max-heap property while maintaining the BST structure. The restructurings that can be achieved using single rotations are a subset of those possible with trinode restructuring. The figure below illustrates left and right single rotations.

Left and Right Single Rotations
(Image source: http://cseweb.ucsd.edu/~kube/cls/100/Lectures/lec5/lec5-5.html#pgfId-955859)

It is not difficult to see that rotations preserve the BST ordering: in both images, we have a<Y<b<X<ca<Y<b<X<c, and we assume that the subtrees aa, bb, and cc were constructed correctly before the rotation occured. How dow we use rotations to make local fixes to the max-heap property? Suppose that in the left picture, the priority of YY were higher than the priority of XX, violating the max-heap property; then a right rotation would make YY the parent of XX, correcting the error.

We can use single rotations, along with standard BST operations, to maintain a treap.

  • Insertion: suppose we have a value-priority pair (v,p)(v,p) that we wish to insert into a treap. Assume that pp is unique. We first perform a normal BST insertion, which creates a new leaf node. Then, if pp is greater than the priority of the parent, we do a left or right single roation to move (v,p)(v,p) up in the tree.
  • Deletion: suppose we wish to remove the node with value vv. We begin with a normal BST search to see if vv is in fact in the tree; if not, do nothing.

Now (v,p)(v,p) will have a new parent, and it is possible that pp is still larger than the new parent’s priority, in which case we perform another rotation; repeat, moving (v,p)(v,p) up the tree, until the max-heap property is satisfied at each node.

If we find vv and it is a leaf node, we can simply delete the node. If it is not a leaf node, perform a sequence of left and right rotations to move vv down the tree until it is a leaf, and then delete it. When performing the rotations, you should choose the direction (left or right) that moves the child with largest priority higher in the tree.

So why bother with treaps? One interesting fact is that if we build a treap using random priorities it will almost always be balanced (meaning, balanced with high probability); at the same time, treaps are easier to implement than balanced trees such as AVL or red-black trees. Also, there are other operations that can be performed efficiently on treaps, such as joining two treaps to create a single combined treap, or splitting a treap into two treaps.

A good reference for additional information is this lecture on treaps from UCSD.


Assignment

Your assignment is to implement the Treap class using single rotation method described in the Introduction to maintain the treap properties. You must use the provided treap.h and treap.cpp files. You may not modify the public function declarations or private data, but you may add private helper functions.

Although several test programs are provided, you are responsible for thoroughly testing your program. It is particularly important that your code run without segmentation faults, memory leaks, or memory errors. Memory leaks are considered as bad as segmentation fault since many segmentation faults are caused by poorly written destructors. A program with a poorly written destructor might avoid some segmentation faults but will leak memory horribly. Memory leaks will incur a penalty similar to that of a segmentation fault.

Following is a alist of member functions that must be implemented. Some of these functions are already implemented (or partially implemented) in treap.cpp; others will need to be written from scratch. Any helper functions that you write must be private and must be declared in treap.h.

  • A default constructor with the signature:
  • Treap::Treap() ;
  • A copy constructor with the signature:
  • Treap::Treap(const Treap& other) ;
  • A destructor with the signature:
  • Treap::~Treap() ;
  • An overloaded assignment operator with the signature:
  • const Treap& Treap::operator=(const Treap& rhs) ;
  • A function that deterimes if the treap is empty having the following signature:
  • bool Treap::empty() const;
  • A function that returns the height of the tree. It should have the following signature:
  • int Treap::height() const;
  • A function that returns the priority of the node. The priority function should should have the signature:
  • priority_t Treap::priority() const;
  • An insertion function that adds a data-priority pair to Treap and has the following signature:
  • void Treap::insert( data_t data, priority_t pri ) ;
  • A treap removal function that finds and removes an item with the given data value. The remove() function should return a boolean value that indicates whether the data value was found; it should not abort or throw an exception when the key is not stored in the BST. The remove() member function must have the following signature:
  • bool Treap::remove(data_t data) ;
  • A find function that reports whether the given data value is stored in the tree. The signature of the find() method must be:
  • const data_t* Treap::find(const data_t& x) ;
  • A member function inorder() that performs an inorder traversal and prints the data in a specified format. It must have the following signature:
  • void Treap::inorder() ;
  • A function locate() that returns whether there is a node in a particular position of the Treap and stores the data, priority, and height in reference parameters. The function must have the signature:
  • bool Treap::locate(const char position[], data_t& x, priority_t& p, int& h, int offset=0) ;
    • A call to locate(“LRL”, data) should return true and store D in data.
    • A call to locate(“RRRL”, data) should return true and store J in data.
    • A call to locate(“RLR”, data) should return false and not make any changes to data since there is no node in that position.
      Note: locate() must not abort and must not throw an exception in this situation.
    • A call to locate(“”, data) should return true and store G in data, since the empty string indicates the root of tree.
  • A dump function that prints information about all the nodes in the tree. The function must have the signature:
  • void Treap::dump() ;

Note: An implementation of this methods is provided in treap.cpp.

The default constructor must create a Treap object that is ready for treap operations such insertion, removal, search, and inorder traversal. Even an empty tree should behave properly when its methods are called.

The copy constructor must make a deep copy and create a new object that has its own allocated memory.

The destructor must completely free all memory allocated for the object. (Use valgrind on GL to check for memory leaks.)

The assignment operator must deallocate memory used by the host object and then make deep copy of rhs.

Note: An implementation of this methods is provided in treap.cpp.

The empty() function should return true if the tree is empty and false otherwise.

Note: An implementation of this methods is provided in treap.cpp.

The height() function should return the height of the tree. The height is stored in the TreapNode pointed to by the treap object and must be maintained by the node insertion and removal methods.

Note: An implementation of this methods is provided in treap.cpp.

The priority() function should return the priority stored in the TreapNode object.

The insert() function must maintain the treap properties (BST with max-heap property) and run in time proportional to the height of the treap. Your implementation must not allow duplicate data values. If the insert() function is invoked with a data value that already stored in the Treap, your insert() function should do nothing.

For full credit, your remove() method must run in time proportional to the height of the tree.

If the data value x is found, find() returns a pointer to the corresponding data value; otherwise it returns nullptr. Your find() method must run in time proportional to the height of the tree.

Note: An implementation of this methods is provided in treap.cpp.

The inorder() methods visits each node using an inorder traversal, prints out the data, followed by a :, followed by the priority, then another :, and then the height of the node. It also prints an open parenthesis before visiting the left subtree and a close parenthesis after visiting the right subtree. Nothing is printed when inorder() is called on an empty tree, not even parentheses. This function will be used for grading and is useful for debugging.

For example, calling inorder() on the sample treap from the introduction should produce the string:

((((A:21:0)B:24:1)C:35:2((D:8:0)E:33:1))G:50:5(H:29:4(I:25:3((J:13:1(K:9:0))L:16:2))))

Sample Treap with String Data and Integer Priorities
(Image source: http://cseweb.ucsd.edu/~kube/cls/100/Lectures/lec5/lec5-2.html#pgfId-955731)

Here, the G:50:5 indicates that the node with data “G” and priority 50 has height 5. The output before G:50:5 is produced by visiting the left subtree, and everything after G:50:5 is produced by visiting the right subtree.

Note: An implementation of this methods is provided in treap.cpp.

The position is given by a constant C-string, where a character L indicates left and a character R indicates right.

For example in the treap above:

The grading programs will use locate() to check if your treap is correct.

Note: An implementation of this methods is provided in treap.cpp.

Sample output from the dump() called on the sample treap is provided in dump_sample.txt.


Additional Requirements

Requirement: You must use the supplied treap.h and treap.cpp files. You may not modify any of the public method prototypes or private data, although you may add private functions.

Requirement: Your find(), insert() and remove() methods must all run in time proportional to the height of the treap.

Requirement: Your implementation must not permit duplicate data values. If an attempt is made to insert a duplicate value, insert() should leave the treap unchanged; it should not throw an exception or cause the program to crash.

Requirement: The treap properties must hold after any call to insert() or remove(). These commands must produce a valid treap.

Requirement: Your code must use single rotations as described in the Introduction to maintain the treap properties.

Requirement: Except for insert(), the provided function implementations should not be modified.


Provided Programs

The provided class files, treap.h and treap.cpp, comprise a partial implementation of a BST, providing a constructor, insert() function, and inorder() traversal, and it is possible to create and print a BST with no additional code. The following driver is provided:

  • driver.cpp — simple driver for the basic BST implementation.

Several sample test programs for the Treap class are provided below. However, it is your responsibility to write additional tests to ensure that your implementation is correct.

Calculate the price
Make an order in advance and get the best price
Pages (550 words)
$0.00
*Price with a welcome 15% discount applied.
Pro tip: If you want to save more money and pay the lowest price, you need to set a more extended deadline.
We know how difficult it is to be a student these days. That's why our prices are one of the most affordable on the market, and there are no hidden fees.

Instead, we offer bonuses, discounts, and free services to make your experience outstanding.
How it works
Receive a 100% original paper that will pass Turnitin from a top essay writing service
step 1
Upload your instructions
Fill out the order form and provide paper details. You can even attach screenshots or add additional instructions later. If something is not clear or missing, the writer will contact you for clarification.
Pro service tips
How to get the most out of your experience with MyCoursebay
One writer throughout the entire course
If you like the writer, you can hire them again. Just copy & paste their ID on the order form ("Preferred Writer's ID" field). This way, your vocabulary will be uniform, and the writer will be aware of your needs.
The same paper from different writers
You can order essay or any other work from two different writers to choose the best one or give another version to a friend. This can be done through the add-on "Same paper from another writer."
Copy of sources used by the writer
Our college essay writers work with ScienceDirect and other databases. They can send you articles or materials used in PDF or through screenshots. Just tick the "Copy of sources" field on the order form.
Testimonials
See why 20k+ students have chosen us as their sole writing assistance provider
Check out the latest reviews and opinions submitted by real customers worldwide and make an informed decision.
Nursing
excellent service! Not a beat missed!
Customer 452453, October 17th, 2021
Business and administrative studies
GREAT
Customer 452813, June 20th, 2022
English 101
The paper was late. However, it was excellent quality.
Customer 452561, July 2nd, 2021
Other
GOOD
Customer 452813, July 5th, 2022
Application Letters
Well written essay, will definitely use this service in the future.
Customer 452773, April 14th, 2022
Other
nice
Customer 452813, June 25th, 2022
Accounting
Thanks for your support
Customer 452701, February 3rd, 2022
Nursing
Amazing work! I passed the assignment!
Customer 452707, August 20th, 2022
Professions and Applied Sciences
Amazing work!
Customer 452707, May 29th, 2022
Nursing
Thank you to the writer and also thank you to the support team I got an A for the paper
Customer 452635, June 17th, 2022
Wellness
The skilled writer did a great job on assignment!! Thank you!!
Customer 452547, June 16th, 2021
Other
great
Customer 452813, July 5th, 2022
11,595
Customer reviews in total
96%
Current satisfaction rate
3 pages
Average paper length
37%
Customers referred by a friend
OUR GIFT TO YOU
15% OFF your first order
Use a coupon FIRST15 and enjoy expert help with any task at the most affordable price.
Claim my 15% OFF Order in Chat

Order your essay today and save 15% with the discount code DC15

NEW

Thank you for choosing MyCoursebay. Your presence is a motivation to us. All papers are written from scratch. Plagiarism is not tolerated. Order now for a 15% discount

Order Now