Suppose you started with an empty binary search tree. We've seen previously that inserting the keys...
Suppose you started with an empty binary search tree. We've seen previously that inserting the keys 1, 2, 3, 4, 5, 6, 7 (in that order) would lead to a binary search tree whose shape we called degenerate.
- Propose a second ordering of the same keys that would also lead to a degenerate-shaped binary search tree.
- If possible, propose a third ordering of the same keys that would also lead to a degenerate-shaped binary search tree. If there are no more orderings other than the one we provided and the second one you proposed, briefly explain why there are no more.
Homework Answers
Trees where every internal node have 1 child, are degenerate trees.
Some of the orderings that would lead to a degenerate shaped Binary Search Tree:
1. : 1, 2, 3, 4, 5, 6, 7
2. : 7, 6, 5, 4, 3, 2, 1
3. : 7, 6, 5, 4, 3, 1, 2
4. : 7, 1, 6, 2, 5, 3, 4
Many more are possible!
Tree structures of above examples:
Please ask for clarifications if any and kindly give feedback!
Add Answer to:
Suppose you started with an empty binary search tree. We've seen
previously that inserting the keys...
PROBLEM 6: Suppose we insert keys below into an initially empty binary search tree in the...
PROBLEM 6: Suppose we insert keys below into an initially empty binary search tree in the given order 6, 9, 2, 1, 5, 7, 10, 8, 3,4 (a) Draw the resulting binary search tree. (b) List the keys according to: A pre-order traversal An in-order traversal A post-order traversal (c) Now we perform some deletions using the "deletion by copying" strategy in which promoted keys are always drawn from a node's right subtree (so that there is only one correct...
PROBLEM 6: Suppose we insert keys below into an initially empty Vanilla binary search tree in...
PROBLEM 6: Suppose we insert keys below into an initially empty Vanilla binary search tree in the given order: 6, 9, 2, 1, 5, 7, 10, 8, 3, 4 (a) Draw the resulting binary search tree. (b) List the keys according to: A pre-order traversal An in-order traversal A post-order traversal (c) Now we perform some deletions using the “deletion by copying” strategy in which promoted keys are always drawn from a node’s right subtree (so that there is only...
Starting with an empty binary search tree, insert each of the following keys and rotate it...
Starting with an empty binary search tree, insert each of the following keys and rotate it to the root in the specified order: 6 1 18 7 15 Starting with an empty red-black binary search tree, insert the following keys in order:: 12 5 23 9 19 2 21 18 7 Show the tree immediately after you insert each key, and after each time you deal with one of the book's cases 1, 2, or 3 (that is, if dealing with one case leads to another, show the additional case as a...
Write a program that builds t BSTs by inserting N random keys into an initially empty tree, and then finds the tree height for N =100, 500 and 1000; and t =5, 10, 15. Find the average height of binary...
Write a program that builds t BSTs by inserting N random keys into an initially empty tree, and then finds the tree height for N =100, 500 and 1000; and t =5, 10, 15. Find the average height of binary search trees for each pair of values of t and N. Decide what you will do with duplicates and explain what you did to handle duplicates.
(20 points) Suppose you are given a binary search tree T of n nodes (as discussed...
(20 points) Suppose you are given a binary search tree T of n nodes (as discussed in class. each node v has v.left, v.right, and v.key). We assume that no two keys in T are equal. Given a value x, the rank operation rank() is to return the rank of x in T, which is defined to be one plus the number of keys of T smaller than 2. For example, if T has 3 keys smaller than r, then...
Read a list of names from a file. Insert the names into a binary search tree...
Read a list of names from a file. Insert the names into a binary search tree that is a little different from what we discussed in class. For this tree, the left side will contain the larger values and the right side will contain the smaller values. In essence, it is the exact opposite of a normal binary search tree. Our tree will also be able to store duplicate names. Aside from a left and a right pointer for each...
I need help in C++ implementing binary search tree. I have the .h file for the...
I need help in C++ implementing binary search tree. I have the .h file for the binary search tree class. I have 4 classic texts, and 2 different dictionaries. Classic Texts: Alice In Wonderland.txt A Tale of Two Cities.txt Pride And Prejudice.txt War and Peace.txt 2 different dictionaries: Dictionary.txt Dictionary-brit.txt The data structures from the standard template library can not be used.The main program should open the text file, read in the words, remove the punctuation and change all the...
C++ Binary Search Tree question. I heed help with the level 2 question please, as level...
C++ Binary Search Tree question. I heed help with the level 2
question please, as level 1 is already completed. I will rate the
answer a 100% thumbs up. I really appreciate the help!. Thank
you!
searching.cpp
#include <getopt.h>
#include <iostream>
#include <sstream>
#include <stdlib.h>
#include <unistd.h>
using namespace std;
// global variable for tree operations
// use to control tree maintenance operations
enum Mode { simple, randomised, avl } mode; // tree type
// returns size of tree
//...
C++ Binary Search Tree question. I heed help with the level 2 question please, as level...
C++ Binary Search Tree question. I heed help with the level 2
question please, as level 1 is already completed. I will rate the
answer a 100% thumbs up. I really appreciate the help!. Thank
you!
searching.cpp
#include <getopt.h>
#include <iostream>
#include <sstream>
#include <stdlib.h>
#include <unistd.h>
using namespace std;
// global variable for tree operations
// use to control tree maintenance operations
enum Mode { simple, randomised, avl } mode; // tree type
// returns size of tree
//...
*****************************In Java***************************************In Java***********************************In Java************************* In this problem, you will implement various algorithms operating on binary search...
*****************************In Java***************************************In Java***********************************In Java************************* In this problem, you will implement various algorithms operating on binary search trees. We have provided with you a standard implementation of a generic BST in BinarySearchTree.java. Note that this class is an abstract class, which means that some of its methods are not implemented. In previous assignments, you have implemented interfaces which specified methods that you needed to write. Very similarly, an abstract class is a class with some unimplemented methods (it can be thought...
PROBLEM 6: Suppose we insert keys below into an initially empty binary search tree in the given order 6, 9, 2, 1, 5, 7, 10, 8, 3,4 (a) Draw the resulting binary search tree. (b) List the keys according to: A pre-order traversal An in-order traversal A post-order traversal (c) Now we perform some deletions using the "deletion by copying" strategy in which promoted keys are always drawn from a node's right subtree (so that there is only one correct...
(20 points) Suppose you are given a binary search tree T of n nodes (as discussed in class. each node v has v.left, v.right, and v.key). We assume that no two keys in T are equal. Given a value x, the rank operation rank() is to return the rank of x in T, which is defined to be one plus the number of keys of T smaller than 2. For example, if T has 3 keys smaller than r, then...
Read a list of names from a file. Insert the names into a binary search tree that is a little different from what we discussed in class. For this tree, the left side will contain the larger values and the right side will contain the smaller values. In essence, it is the exact opposite of a normal binary search tree. Our tree will also be able to store duplicate names. Aside from a left and a right pointer for each...
C++ Binary Search Tree question. I heed help with the level 2
question please, as level 1 is already completed. I will rate the
answer a 100% thumbs up. I really appreciate the help!. Thank
you!
searching.cpp
#include <getopt.h>
#include <iostream>
#include <sstream>
#include <stdlib.h>
#include <unistd.h>
using namespace std;
// global variable for tree operations
// use to control tree maintenance operations
enum Mode { simple, randomised, avl } mode; // tree type
// returns size of tree
//...
C++ Binary Search Tree question. I heed help with the level 2
question please, as level 1 is already completed. I will rate the
answer a 100% thumbs up. I really appreciate the help!. Thank
you!
searching.cpp
#include <getopt.h>
#include <iostream>
#include <sstream>
#include <stdlib.h>
#include <unistd.h>
using namespace std;
// global variable for tree operations
// use to control tree maintenance operations
enum Mode { simple, randomised, avl } mode; // tree type
// returns size of tree
//...
Most questions answered within 3 hours.
-
what would be the best entry mode in shipping from the U.S to Spain
by boat...
asked 16 seconds from now -
Under certain conditions, the substance ammonium
nitrate can be broken down to form dinitrogen
monoxide and...
asked 51 seconds ago -
1. A boy stands on one end of a boat, and then walks to the
other...
asked 11 minutes ago -
Casey is on trial under criminal allegations that she engaged in
fraudulent behavior at the company...
asked 16 minutes ago -
Surplus Styles is a manufacturer of hair care products,
including shampoos, conditioners, and hair gels. The...
asked 14 minutes ago -
Using an income-expenditure diagram, use the infinite line and
double-drop line tools to show the economy...
asked 22 minutes ago -
Which expression computes a pseudorandom integer between -10 and
10 using rand()
from cstdlib?
A. (rand(...
asked 29 minutes ago -
Roybus, Inc., a manufacturer of flash memory, just reported that
its main production facility in Taiwan...
asked 37 minutes ago -
Two capacitors connected in parallel produce an equivalent
capacitance of 45.0 μF but when connected in...
asked 46 minutes ago -
The differences between the two sets of dependent data are -1,
2,-,2, 2. Round to the...
asked 1 hour ago -
A χ2-curve, looking at the relationship between age and hours
spent working at an office per...
asked 1 hour ago -
The pH of a sample of water from a river is 5.0. A
sample of effluent from...
asked 2 hours ago