Question

In this assignment you have to design and implement a “Bribe Organized Search Tree” (BOST). BOST is a new data structure invented for this assignment and it might not be of any use in real programs.

A BOST is an ordinary binary search tree where all the nodes contain an extra attribute – the bribe. When a node is created the bribe is set to zero. The tree should contain a method to update the bribe. After changing a bribe the tree might need reorganization.

When a BOST is well organized, all the descendants of a node have either the same or a lower bribe than the node itself. On the other hand, it is still a search tree, where all nodes in the left subtree of node have elements smaller than the element of the node, and corresponding greater than for the right subtree.

In other words: the root will be the node with the highest bribe. To the left are the smaller elements and the larger element are to the right. This rule is applied recursively down both subtrees.

Notice that a BOST is not balanced in the classical sense. A BOST doesn’t guarantee an average search time of O(log n).
Implement a BOST and make a proper test of your implementation.

Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

/**
*
* @param <E>
*/
public class BOST<E extends Comparable<E> > {
   
    private Node<E> root;

    /**
    * constructor
    */
    public BOST() {
       root = null;
    }
   
    /**
    * remove a data
    * @param data
    */
    public void remove(E data){
       // fin in the tree
       Node<E> node = find(data);
      
       // it is found
       if (node != null) {
            // set it bribe to the smallest value
            node.setBribe(Integer.MIN_VALUE);
            // move it down
            node = moveDown(node);
            if (node == root) { // basic case
                root = null;
            } else {
                // remove a leaf from the tree
                Node<E> parent = node.getParent();
                if (parent.getLeft() == node) {...

This is only a preview of the solution. Please use the purchase button to see the entire solution

Assisting Tutor

Related Homework Solutions

Land Tract Problems in Java
Homework Solution
$5.00
Computer Science
Java Programming
Land Tract
Methods
Strings
Area
Equality
Size
Dimensions
Statements
Variables
Financial Application in Java
Homework Solution
$15.00
Computer Science
Java Programming
Financial Applications
Payroll
Hourly Rates
Withholding Rate
Tax
Deductions
Net Pay
Java Programming
Homework Solution
$98.00
Computer Science
Java Programming
Graphs
Algorithms
Minimum Spanning Trees
Classes
Queue
Edges
Distances
Statements
Variables
Java Programming Problems
Homework Solution
$50.00
Computer Science
Java Programming
Rooms
Classes
Constructors
Input Arguments
Attributes
High School Locker
Students
Combinations
Numbers
Variables
Cycles
Lists
Books
Arrays
Characters
Letters
Symbols
Java Programming Picture Problem
Homework Solution
$40.00
Computer Science
Java Programming
Pictures
Squares
Pixels
Grid
Input
Output
Colors
Statements
Variables
Hanoi Tower ASCII Beauty
Homework Solution
$50.00
Computer Science
Java Programming
Hanoi Tower
ASCII Beauty
Recursive Problems
Command Line Arguments
Numbers
Statements
Variables
Get help from a qualified tutor
Live Chats