1- Insert in the given order the following values into an intially empty 2-3-4 tree: 100,...
1- Insert in the given order the following values into an intially empty 2-3-4 tree: 100, 200, 300, 400, 500, 600, 700, 110, 120, 130, 800, 750, 690. Show how the tree evolves after each value is inserted. In other words, draw a picture of the tree after each insertion.
2- Insert the same sequence as above into an initially empty red-black tree. Again draw a picture of the tree after each insertion, and indicate which rotations and/or color flips were performed.
Submit a SINGLE document (Word, PDF, or high quality scan) containing your solution,
Homework Answers
2-3-4
RED BLACK
Add Answer to:
1- Insert in the given order the following values into an
intially empty 2-3-4 tree: 100,...
(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.)
11. In the 2-3 tree given below (i.e., NOT a 2-3-4 tree), execute insert(28), insert(99), and...
11. In the 2-3 tree given below (i.e., NOT a 2-3-4 tree), execute insert(28), insert(99), and insert(58), in that order, making sure to rebalance after each insertion. Draw the resulting 2-3 tree after executing these operations. 45 20 70 30 60 80 90 2(4(10 11) (25) (40) (50 55) (65) (71 75)(85) (92 96
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...
2. a) Consider the following AVL Tree. 50 / 25 75 10 Insert the following values...
2. a) Consider the following AVL Tree. 50 / 25 75 10 Insert the following values in the given AVL Tree, one after another, and show the resulting tree after each insertion. You must justify your answer by explaining the rotation operation you performed during insertion. 17 40 10 90 5 100 b) Delete the root of the resulting tree in Question 2.a. Show the resulting AVL Tree. Justify your answer by showing every step during deletion.
5. Submission Take an empty B-tree of order 3. Take into 4 2-digit integers. Insert each of these 2-digit numbers in...
5. Submission Take an empty B-tree of order 3. Take into 4 2-digit integers. Insert each of these 2-digit numbers in the order in which they appear in your student number into the empty heap. Then insert the values 10, 30, 50 70, 90. For your solution, write out the B-tree after each insertion. your student number and split it Example If your student number was 40260833, your solution would look something like the following. The o-->here indicates a child...
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....
(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.)
11. In the 2-3 tree given below (i.e., NOT a 2-3-4 tree), execute insert(28), insert(99), and insert(58), in that order, making sure to rebalance after each insertion. Draw the resulting 2-3 tree after executing these operations. 45 20 70 30 60 80 90 2(4(10 11) (25) (40) (50 55) (65) (71 75)(85) (92 96
2. a) Consider the following AVL Tree. 50 / 25 75 10 Insert the following values in the given AVL Tree, one after another, and show the resulting tree after each insertion. You must justify your answer by explaining the rotation operation you performed during insertion. 17 40 10 90 5 100 b) Delete the root of the resulting tree in Question 2.a. Show the resulting AVL Tree. Justify your answer by showing every step during deletion.
5. Submission Take an empty B-tree of order 3. Take into 4 2-digit integers. Insert each of these 2-digit numbers in the order in which they appear in your student number into the empty heap. Then insert the values 10, 30, 50 70, 90. For your solution, write out the B-tree after each insertion. your student number and split it Example If your student number was 40260833, your solution would look something like the following. The o-->here indicates a child...
Most questions answered within 3 hours.
-
Discuss at least five differences between supply chain
partnerships of the past and those that have...
asked 34 minutes ago -
"The Ramsey family has total assets of $1,000,000 and total
liabilities of $700,000. Included in their...
asked 1 hour ago -
The following table gives information on the amount of sugar (in
grams) and the calorie count...
asked 3 hours ago -
A car travels at an average speed of 56 mph for 15 hours. What
was the...
asked 3 hours ago -
Exercise on Mirror, Mirror on the Wall/lnitial Self
Evaluation
Write an Initial Self Evaluation paper that...
asked 4 hours ago -
Implementation of policy recommendations is often a
problem. What do you see as the major barriers...
asked 5 hours ago -
23- The consideration needed to support a contract
must:
a. Flow to the promise AND have...
asked 7 hours ago -
1. What is the main causal factor of Border line personality
disorder? Research has also found...
asked 9 hours ago -
The National Institute of Standards and Technology (NIST)
supplies "standard materials" whose physical properties are
supposed...
asked 9 hours ago -
Alpha Centauri A and B are Sun-like stars, and together they
form the binary star Alpha...
asked 9 hours ago -
What is the pH of a 0.200 M solution of sulfurous acid? Given:
Ka1 = 1.70×10–2,...
asked 9 hours ago -
Sociologists have conducted much interesting research on gender
stereotypes in American society. A curious aspect of...
asked 9 hours ago