The keys of value N, N-1, N-2,.., 4, 3, 2, 1 are inserted in this order in a splay tree. What is ...
- The keys of value N, N-1, N-2,.., 4, 3, 2, 1 are inserted in this order in a splay tree. What is the final configuration of the tree? What is the cost in Big-Oh notation of each insert operation?
- Assume now that the next 100 operations will be a mix of only Find(1), Find(2) and Find(3), i.e., search in the tree for either the key of value 1, or the key of value 2, or the key of value 3. After each successful search, splaying is performed from the node where the key was found.
- What are the 3 tree configurations that are possible after these 100 operations are completed? What is the cost in Big-Oh notation of each Find operation?
- The next operation is Find(N). In terms of Big-Oh notation, is any of the 3 configurations above faster than the others? If so, what is its Big-Oh time complexity? If not what is the Big-Oh time complexity of Find(N) in the three configurations?
Homework Answers
1. In the splay tree last accessed element will be at the root. hence n will be at the bottom ,n-1 on top of that and finally 1 will be at the root.Each insert takes O(1). Configuration of the tree is as shown
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
2. Next 100 operations will be a mix of only Find(1), Find(2) and Find(3), i.e. search in the tree for either the key of value 1, or the key of value 2, or the key of value 3. After each successful search, splaying is performed from node where key was found.
3. when you execute find(1) splaying will be performed and tree is restructured as shown in the second picture given below. when find(2) is performed tree is again restructured .the output after find(2) and find(3) is shown at the right end.in the question it is said that we perform only Find(1), Find(2) and Find(3) and hence even if we perform 100 operations the structure of tree will be same.
4. Each of the three configurations have the same complexity . three configurations have the same Big-Oh complexity of O(N)
Add Answer to:
The keys of value N, N-1, N-2,.., 4, 3, 2, 1 are inserted in this order in a splay tree. What is ...
8. Given the BST below, show the BST that would result after inserting the key of value 180 if sp...
8. Given the BST below, show the BST that would result after inserting the key of value 180 if splaying is performed starting at the node that was inserted. 100 50 150 40 60 200 30 9. A nice property of splay trees is that each of Find, Insert and Delete takes O(logn) time. TrueFalse? 10. The keys of value N, N-1, N-2... 4, 3, 2, 1 are inserted in this order in a splay tree. What is the final...
(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...
1. What is the worst case time complexity of insertion into a binary search tree with...
1. What is the worst case time complexity of insertion into a binary search tree with n elements? You should use the most accurate asymptotic notation for your answer. 2. A binary search tree is given in the following. Draw the resulting binary search tree (to the right of the given tree) after deleting the node with key value 8. 10 3. You have a sorted array B with n elements, where n is very large. Array C is obtained...
(a) On an initially empty red-black tree, perform the following operations in this order: insert(1), insert(3),...
(a) On an initially empty red-black tree, perform the following operations in this order: insert(1), insert(3), insert(5), insert(6), insert(7), delete(1) Show all the intermediate steps of your work (b) We can get another sorting algorithm by first inserting all the keys into a red-black tree, and then performing an in-order traversal of the tree. What's the time complexity of this algorithm? (As always, use O or Θ notation.)
1. (10 pts) What is the order of each of the following tasks in the worst...
1. (10 pts) What is the order of each of the following tasks in the worst case (the worst case of the best algorithm for the task) (in Big-Oh notation)? • Searching a pointer-based link listed of n integers for a particular value. Answer: Searching a sorted array of n integers for a particular value. Answer: • Searching an unsorted array of n integers for a particular value. Answer: • Inserting a new value into a sorted array of n...
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.
1. Consider the following function for an AVL tree with n nodes. void _removeLeftmost(struct Node *cur) {...
1. Consider the following function for an AVL tree with n nodes. void _removeLeftmost(struct Node *cur) { while(cur->left != 0) { cur = cur->left } free(cur); } What is the average case big-O complexity of _removeLeftmost()? a. O(1) b. O(log n) c. O(n) d. None of the above 2. Refer to _removeLeftmost() from Question 1. What is the worst case big-O complexity of _removeLeftmost() for a binary search tree (not necessarily an AVL tree) with n nodes? a. O(1) b. O(log n) c. O(n) d. None of the above
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
//...
8. Given the BST below, show the BST that would result after inserting the key of value 180 if splaying is performed starting at the node that was inserted. 100 50 150 40 60 200 30 9. A nice property of splay trees is that each of Find, Insert and Delete takes O(logn) time. TrueFalse? 10. The keys of value N, N-1, N-2... 4, 3, 2, 1 are inserted in this order in a splay tree. What is the final...
(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...
1. What is the worst case time complexity of insertion into a binary search tree with n elements? You should use the most accurate asymptotic notation for your answer. 2. A binary search tree is given in the following. Draw the resulting binary search tree (to the right of the given tree) after deleting the node with key value 8. 10 3. You have a sorted array B with n elements, where n is very large. Array C is obtained...
(a) On an initially empty red-black tree, perform the following operations in this order: insert(1), insert(3), insert(5), insert(6), insert(7), delete(1) Show all the intermediate steps of your work (b) We can get another sorting algorithm by first inserting all the keys into a red-black tree, and then performing an in-order traversal of the tree. What's the time complexity of this algorithm? (As always, use O or Θ notation.)
1. (10 pts) What is the order of each of the following tasks in the worst case (the worst case of the best algorithm for the task) (in Big-Oh notation)? • Searching a pointer-based link listed of n integers for a particular value. Answer: Searching a sorted array of n integers for a particular value. Answer: • Searching an unsorted array of n integers for a particular value. Answer: • Inserting a new value into a sorted array of n...
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.
-
The pH of a sample of water from a river is 5.0. A
sample of effluent from...
asked 35 minutes ago -
At the beginning of the period, the Fabricating Department
budgeted direct labor of $136,500 and equipment...
asked 1 hour ago -
Please answer all
____ 28. Rent control is usually
justified on the grounds that it protects...
asked 1 hour ago -
PARTS A-D HAVE BEEN ANSWERED. WAS TOLD TO REPOST. ONLY ANSWER
PARTS E and F.
A...
asked 1 hour ago -
2) You are given the task of finding a representation for a
circle in a drawing...
asked 2 hours ago -
STUDY QUESTION: Does use of diet drug fen-phen
(fenfluramine-phentermine) cause valvular heart disease?
HINT: Valvular heart...
asked 2 hours ago -
1. An object weighing 40 N rests on a surface. The coefficient
of friction is 0.35....
asked 3 hours ago -
Investor company owns 35% of investee company voting stock and
accounts for the investment under the...
asked 4 hours ago -
The number of major faults on a randomly chosen 1 km stretch of
highway has a...
asked 5 hours ago -
Consider the competitive environment of Starbuck's, Progressive
Insurance, a manufacturing firm with low turnover, or a...
asked 5 hours ago -
3. Gains from trade
Consider two neighbouring island countries called Euphoria and
Contente. They each have...
asked 7 hours ago -
A business executive has the option to invest money in two
plans: Plan A guarantees that...
asked 10 hours ago