Implement a generic bst library

Assignment Help C/C++ Programming
Reference no: EM132521074

Assignment: A Binary Search Tree Variant

Write functions in C to perform i) insertions and ii) deletions in a slightly different way in a BST as explained below. For printing, follow the convention in the previous assignment. As before, the keys will be positive integers. The struct will be necessarily have a) the key value b) pointer to the left child, c) pointer to the right child and d) pointer to parent. Additionally, you will maintain the size of the tree rooted at any given node. More later in the examples.

Part 1. There are two ways of insertion into the tree: a) recursively insert into the tree in the usual way that you did in the previous assignment and b) insert at root. When there is an insertion to be done in a tree of size n, perform step a) with probability n-1 and b) with probability 1 . Note that since this is a recursive step, you have to make this choice at every level.

Insert at root works as follows as shown in the picture below:

901_figure.jpg

1037_figure1.jpg

Figure 1: 26 is being inserted into the BST (top left); the original BST is split into two BSTs (top right); 26 is made the root, and stitched again (bottom).

Part 2. Delete is similar to the usual delete operation in a BST, but for a minor twist. Searching for the node to be deleted works as in the usual case. When you find the node to be deleted, do the following (showing only the relevant part and skipping the part where you search):

// relevant part of the function
//BST delete(int x, BST T)

temp = join(T->left, T->right); free(T);
T = temp;
Finally, the delete subroutine returns T , a pointer to the tree. The join function behaves is detailed below:

1485_figure2.jpg

A pictorial representation of what happens during deletion is as follows:

2291_figure3.jpg

Figure 2: Deleting 15

Some remarks:
(a) Test cases will be similar to the previous assignment.

(b) You would have noticed through your learning about the BST that the tree can get skewed to one side over several insertions. E.g. if you insert 1,2,3,4 and 5 in that order, you will get a tree skewed to the right, results in a Θ(n) search time. This would be as if you are searching in a linked list, and you don't get any advantage that a BST is supposed to offer. Folks in the past have designed workarounds that mitigate this problem. In the coming courses, you will study about many approaches towards restoring some sense of balance to avoid such a skew. For those who wish to have a sneak peek, read up on AVL trees, Red Black trees and Splay Trees to get an idea.

(c) What you will do in this assignment is unlikely to be discussed in a usual course, but this is another way of achieving this balance. Convince yourself of this.

(d) (thanks to Supreet for this!), do the following:

i. Implement a generic BST library that takes an arbitrary data type (int, strings, even other structs) as key, depending on the need of the user. You could use a void* pointer for the datatype of key in the tree node. Also you'll need to modify the library functions to take in an additional argument - a function pointer. This pointer points to a comparison function, that compares two objects of your custom data type. We need to do this since a BST relies on comparison for its operations. The user of your library will have to write these comparison functions for the data type that she is using.

ii. Export the above written code as a shared library (.so/.dll file). You'll also need to export a header (.h) file that declares the publicly available functions. Hide other helper functions that you might have used using the static keyword in front of the function declaration. Ensure no memory leaks! Also read up about static vs dynamically linked libraries.

Reference no: EM132521074

Questions Cloud

Discuss one literary or poetic term that found demonstrated : In your view, do body size issues rob the broader human community of valuable insights and perspectives? How might we combat the problem?
Disaster Recovery And Business Continuity Plan : Determine the recovery model for your backup and recovery strategy. Design the backup strategy, and include a diagram to document your backup strategy.
Calculate the weighted-average number of common shares : Omar Products Inc. reported a profit in 2020 and declared a preferred share dividend. Calculate the weighted-average number of common shares
What is the change in kinetic energy for the core : After a massive star undergoes a core collapse supernova event sometimes a neutron star is left over. Let us say that the core of a star has a mass
Implement a generic bst library : Implement a generic BST library that takes an arbitrary data type (int, strings, even other structs) as key, depending on the need of the user
Describe purchase discounts : Describe the 2 shipping terms methods companies use when delivering products, and how freight costs are accounted for. Describe purchase discounts
Record issuance of the bonds on January : Record (a) issuance of the bonds on January 31, (b) the semiannual interest payment and amortization of bond discount on July 31
Calculate the total volume of air : A power plant operates at 25% efficiency. The exhaust heat is let out into the air which raises the local air temperature by 8o. The power output of the plant
What motivates most employees at washburn guitars : Recall a past or present manager. Which of the five Leadership Grid styles does or did your manager use most often. Describe the behavior. Successful?

Reviews

Write a Review

C/C++ Programming Questions & Answers

  Create program that uses functions and reference parameters

Create program that uses functions and reference parameters, and asks user for the outside temperature.

  Write a program using vectors and iterators

Write a program using vectors and iterators that allows a user to maintain a personal list of DVD titles

  Write the code required to analyse and display the data

Calculate and store the average for each row and column. Determine and store the values for the Average Map.

  Write a webservices application

Write a webservices application that does a simple four function calculator

  Iimplement a client-server of the game

Iimplement a client-server version of the rock-paper-scissors-lizard-Spock game.

  Model-view-controller

Explain Model-View-Controller paradigm

  Design a nested program

How many levels of nesting are there in this design?

  Convert celsius temperatures to fahrenheit temperatures

Write a C++ program that converts Celsius Temperatures to Fahrenheit Temperatures.

  Evaluate and output the value in the given base

Write C program that will input two values from the user that are a Value and a Base with which you will evaluate and output the Value in the given Base.

  Design a base class shape with virtual functions

Design a base class shape with virtual functions

  Implementation of classes

Implementation of classes Chart and BarChart. Class barChart chould display a simple textual representation of the data

  Technical paper: memory management

Technical Paper: Memory Management, The intent of this paper is to provide you with an in depth knowledge of how memory is used in executing, your programs and its critical support for applications.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd