Homework Help is Here – Start Your Trial Now!
Engineering
Computer Science
324 Chapter 8. Trees Operations for Updating a Linked Binary Tree The Tree and Binary Tree interfaces define a variety of methods for inspecting an existing tree, yet they do not declare any update methods. Presuming that a newly constructed tree is empty, we would like to have means for changing the structure of content of a tree. Although the principle of encapsulation suggests that the outward behaviors of an abstract data type need not depend on the internal representation, the efficiency of the operations depends greatly upon the representation. We therefore prefer to have each concrete implementation of a tree class support the most suitable behaviors for updating a tree. In the case of a linked binary tree, we suggest that the following update methods be supported: add Root(e): Creates a root for an empty tree, storing e as the element, and returns the position of that root; an error occurs if the tree is not empty. add Left(p, e): Creates a left child of position p, storing element e, and returns the position of the new node; an error occurs if p already has a left child. addRight(p, e): Creates a right child of position p, storing element e, and returns the position of the new node; an error occurs if p already has a right child. set(p, e): Replaces the element stored at position p with element e, and returns the previously stored element. attach(p, T₁, T₂): Attaches the internal structure of trees T₁ and T₂ as the respective left and right subtrees of leaf position p and resets T₁ and T₂ to empty trees; an error condition occurs if p is not a leaf. remove(p): Removes the node at position p, replacing it with its child (if any), and returns the element that had been stored at p; an error occurs if p has two children. We have specifically chosen this collection of operations because each can be implemented in 0(1) worst-case time with our linked representation. The most complex of these are attach and remove, due to the case analyses involving the various parent-child relationships and boundary conditions, yet there remains only a constant number of operations to perform. (The implementation of both methods could be greatly simplified if we used a tree representation with a sentinel node, akin to our treatment of positional lists; see Exercise C-8.38.) root 5 size Baltimore H Chicago Ø New York (b) Ø Ø Providence Seattle

324 Chapter 8. Trees Operations for Updating a Linked Binary Tree The Tree and Binary Tree interfaces define a variety of methods for inspecting an existing tree, yet they do not declare any update methods. Presuming that a newly constructed tree is empty, we would like to have means for changing the structure of content of a tree. Although the principle of encapsulation suggests that the outward behaviors of an abstract data type need not depend on the internal representation, the efficiency of the operations depends greatly upon the representation. We therefore prefer to have each concrete implementation of a tree class support the most suitable behaviors for updating a tree. In the case of a linked binary tree, we suggest that the following update methods be supported: add Root(e): Creates a root for an empty tree, storing e as the element, and returns the position of that root; an error occurs if the tree is not empty. add Left(p, e): Creates a left child of position p, storing element e, and returns the position of the new node; an error occurs if p already has a left child. addRight(p, e): Creates a right child of position p, storing element e, and returns the position of the new node; an error occurs if p already has a right child. set(p, e): Replaces the element stored at position p with element e, and returns the previously stored element. attach(p, T₁, T₂): Attaches the internal structure of trees T₁ and T₂ as the respective left and right subtrees of leaf position p and resets T₁ and T₂ to empty trees; an error condition occurs if p is not a leaf. remove(p): Removes the node at position p, replacing it with its child (if any), and returns the element that had been stored at p; an error occurs if p has two children. We have specifically chosen this collection of operations because each can be implemented in 0(1) worst-case time with our linked representation. The most complex of these are attach and remove, due to the case analyses involving the various parent-child relationships and boundary conditions, yet there remains only a constant number of operations to perform. (The implementation of both methods could be greatly simplified if we used a tree representation with a sentinel node, akin to our treatment of positional lists; see Exercise C-8.38.) root 5 size Baltimore H Chicago Ø New York (b) Ø Ø Providence Seattle

Database System Concepts
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
icon
Related questions
Question

Java programming homework

Please help me with this Question. I really need to understand it

324 Chapter 8. Trees Operations for Updating a Linked Binary Tree The Tree and Binary Tree interfaces define a variety of methods for inspecting an existing tree, yet they do not declare any update methods. Presuming that a newly constructed tree is empty, we would like to have means for changing the structure of content of a tree. Although the principle of encapsulation suggests that the outward behaviors of an abstract data type need not depend on the internal representation, the efficiency of the operations depends greatly upon the representation. We therefore prefer to have each concrete implementation of a tree class support the most suitable behaviors for updating a tree. In the case of a linked binary tree, we suggest that the following update methods be supported: add Root(e): Creates a root for an empty tree, storing e as the element, and returns the position of that root; an error occurs if the tree is not empty. add Left(p, e): Creates a left child of position p, storing element e, and returns the position of the new node; an error occurs if p already has a left child. addRight(p, e): Creates a right child of position p, storing element e, and returns the position of the new node; an error occurs if p already has a right child. set(p, e): Replaces the element stored at position p with element e, and returns the previously stored element. attach(p, T₁, T₂): Attaches the internal structure of trees T₁ and T₂ as the respective left and right subtrees of leaf position p and resets T₁ and T₂ to empty trees; an error condition occurs if p is not a leaf. remove(p): Removes the node at position p, replacing it with its child (if any), and returns the element that had been stored at p; an error occurs if p has two children. We have specifically chosen this collection of operations because each can be implemented in 0(1) worst-case time with our linked representation. The most complex of these are attach and remove, due to the case analyses involving the various parent-child relationships and boundary conditions, yet there remains only a constant number of operations to perform. (The implementation of both methods could be greatly simplified if we used a tree representation with a sentinel node, akin to our treatment of positional lists; see Exercise C-8.38.)
Transcribed Image Text:324 Chapter 8. Trees Operations for Updating a Linked Binary Tree The Tree and Binary Tree interfaces define a variety of methods for inspecting an existing tree, yet they do not declare any update methods. Presuming that a newly constructed tree is empty, we would like to have means for changing the structure of content of a tree. Although the principle of encapsulation suggests that the outward behaviors of an abstract data type need not depend on the internal representation, the efficiency of the operations depends greatly upon the representation. We therefore prefer to have each concrete implementation of a tree class support the most suitable behaviors for updating a tree. In the case of a linked binary tree, we suggest that the following update methods be supported: add Root(e): Creates a root for an empty tree, storing e as the element, and returns the position of that root; an error occurs if the tree is not empty. add Left(p, e): Creates a left child of position p, storing element e, and returns the position of the new node; an error occurs if p already has a left child. addRight(p, e): Creates a right child of position p, storing element e, and returns the position of the new node; an error occurs if p already has a right child. set(p, e): Replaces the element stored at position p with element e, and returns the previously stored element. attach(p, T₁, T₂): Attaches the internal structure of trees T₁ and T₂ as the respective left and right subtrees of leaf position p and resets T₁ and T₂ to empty trees; an error condition occurs if p is not a leaf. remove(p): Removes the node at position p, replacing it with its child (if any), and returns the element that had been stored at p; an error occurs if p has two children. We have specifically chosen this collection of operations because each can be implemented in 0(1) worst-case time with our linked representation. The most complex of these are attach and remove, due to the case analyses involving the various parent-child relationships and boundary conditions, yet there remains only a constant number of operations to perform. (The implementation of both methods could be greatly simplified if we used a tree representation with a sentinel node, akin to our treatment of positional lists; see Exercise C-8.38.)
root 5 size Baltimore H Chicago Ø New York (b) Ø Ø Providence Seattle
Transcribed Image Text:root 5 size Baltimore H Chicago Ø New York (b) Ø Ø Providence Seattle
Expert Solution
steps

Step by step

Solved in 2 steps with 1 images

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Knowledge Booster
Types of trees
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.
Recommended textbooks for you
Database System Concepts
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)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education
SEE MORE TEXTBOOKS