Hello people, I need an algorithm written in Java with an explanation so I under

Question

Hello people, I need an algorithm written in Java with an explanation so I understand it, Ive tried to look at the text books etc but couldnt find how to do it, Would really appreciate it if someone can help me out.

Thank you

Problem

If we insert a set of n items into a binary search tree using TREE-INSERT, the resulting tree may be horribly unbalanced. As we saw in class, however, we could expect randomly built binary search trees to be balanced. Therefore, if we want to build an expected balanced tree for a fixed set of items, we could randomly permute the items and then insert them in that order into the tree.

What if we do not have all the items at once? If we receive the items one at a time, can we still randomly build a balanced binary search tree out of them?

You will define and implement an algorithm that answers this question in the affirmative.

Each item x has a key key[x]. In addition, we assign priority[x], which is a random number chosen independently for each x. We assume that all priorities are distinct.




The nodes of the underpinning binary tree are ordered so that (1) the keys obey the binary-search-tree property and (2) the priorities obey the min-heap order property. In other words,

• If v is a left child of u, then key[v] < key[u];
• If v is a right child of u, then key[v] > key[u];
And
• If v is a child of u, then priority(v) > priority(u).

Your algorithm should be working and tested (i.e., checked for correctness) in both, definition and implementation, with the following example:

Input: We assume that you are given the initial set of items :
{A(10), B(7), E(23), G(4), H(5), K(65), I(73)}, with the randomly assigned priorities to the elements given in parentheses
• The tree after inserting a node with key C and priority 25.
• The tree after inserting a node with key D and priority 9.
• The tree after inserting a node with key F and priority 2.

Explanation / Answer

The described data structure is called a treap. This site describes and gives a Java implementation for treaps.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.