In this question you are to write MIPS assembly language procedures insert and search for a quadtree data structure, and a main program to test them. Each node of the tree should be implemented with six consecutive words of memory, as shown below: x value y value NW child ptr NE child ptr SE child ptr SW child ptr address a address a+4 address a+8 address a+12 address a+16 address a+20 Each of the four child pointers (NW child ptr, NE child ptr, SE child ptr, and SW child ptr) gives the memory address of the first word of the corresponding child node. A pointer (memory address) value of zero indicates that there is no such child node. The tree nodes should be linked such that for a node with (integer) values (X,Y) all nodes in its NW subtree have x value less than or equal to X and y value greater than Y, all nodes in its NE subtree have x value greater than X and y value greater than or equal to Y, all nodes in its SE subtree have x value greater than or equal to X and y value less than Y, and all nodes in its SW subtree have x value less than X and y value less than or equal to Y.               Use “.space 600” to allocate memory sufficient for 25 nodes (25 nodes x 6 words/node x 4 bytes/word = 600 bytes). On the class Canvas site, you will find procedures init, alloc, and free, that can be used to keep track of what portions of this memory are not in use (i.e., not currently being used for a node in your tree) using a free list of nodes, and to allocate/free node-sized chunks of it. Note that these procedures differ from those used in Assignment #3, due to the different node size. On the class Canvas site you will also find the procedure deletetree which takes as its parameters the address of a memory word that contains the address of the root of the tree, and the address of a memory word containing the address of the first node in the free list. The deletetree procedure frees all of the tree nodes (using free), and stores zero into the memory word containing the address of the root of the tree. Your insert procedure should take as its parameters the (integer) x and y values of the node to be added to the tree, the address of a memory word that contains the address of the root of the tree (if the tree is not empty, otherwise the memory word would contain zero), and the address of a memory word containing the address of the first node in the free list. If there is already a node in the tree with these x and y values, the tree should not be changed. Otherwise, your insert procedure should attempt to allocate a node from your free list using alloc, and, if successful (the free list wasn’t empty), store the x and y values in that node and link the node into the tree in a position that maintains the ordering property described above. Your insert procedure should return 0 unless it was unable to add a node to the tree because the free list was empty, in which case your procedure should return 1. Your search procedure should take as its parameters the x and y values to be searched for, and the address of a memory word that contains the address of the root of the tree. It should return 1 if a node with these x and y values is present in the quadtree, and zero otherwise. Your main program should prompt the user to enter an integer N, then to enter N pairs of integers (corresponding to (x,y) values of nodes, which your program should use to build a quadtree), prompt the user to enter a pair of integers to search for, output whether or not a node with that pair is present in the tree, deallocate the quadtree using deletetree, and then repeat all of the above actions (once). Your code must use the “standard” conventions covered in class for passing parameters and returning results.

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
icon
Related questions
Question
In this question you are to write MIPS assembly language procedures insert
and search for a quadtree data structure, and a main program to test them. Each node
of the tree should be implemented with six consecutive words of memory, as shown
below:

x value y value NW child ptr NE child ptr SE child ptr SW child ptr
address a address a+4 address a+8 address a+12 address a+16 address a+20
Each of the four child pointers (NW child ptr, NE child ptr, SE child ptr, and SW child
ptr) gives the memory address of the first word of the corresponding child node. A
pointer (memory address) value of zero indicates that there is no such child node. The
tree nodes should be linked such that for a node with (integer) values (X,Y) all nodes
in its NW subtree have x value less than or equal to X and y value greater than Y, all
nodes in its NE subtree have x value greater than X and y value greater than or equal
to Y, all nodes in its SE subtree have x value greater than or equal to X and y value less
than Y, and all nodes in its SW subtree have x value less than X and y value less than
or equal to Y.
 
 
 
 
 
 
 
Use “.space 600” to allocate memory sufficient for 25 nodes (25 nodes x 6 words/node
x 4 bytes/word = 600 bytes). On the class Canvas site, you will find procedures init,
alloc, and free, that can be used to keep track of what portions of this memory are not
in use (i.e., not currently being used for a node in your tree) using a free list of nodes,
and to allocate/free node-sized chunks of it. Note that these procedures differ from
those used in Assignment #3, due to the different node size. On the class Canvas
site you will also find the procedure deletetree which takes as its parameters the address
of a memory word that contains the address of the root of the tree, and the address of a
memory word containing the address of the first node in the free list. The deletetree
procedure frees all of the tree nodes (using free), and stores zero into the memory word
containing the address of the root of the tree.
Your insert procedure should take as its parameters the (integer) x and y values of the
node to be added to the tree, the address of a memory word that contains the address of
the root of the tree (if the tree is not empty, otherwise the memory word would contain
zero), and the address of a memory word containing the address of the first node in the
free list. If there is already a node in the tree with these x and y values, the tree should
not be changed. Otherwise, your insert procedure should attempt to allocate a node
from your free list using alloc, and, if successful (the free list wasn’t empty), store the
x and y values in that node and link the node into the tree in a position that maintains
the ordering property described above. Your insert procedure should return 0 unless it
was unable to add a node to the tree because the free list was empty, in which case your
procedure should return 1.
Your search procedure should take as its parameters the x and y values to be searched
for, and the address of a memory word that contains the address of the root of the tree.
It should return 1 if a node with these x and y values is present in the quadtree, and zero
otherwise.
Your main program should prompt the user to enter an integer N, then to enter N pairs
of integers (corresponding to (x,y) values of nodes, which your program should use to
build a quadtree), prompt the user to enter a pair of integers to search for, output
whether or not a node with that pair is present in the tree, deallocate the quadtree using
deletetree, and then repeat all of the above actions (once). Your code must use the
“standard” conventions covered in class for passing parameters and returning
results.
Expert Solution
steps

Step by step

Solved in 3 steps

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.
Similar questions
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