{"id":150,"date":"2018-07-19T05:01:16","date_gmt":"2018-07-19T05:01:16","guid":{"rendered":"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/?post_type=chapter&#038;p=150"},"modified":"2018-07-19T11:25:53","modified_gmt":"2018-07-19T11:25:53","slug":"multimedia-data-structures-2","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/chapter\/multimedia-data-structures-2\/","title":{"rendered":"Multimedia Data Structures"},"content":{"raw":"<strong>The MX-Quadtree<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">In the case of both 2-d trees and point quadtrees, the \"shape\" of the tree depends upon the order in which objects are inserted into the tree. In particular, the order affects the height of the tree, which, in turn, may affect the complexity of search and insertion operations. Also, for both 2-d trees and point quadtrees, each node N represents a region and splits the region into two (for 2-d trees) or four (for point quadtrees) subregions. The split may be uneven, depending upon exactly where the point (iV.XVAL,iV.YVAL) is located inside the region represented by node N. In contrast, the aim behind MX-quadtrees was to ensure that the shape (and height) of the tree was independent of the number of nodes present in the tree, as well as the order of insertion of these nodes. Additionally, the MX-quadtree aimed at providing efficient deletion and search algorithms.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">In short, the MX-quadtree works as follows: First, we assume that the map being represented is split up into a grid of size (2* X 2k) for some k. The application developer is free to choose k to reflect the desired granularity, but once k is chosen, it must be kept fixed.<\/p>\r\n\r\n<ul>\r\n \t<li><strong>Node Structure<\/strong>: Exactly the same as for point quadtrees, except that the root of an MX-quadtree represents the region speficied by XLB= 0, XUB= 2k, YLB= 0, YUB=2k.<\/li>\r\n \t<li>When a region gets \u201csplit\", it gets split down the middle.<\/li>\r\n \t<li>Thus, if N is a node, then the regions represented by the four children of N<\/li>\r\n<\/ul>\r\n<p style=\"text-align: center\"><img class=\"alignnone size-full wp-image-151\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-61.png\" alt=\"\" width=\"634\" height=\"250\" \/><\/p>\r\n&nbsp;\r\n\r\n<strong>INSERTION INTO MX-QUAD TREES:<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Let us now examine how we might insert points into an MX-quadtree. Each point (x,y) in an MX-quadtree represents the lxl region whose lower-left corner is (x,y). A point is inserted at the node representing the lxl region corresponding to that point. Suppose now that we wish to insert the points A, B, C, and D shown in Figure. We proceed as follows:<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><span style=\"font-size: 1em\">The insertion of point A with coordinates (1,3) causes the following: The root node represents the entire region, and A lies in its NW quadrant. Thus, the root's NW child corresponds to the 2x2 region whose lower-left corner is the point (0, 2). The point A is in the NE subquadrant of this region. Figure shows the MX-quadtree resulting after the insertion of A; Figure shows the split of the regions involved. Note that point A is inserted at level 2 in the tree, and this level is identical to k. In general, points will always be inserted at level k in the MX-quadtree.<\/span><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><span style=\"font-size: 1em\">The insertion of point B with coordinates (3,3) causes a branch to the NE quadrant as B. Thus, the root's NE child corresponds to the 2x2 region whose lower-left corner is the point (2, 2). The point B is in the NE sub- quadrant of this region. Figure given below show the resulting situation.<\/span><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><span style=\"font-size: 1em\">The insertion of point C with coordinates (3,1) proceeds as follows: C is in the SE quadrant of the whole region. This causes us to create a new node.<\/span><\/p>\r\n&nbsp;\r\n<p style=\"text-align: center\"><img class=\"size-full wp-image-152 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-62.png\" alt=\"\" width=\"625\" height=\"408\" \/><\/p>\r\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0After insertion of D\r\n<p style=\"text-align: center\"><img class=\"size-full wp-image-153 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-63.png\" alt=\"\" width=\"598\" height=\"287\" \/><\/p>\r\n\r\n<div>\r\n\r\n<strong>\u00a0 \u00a0 \u00a0DELETION IN MX-QUAD TREES:<\/strong>\r\n<ul>\r\n \t<li style=\"text-align: justify\">Deletion in an MX-quadtree is a fairly simple operation, because all points are represented at the leaf level.<\/li>\r\n \t<li style=\"text-align: justify\">If N is an interior (i.e. non-leaf) node in an MX-quadtree whose root is pointed to by T, then the region implicitly represented by node N contains at least one point that is explicitly contained in the tree.<\/li>\r\n \t<li style=\"text-align: justify\">If we wish to delete a point (x, y) from tree T, we try to preserve this property.<\/li>\r\n<\/ul>\r\n&nbsp;\r\n\r\nThis can be done as follows.\r\n<ul>\r\n \t<li style=\"text-align: justify\">First, we set the appropriate link of N's parent to NIL.<\/li>\r\n \t<li style=\"text-align: justify\">We then check if all the four link fields of M are NIL.<\/li>\r\n \t<li style=\"text-align: justify\">If so, we examine M's parent (let us call it P for now). As M is P's child, we find a link field dir1 such that P.dir1 = M. We then set P.dir1 = NIL and then (as before) check to see if P's four link fields are all NIL.<\/li>\r\n \t<li style=\"text-align: justify\">if so, we continue this process.<\/li>\r\n \t<li style=\"text-align: justify\">Total time required for deletion is O(k).<\/li>\r\n<\/ul>\r\n<\/div>\r\n<strong>Range Queries in MX-Quadtrees<\/strong>\r\n\r\n&nbsp;\r\n\r\nHandled in exactly the same way as for point quadtrees. But there are two differences:\r\n<ul>\r\n \t<li style=\"text-align: justify\">The content of the XLB,XUB,YLB,YUB fields is different from that in the case of point quadtrees.<\/li>\r\n \t<li style=\"text-align: justify\">As points are stored at the leaf level, checking to see if a point is in the circle denied by the range query needs to be performed only at the leaf level.<\/li>\r\n<\/ul>\r\n<strong>\u00a0 \u00a0 \u00a0R-Trees<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Used to store rectangular regions of an image or a map such as those shown below. R-trees are particularly useful in storing very large amounts of data on disk. They provide a convenient way of minimizing the number of disk accesses. Each R-tree has an associated order, which is an integer K.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Each non-leaf R-tree node contains a set of at most K rectangles and at least K\/2 rectangles (with the possible exception of the root). Intuitively, this says that each nonleaf node in the R-tree, with the exception of the root, must be at least \u201chalf\u201d full.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">This feature makes R-trees appropriate for disk based retrieval because each disk access brings back a page containing several (i.e. at least K\/2 rectangles). R-trees manipulate two kinds of rectangles:<\/p>\r\n&nbsp;\r\n\r\n\u201cReal\u201d rectangles. \u201cGroup\u201d rectangles.\r\n\r\nThis is an R-Tree of order 4, associated with the rectangles.\r\n\r\n&nbsp;\r\n<p style=\"text-align: center\"><img class=\"size-full wp-image-154 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-64.png\" alt=\"\" width=\"602\" height=\"229\" \/><\/p>\r\n<strong>R-tree nodes have the following structure:<\/strong>\r\n\r\n&nbsp;\r\n\r\n<strong>rtnodetype = record<\/strong>\r\n\r\n&nbsp;\r\n\r\nRec1,\u2026,<strong>Reck:rectangle<\/strong>;\r\n\r\n&nbsp;\r\n\r\nP1,\u2026,Pk: \u2191<strong>rtnotetype<\/strong>\r\n\r\n&nbsp;\r\n\r\n<strong>end<\/strong>\r\n\r\n&nbsp;\r\n\r\n<strong>Deletion in R-Trees<\/strong>\r\n<ul>\r\n \t<li style=\"text-align: justify\">Deletion of objects from R-trees may cause a node in the R-tree to \u201cunderflow\u201d because an R-tree of order K must contain at least K\/2 rectangles (real or group) in it.<\/li>\r\n \t<li style=\"text-align: justify\">When we delete a rectangle from an R-tree, we must ensure that that node is not \u201cunder full.\u201d<\/li>\r\n \t<li style=\"text-align: justify\">If we delete R9, then the node containing rectangle R9 would have only one node in it. In this case, we must create a new logical grouping.<\/li>\r\n<\/ul>\r\nOne possibility is to reallocate the groups as follows:\r\n\r\n&nbsp;\r\n<p style=\"text-align: center\"><img class=\"size-full wp-image-155 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-65.png\" alt=\"\" width=\"242\" height=\"204\" \/><\/p>\r\n&nbsp;\r\n\r\nThe new R-tree is:\r\n\r\n&nbsp;\r\n<p style=\"text-align: center\"><img class=\"size-full wp-image-157 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-67.png\" alt=\"\" width=\"540\" height=\"252\" \/><\/p>\r\n<p style=\"text-align: center\"><img class=\"size-full wp-image-158 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-68.png\" alt=\"\" width=\"638\" height=\"445\" \/><\/p>\r\n&nbsp;","rendered":"<p><strong>The MX-Quadtree<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">In the case of both 2-d trees and point quadtrees, the &#8220;shape&#8221; of the tree depends upon the order in which objects are inserted into the tree. In particular, the order affects the height of the tree, which, in turn, may affect the complexity of search and insertion operations. Also, for both 2-d trees and point quadtrees, each node N represents a region and splits the region into two (for 2-d trees) or four (for point quadtrees) subregions. The split may be uneven, depending upon exactly where the point (iV.XVAL,iV.YVAL) is located inside the region represented by node N. In contrast, the aim behind MX-quadtrees was to ensure that the shape (and height) of the tree was independent of the number of nodes present in the tree, as well as the order of insertion of these nodes. Additionally, the MX-quadtree aimed at providing efficient deletion and search algorithms.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">In short, the MX-quadtree works as follows: First, we assume that the map being represented is split up into a grid of size (2* X 2k) for some k. The application developer is free to choose k to reflect the desired granularity, but once k is chosen, it must be kept fixed.<\/p>\n<ul>\n<li><strong>Node Structure<\/strong>: Exactly the same as for point quadtrees, except that the root of an MX-quadtree represents the region speficied by XLB= 0, XUB= 2k, YLB= 0, YUB=2k.<\/li>\n<li>When a region gets \u201csplit&#8221;, it gets split down the middle.<\/li>\n<li>Thus, if N is a node, then the regions represented by the four children of N<\/li>\n<\/ul>\n<p style=\"text-align: center\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-151\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-61.png\" alt=\"\" width=\"634\" height=\"250\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-61.png 634w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-61-300x118.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-61-65x26.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-61-225x89.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-61-350x138.png 350w\" sizes=\"auto, (max-width: 634px) 100vw, 634px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><strong>INSERTION INTO MX-QUAD TREES:<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Let us now examine how we might insert points into an MX-quadtree. Each point (x,y) in an MX-quadtree represents the lxl region whose lower-left corner is (x,y). A point is inserted at the node representing the lxl region corresponding to that point. Suppose now that we wish to insert the points A, B, C, and D shown in Figure. We proceed as follows:<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><span style=\"font-size: 1em\">The insertion of point A with coordinates (1,3) causes the following: The root node represents the entire region, and A lies in its NW quadrant. Thus, the root&#8217;s NW child corresponds to the 2&#215;2 region whose lower-left corner is the point (0, 2). The point A is in the NE subquadrant of this region. Figure shows the MX-quadtree resulting after the insertion of A; Figure shows the split of the regions involved. Note that point A is inserted at level 2 in the tree, and this level is identical to k. In general, points will always be inserted at level k in the MX-quadtree.<\/span><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><span style=\"font-size: 1em\">The insertion of point B with coordinates (3,3) causes a branch to the NE quadrant as B. Thus, the root&#8217;s NE child corresponds to the 2&#215;2 region whose lower-left corner is the point (2, 2). The point B is in the NE sub- quadrant of this region. Figure given below show the resulting situation.<\/span><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><span style=\"font-size: 1em\">The insertion of point C with coordinates (3,1) proceeds as follows: C is in the SE quadrant of the whole region. This causes us to create a new node.<\/span><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: center\"><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-152 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-62.png\" alt=\"\" width=\"625\" height=\"408\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-62.png 625w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-62-300x196.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-62-65x42.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-62-225x147.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-62-350x228.png 350w\" sizes=\"auto, (max-width: 625px) 100vw, 625px\" \/><\/p>\n<p>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0After insertion of D<\/p>\n<p style=\"text-align: center\"><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-153 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-63.png\" alt=\"\" width=\"598\" height=\"287\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-63.png 598w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-63-300x144.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-63-65x31.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-63-225x108.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-63-350x168.png 350w\" sizes=\"auto, (max-width: 598px) 100vw, 598px\" \/><\/p>\n<div>\n<p><strong>\u00a0 \u00a0 \u00a0DELETION IN MX-QUAD TREES:<\/strong><\/p>\n<ul>\n<li style=\"text-align: justify\">Deletion in an MX-quadtree is a fairly simple operation, because all points are represented at the leaf level.<\/li>\n<li style=\"text-align: justify\">If N is an interior (i.e. non-leaf) node in an MX-quadtree whose root is pointed to by T, then the region implicitly represented by node N contains at least one point that is explicitly contained in the tree.<\/li>\n<li style=\"text-align: justify\">If we wish to delete a point (x, y) from tree T, we try to preserve this property.<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p>This can be done as follows.<\/p>\n<ul>\n<li style=\"text-align: justify\">First, we set the appropriate link of N&#8217;s parent to NIL.<\/li>\n<li style=\"text-align: justify\">We then check if all the four link fields of M are NIL.<\/li>\n<li style=\"text-align: justify\">If so, we examine M&#8217;s parent (let us call it P for now). As M is P&#8217;s child, we find a link field dir1 such that P.dir1 = M. We then set P.dir1 = NIL and then (as before) check to see if P&#8217;s four link fields are all NIL.<\/li>\n<li style=\"text-align: justify\">if so, we continue this process.<\/li>\n<li style=\"text-align: justify\">Total time required for deletion is O(k).<\/li>\n<\/ul>\n<\/div>\n<p><strong>Range Queries in MX-Quadtrees<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Handled in exactly the same way as for point quadtrees. But there are two differences:<\/p>\n<ul>\n<li style=\"text-align: justify\">The content of the XLB,XUB,YLB,YUB fields is different from that in the case of point quadtrees.<\/li>\n<li style=\"text-align: justify\">As points are stored at the leaf level, checking to see if a point is in the circle denied by the range query needs to be performed only at the leaf level.<\/li>\n<\/ul>\n<p><strong>\u00a0 \u00a0 \u00a0R-Trees<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Used to store rectangular regions of an image or a map such as those shown below. R-trees are particularly useful in storing very large amounts of data on disk. They provide a convenient way of minimizing the number of disk accesses. Each R-tree has an associated order, which is an integer K.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Each non-leaf R-tree node contains a set of at most K rectangles and at least K\/2 rectangles (with the possible exception of the root). Intuitively, this says that each nonleaf node in the R-tree, with the exception of the root, must be at least \u201chalf\u201d full.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">This feature makes R-trees appropriate for disk based retrieval because each disk access brings back a page containing several (i.e. at least K\/2 rectangles). R-trees manipulate two kinds of rectangles:<\/p>\n<p>&nbsp;<\/p>\n<p>\u201cReal\u201d rectangles. \u201cGroup\u201d rectangles.<\/p>\n<p>This is an R-Tree of order 4, associated with the rectangles.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: center\"><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-154 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-64.png\" alt=\"\" width=\"602\" height=\"229\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-64.png 602w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-64-300x114.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-64-65x25.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-64-225x86.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-64-350x133.png 350w\" sizes=\"auto, (max-width: 602px) 100vw, 602px\" \/><\/p>\n<p><strong>R-tree nodes have the following structure:<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong>rtnodetype = record<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Rec1,\u2026,<strong>Reck:rectangle<\/strong>;<\/p>\n<p>&nbsp;<\/p>\n<p>P1,\u2026,Pk: \u2191<strong>rtnotetype<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong>end<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong>Deletion in R-Trees<\/strong><\/p>\n<ul>\n<li style=\"text-align: justify\">Deletion of objects from R-trees may cause a node in the R-tree to \u201cunderflow\u201d because an R-tree of order K must contain at least K\/2 rectangles (real or group) in it.<\/li>\n<li style=\"text-align: justify\">When we delete a rectangle from an R-tree, we must ensure that that node is not \u201cunder full.\u201d<\/li>\n<li style=\"text-align: justify\">If we delete R9, then the node containing rectangle R9 would have only one node in it. In this case, we must create a new logical grouping.<\/li>\n<\/ul>\n<p>One possibility is to reallocate the groups as follows:<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: center\"><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-155 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-65.png\" alt=\"\" width=\"242\" height=\"204\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-65.png 242w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-65-65x55.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-65-225x190.png 225w\" sizes=\"auto, (max-width: 242px) 100vw, 242px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>The new R-tree is:<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: center\"><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-157 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-67.png\" alt=\"\" width=\"540\" height=\"252\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-67.png 540w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-67-300x140.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-67-65x30.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-67-225x105.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-67-350x163.png 350w\" sizes=\"auto, (max-width: 540px) 100vw, 540px\" \/><\/p>\n<p style=\"text-align: center\"><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-158 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-68.png\" alt=\"\" width=\"638\" height=\"445\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-68.png 638w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-68-300x209.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-68-65x45.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-68-225x157.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-68-350x244.png 350w\" sizes=\"auto, (max-width: 638px) 100vw, 638px\" \/><\/p>\n<p>&nbsp;<\/p>\n","protected":false},"author":4,"menu_order":18,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["dr-r-baskaran"],"pb_section_license":""},"chapter-type":[],"contributor":[58],"license":[],"class_list":["post-150","chapter","type-chapter","status-publish","hentry","contributor-dr-r-baskaran"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/pressbooks\/v2\/chapters\/150","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/wp\/v2\/users\/4"}],"version-history":[{"count":2,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/pressbooks\/v2\/chapters\/150\/revisions"}],"predecessor-version":[{"id":283,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/pressbooks\/v2\/chapters\/150\/revisions\/283"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/pressbooks\/v2\/chapters\/150\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/wp\/v2\/media?parent=150"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/pressbooks\/v2\/chapter-type?post=150"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/wp\/v2\/contributor?post=150"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/wp\/v2\/license?post=150"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}