COMPUTER SCIENCE ILLUMIN.-TEXT
6th Edition
ISBN: 2810016866372
Author: Dale
Publisher: JONES+BART
expand_more
expand_more
format_list_bulleted
Question
Chapter 8, Problem 47E
Program Plan Intro
Binary search tree:
- Binary search tree is a tree; the nodes are sorted in the semantic order.
- Binary search tree nodes can have zero, one, or two children.
- Node without children is called a leaf or end node.
- A node that does not have a superior node is called a root node or starting node.
- In binary search tree, the left subtree contains the nodes lesser than the root node.
- The right subtree contains the nodes greater than the root node.
- The binary search will performed until finding a search node or reaching the end of the tree.
Expert Solution & Answer
Explanation of Solution
Insertion of elements in the binary search tree:
Given elements to construct a binary search tree are as follows:
50, 72, 96, 107, 26, 12, 11, 9, 2, 10, 25, 51, 16, 17, 95.
Step 1:
Insert the element 50, which is the root node of a binary search tree.
Step 2:
Next element is 72, which is greater than root node element 50, so insert the element 72 as the right child of the root node.
Step 3:
- Next element is 96, which is greater than root node element 50, so insert the element 96 as the right child of the root node.
- The root node already contains the element 72 as the right child and the element 96 is greater than the element 72.
- So, insert the element 96 as the right child of 72.
Step 4:
- Next element is 107, which is greater than root node element 50, so insert the element 107 as the right child of the root node.
- The root node already contains the element 72 as the right child and the element 107 is greater than the element 72.
- The element 72 already contains the element 96 as the right child and the element 107 is greater than the element 96.
- So, insert the element 107 as the right child of 96.
Step 5:
Next element is 26, which is less than root node value 50, so insert the element 26 as the left child of the root node.
Step 6:
- Next element is 12, which is less than the root node value 50, so insert the element 12 as left child of the root node.
- The root node already contains the element 26 as the left child and the element 12 is less than the element 26.
- So, insert the element 12 as left child of the element 26.
Step 7:
- Next element is 11, which is less than the root node value 50, so insert the element 11 as left child of the root node.
- The root node already contains the element 26 as the left child and the element 11 is less than the element 26.
- The element 26 already contains the element 12 as the left child and the element 11 is lesser than the element 12.
- So, insert the element 11 as left child of the element 12.
Step 8:
- Next element is 9, which is less than the root node value 50, so insert the element 9 as left child of the root node.
- The root node already contains the element 26 as the left child and the element 9 is less than the element 26.
- The element 26 already contains the element 12 as the left child and the element 9 is lesser than the element 12.
- The element 12 already contains the element 11 as the left child and the element 9 is lesser than the element 11.
- So, insert the element 9 as left child of the element 11.
Step 9:
- Next element is 2, which is less than the root node value 50, so insert the element 2 as left child of the root node.
- The root node already contains the element 26 as the left child and the element 2 is less than the element 26.
- The element 26 already contains the element 12 as the left child and the element 2 is lesser than the element 12.
- The element 12 already contains the element 11 as the left child and the element 2 is lesser than the element 11.
- The element 11 already contains the element 9 as the left child and the element 2 is lesser than the element 9.
- So, insert the element 2 as left child of the element 9.
Step 10:
- Next element is 10, which is less than the root node value 50, so insert the element 10 as left child of the root node.
- The root node already contains the element 26 as the left child and the element 10 is less than the element 26.
- The element 26 already contains the element 12 as the left child and the element 10 is lesser than the element 12.
- The element 12 already contains the element 11 as the left child and the element 10 is lesser than the element 11.
- The element 11 already contains the element 9 as the left child and the element 10 is greater than the element 9.
- So, insert the element 10 as right child of the element 9.
Step 11:
- Next element is 25, which is less than the root node value 50, so insert the element 25 as left child of the root node.
- The root node already contains the element 26 as the left child and the element 25 is less than the element 26.
- The element 26 already contains the element 12 as the left child and the element 25 is greater than the element 12.
- So, insert the element 25 as right child of the element 12.
Step 12:
- Next element is 51, which is greater than root node element 50, so insert the element 51 as the right child of the root node.
- The root node already contains the element 72 as the right child and the element 51 is lesser than the element 72.
- So, insert the element 51 as the left child of 72.
Step 13:
- Next element is 16, which is less than the root node value 50, so insert the element 16 as left child of the root node.
- The root node already contains the element 26 as the left child and the element 16 is less than the element 26.
- The element 26 already contains the element 12 as the left child and the element 16 is greater than the element 12.
- The element 12 already contains the element 25 as the right child and the element 16 is lesser than the element 25.
- So, insert the element 16 as left child of the element 25.
Step 14:
- Next element is 17, which is less than the root node value 50, so insert the element 17 as left child of the root node.
- The root node already contains the element 26 as the left child and the element 17 is less than the element 26.
- The element 26 already contains the element 12 as the left child and the element 17 is greater than the element 12.
- The element 12 already contains the element 25 as the right child and the element 17 is lesser than the element 25.
- The element 25 already contains the element 16 as the left child and the element 17 is greater than the element 16.
- So, insert the element 17 as right child of the element 16.
Step 15:
- Next element is 95, which is greater than root node element 50, so insert the element 95 as the right child of the root node.
- The root node already contains the element 72 as the right child and the element 95 is greater than the element 72.
- The element 72 already contains the element 96 as the right child and the element 95 is lesser than the element 96.
- So, insert the element 95 as the left child of 96.
Therefore, the above tree is the final constructed binary search tree for the given elements.
Want to see more full solutions like this?
Subscribe now to access step-by-step solutions to millions of textbook problems written by subject matter experts!
Students have asked these similar questions
I would like to get help to resolve the following case
Last Chance Securities
The IT director opened the department staff meeting today by saying, "I've got some good news and
some bad news. The good news is that management approved the payroll system project this morning.
The new system will reduce clerical time and errors, improve morale in the payroll department, and avoid
possible fines and penalties for noncompliance. The bad news is that the system must be installed by
January 1st in order to meet new federal reporting rules, all expenses from now on must be approved in
advance, the system should have a modular design if possible, and the vice president of finance would
like to announce the new system in a year-end report if it is ready by mid-December."
Tasks
1. Why is it important to define the project scope? How would you define the scope of the payroll
project in this case?
2. Review each constraint and identify its characteristics: present versus future, internal versus exter-
nal, and mandatory versus desirable.
3. What…
2. Signed Integers
Unsigned binary numbers work for natural numbers, but many calculations use negative
numbers as well. To deal with this, a number of different methods have been used to represent
signed numbers, but we will focus on two's complement, as it is the standard solution for
representing signed integers.
2.1 Two's complement
• Most significant bit has a negative value, all others are positive. So, the value of an n-digit
-2
two's complement number can be written as: Σ2 2¹ di 2n-1 dn
• Otherwise exactly the same as unsigned integers.
i=0
-
• A neat trick for flipping the sign of a two's complement number: flip all the bits (0 becomes 1,
or 1 becomes 0) and then add 1 to the least significant bit.
• Addition is exactly the same as with an unsigned number.
2.2 Exercises
For questions 1-3, answer each one for the case of a two's complement number and an
unsigned number, indicating if it cannot be answered with a specific representation.
1. (15 pts) What is the largest integer…
Chapter 8 Solutions
COMPUTER SCIENCE ILLUMIN.-TEXT
Ch. 8 - Prob. 1ECh. 8 - Prob. 2ECh. 8 - Prob. 3ECh. 8 - Prob. 4ECh. 8 - Prob. 5ECh. 8 - Prob. 6ECh. 8 - Prob. 7ECh. 8 - Prob. 8ECh. 8 - Prob. 9ECh. 8 - Prob. 10E
Ch. 8 - Prob. 11ECh. 8 - Prob. 12ECh. 8 - Prob. 13ECh. 8 - Prob. 14ECh. 8 - Prob. 15ECh. 8 - Prob. 16ECh. 8 - Prob. 17ECh. 8 - Prob. 18ECh. 8 - Prob. 19ECh. 8 - Prob. 20ECh. 8 - Prob. 21ECh. 8 - Prob. 22ECh. 8 - Prob. 23ECh. 8 - Prob. 24ECh. 8 - Prob. 25ECh. 8 - Prob. 26ECh. 8 - Prob. 27ECh. 8 - Prob. 28ECh. 8 - Prob. 29ECh. 8 - Prob. 30ECh. 8 - Prob. 31ECh. 8 - Prob. 32ECh. 8 - Prob. 33ECh. 8 - Prob. 34ECh. 8 - Prob. 35ECh. 8 - Prob. 36ECh. 8 - Prob. 37ECh. 8 - Prob. 38ECh. 8 - Prob. 39ECh. 8 - Prob. 40ECh. 8 - Prob. 41ECh. 8 - Prob. 42ECh. 8 - Prob. 43ECh. 8 - Prob. 44ECh. 8 - Prob. 45ECh. 8 - Prob. 46ECh. 8 - Prob. 47ECh. 8 - Prob. 48ECh. 8 - Prob. 49ECh. 8 - Prob. 50ECh. 8 - Prob. 51ECh. 8 - Prob. 52ECh. 8 - Prob. 53ECh. 8 - Prob. 54ECh. 8 - Prob. 55ECh. 8 - Prob. 56ECh. 8 - Prob. 57ECh. 8 - Prob. 58ECh. 8 - Prob. 59ECh. 8 - Prob. 60ECh. 8 - Prob. 61ECh. 8 - Prob. 62ECh. 8 - Prob. 66ECh. 8 - Prob. 67ECh. 8 - Prob. 68ECh. 8 - Prob. 69ECh. 8 - Prob. 1TQCh. 8 - Prob. 2TQCh. 8 - Prob. 4TQ
Knowledge Booster
Similar questions
- can u solve this questionarrow_forward1. Unsigned Integers If we have an n-digit unsigned numeral dn-1d n-2...do in radix (or base) r, then the value of that numeral is n−1 r² di Σi=0 which is basically saying that instead of a 10's or 100's place we have an r's or r²'s place. For binary, decimal, and hex r equals 2, 10, and 16, respectively. Just a reminder that in order to write down a large number, we typically use the IEC or SI prefixing system: IEC: Ki = 210, Mi = 220, Gi = 230, Ti = 240, Pi = 250, Ei = 260, Zi = 270, Yi = 280; SI: K=103, M = 106, G = 109, T = 10¹², P = 1015, E = 10¹8, Z = 1021, Y = 1024. 1.1 Conversions a. (15 pts) Write the following using IEC prefixes: 213, 223, 251, 272, 226, 244 21323 Ki8 Ki 223 23 Mi 8 Mi b. (15 pts) Write the following using SI prefixes: 107, 10¹7, 10¹¹, 1022, 1026, 1015 107 10¹ M = 10 M = 1017102 P = 100 P c. (10 pts) Write the following with powers of 10: 7 K, 100 E, 21 G 7 K = 7*10³arrow_forwardanswer shoul avoid using AI and should be basic and please explainarrow_forward
- Node A is connected to node B by a 2000km fiber link having a bandwidth of 100Mbps. What is the total latency time (transmit + propagation) required to transmit a 4000 byte file using packets that include 1000 Bytes of data plus 40 Bytes of header.arrow_forwardanswer should avoid using AI and should be basic and explain pleasearrow_forwardasnwer should avoid using AIarrow_forward
- answer should avoid using AI (such as ChatGPT), do not any answer directly copied from AI would and explain codearrow_forwardWrite a c++ program that will count from 1 to 10 by 1. The default output should be: 1, 2, 3, 4, 5, 6 , 7, 8, 9, 10 There should be only a newline after the last number. Each number except the last should be followed by a comma and a space. To make your program more functional, you should parse command line arguments and change behavior based on their values. Argument Parameter Action -f, --first yes, an integer Change place you start counting -l, --last yes, an integer Change place you end counting -s, --skip optional, an integer, 1 if not specified Change the amount you add to the counter each iteration -h, —help none Print a help message including these instructions. -j, --joke none Tell a number based joke. So, if your program is called counter, counter -f 10 --last 4 --skip 2 should produce 10, 8, 6, 4 Please use the last supplied argument. If your code is called counter, counter -f 4 -f 5 -f 6 should count from 6. You should…arrow_forwardshow workarrow_forward
arrow_back_ios
SEE MORE QUESTIONS
arrow_forward_ios
Recommended textbooks for you
Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill Education
Starting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSON
Digital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSON
Database Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage Learning
Programmable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education
Database System Concepts
Computer Science
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:9780134444321
Author:Tony Gaddis
Publisher:PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:9780132737968
Author:Thomas L. Floyd
Publisher:PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:9780133976892
Author:Paul J. Deitel, Harvey Deitel
Publisher:PEARSON
Database Systems: Design, Implementation, & Manag...
Computer Science
ISBN:9781337627900
Author:Carlos Coronel, Steven Morris
Publisher:Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:9780073373843
Author:Frank D. Petruzella
Publisher:McGraw-Hill Education