The definition for binary search tree should be the one used in class (which is different from that adopted by the suggested-book authors). ► Class definition: Suggested-book definition: A BST is a binary tree that (if not empty) also follows two storage rules regarding its nodes’ items: A BST is a binary tree that (if not empty) also follows two storage rules regarding its nodes’ items: ♯ For any node n of the tree, every item in n’s left subtree (LST), if not empty, is less than the item in n ♯ For any node n of the tree, every item in n’s left subtree (LST), if not empty, is less than or equal the item in n ♯ For any node n of the tree, every item in n’s right subtree (RST), if not empty, is greater than the item in n ♯ For any node n of the tree, every item in n’s right subtree (RST), if not empty, is greater than the item in n ● bst_insert must be iterative (NOT recursive). ● bst_remove and bst_remove_max must use the algorithm described by the suggested book authors, appropriately adapted for the difference in tree definition above In btNode.h: provide prototypes for bst_insert, bst_remove and bst_remove_max. ● In btNode.cpp: provide definition (implementation) for bst_insert, bst_remove and bst_remove_max. Here is what the test output is suppose to look like: ============================== test case 1 of 990000 attempt to remove 5 values below: (sequential order) -2 8 -4 0 1 (value-sort order) -4 -2 0 1 8 from 8 values below: -8 -7 -6 -2 -1 0 1 2 gives (with 3 values successfully removed) -8 -7 -6 -1 2 ============================== test case 2 of 990000 attempt to remove 7 values below: (sequential order) 8 -3 -5 -4 5 6 4 (value-sort order) -5 -4 -3 4 5 6 8

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

●	The definition for binary search tree should be the one used in class (which is different from that adopted by the suggested-book authors).

►

Class definition:

Suggested-book definition:

A BST is a binary tree that (if not empty) also follows two storage rules regarding its nodes’ items:

♯

For any node n of the tree, every item in n’s left subtree (LST), if not empty, is less than the item in n

♯

For any node n of the tree, every item in n’s left subtree (LST), if not empty, is less than or equal the item in n

♯

For any node n of the tree, every item in n’s right subtree (RST), if not empty, is greater than the item in n

♯

For any node n of the tree, every item in n’s right subtree (RST), if not empty, is greater than the item in n

●	bst_insert must be iterative (NOT recursive).

●	bst_remove and bst_remove_max must use the algorithm described by the suggested book authors, appropriately adapted for the difference in tree definition above

In btNode.h: provide prototypes for bst_insert, bst_remove and bst_remove_max.

●

In btNode.cpp: provide definition (implementation) for bst_insert, bst_remove and bst_remove_max.

Here is what the test output is suppose to look like:

==============================
test case 1 of 990000
attempt to remove 5 values below:
(sequential order) -2 8 -4 0 1
(value-sort order) -4 -2 0 1 8
from 8 values below:
-8 -7 -6 -2 -1 0 1 2
gives (with 3 values successfully removed)
-8 -7 -6 -1 2
==============================
test case 2 of 990000
attempt to remove 7 values below:
(sequential order) 8 -3 -5 -4 5 6 4
(value-sort order) -5 -4 -3 4 5 6 8
from 6 values below:
-8 -5 -4 -3 -2 3
gives (with 3 values successfully removed)
-8 -2 3
==============================
test case 3 of 990000
attempt to remove 5 values below:
(sequential order) 4 -6 -4 -1 6
(value-sort order) -6 -4 -1 4 6
from 11 values below:
-8 -7 -6 -5 -4 -2 -1 0 5 6 7
gives (with 4 values successfully removed)
-8 -7 -5 -2 0 5 7
==============================
test case 4 of 990000
attempt to remove 1 values below:
(sequential order) 8
(value-sort order) 8
from 12 values below:
-9 -8 -7 -6 -4 -3 -1 1 3 4 5 9
gives (with 0 values successfully removed)
-9 -8 -7 -6 -4 -3 -1 1 3 4 5 9

==============================
test case 5 of 990000
attempt to remove 8 values below:
(sequential order) 4 -6 4 2 -9 7 -7 5
(value-sort order) -9 -7 -6 2 4 4 5 7
from 9 values below:
-8 -5 -4 -2 1 2 3 8 9
gives (with 1 values successfully removed)
-8 -5 -4 -2 1 3 8 9
==============================
test case 66000 of 990000
attempt to remove 3 values below:
(sequential order) 1 -1 7
(value-sort order) -1 1 7
from 4 values below:
-5 -3 0 8
gives (with 0 values successfully removed)
-5 -3 0 8
==============================
test case 132000 of 990000
attempt to remove 8 values below:
(sequential order) 7 6 -3 5 -1 -4 2 1
(value-sort order) -4 -3 -1 1 2 5 6 7
from 13 values below:
-8 -7 -6 -5 -4 -3 -2 -1 0 1 4 6 7
gives (with 6 values successfully removed)
-8 -7 -6 -5 -2 0 4

C-btNode.cpp
C-btNode.cpp > ...
1 #include "btNode.h"
2
4
5
6
7
8
9
10
// write definition for bst_insert here
// write definition for bst_remove here
V
// write definition for bst_remove_max here
void portToArrayInOrder (btNode* bst_root, int* portArray)
{
11
12
13
14
15
16
17 void portToArrayInOrder Aux(btNode* bst_root, int* portArray, int& portIndex)
}
18 {
19
20
21
22
23
24
25 void tree_clear (btNode*& root)
26
{
27
28
29
30
}
if (bst_root == 0) return;
int portIndex = 0;
portToArrayInOrder Aux(bst_root, portArray, portIndex);
}
}
if (bst_root == 0) return;
portToArrayInOrder Aux(bst_root->left, portArray, portIndex);
portArray[portIndex++] = bst_root->data;
portToArrayInOrderAux(bst_root->right, portArray, portIndex);
if (root == 0) return;
tree_clear (root->left);
tree_clear (root->right);
31
32
33
34 int bst_size(btNode* bst_root)
35 {
36
37
38
delete root;
root = 0;
if (bst_root == 0) return 0;
return 1 + bst_size(bst_root->left) + bst_size(bst_root->right);

=a6p2test.txt x
C btNode.h>...
30 /////
31
32 // pre:
33
34 // post:
35
//
36
//
37
//
38 //
39
//
40
//
41
42
43
44
45
46
47
48
49
50
51
52
53
54
btNode.h B X
// write prototype for bst_insert here
// pre: bst_root is root pointer of a binary search tree (may be 0 for
//
empty tree)
// post:
//
//
//
// pre:
// post:
55
//
56 //
57 //
58
bst_root is root pointer of a binary search tree (may be for
empty tree)
If no node in the binary search tree has data equals insInt, a
node with data insInt has been created and inserted at the proper
location in the tree to maintain binary search tree property.
If a node with data equals insInt is found, the node's data field
has been overwritten with insInt; no new node has been created.
(Latter case seems odd but it's to mimick update of key-associated
data that exists in more general/real-world situations.)
// write prototype for bst_remove here
///
If remInt was in the tree, then rem Int has been removed, bst_root
now points to the root of the new (smaller) binary search tree,
and the function returns true. Otherwise, if remInt was not in the
tree, then the tree is unchanged, and the function returns false.
bst_root is root pointer of a non-empty binary search tree
The largest item in the binary search tree has been removed, and
bst_root now points to the root of the new (smaller) binary search
tree. The reference parameter, removed, has been set to a copy of
the removed item.
59 // write prototype for bst_remove_max here
60
61 #endif
62

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 3 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.