CSE 326: Data Structures Part 10 Advanced Data StructuresOutlineMulti-D Search ADTApplications of Multi-D SearchRange QueryRange Query Examples: Two DimensionsRange Querying in 1-DRange Querying in 1-D with a BST1-D Range Querying in 2-D2-D Range Querying in 2-Dk-D TreesFind in a k-D TreeFind ExampleBuilding a 2-D Tree (1/4)Building a 2-D Tree (2/4)Building a 2-D Tree (3/4)Building a 2-D Tree (4/4)k-D Tree2-D Range Querying in 2-D TreesRange Query in a 2-D TreeRange Query in a k-D TreeOther Shapes for Range Queryingk-D Trees Can Be Inefficient (but not when built in batch!)Slide 24Quad TreesFind in a Quad TreeSlide 27Building a Quad Tree (1/5)Building a Quad Tree (2/5)Building a Quad Tree (3/5)Building a Quad Tree (4/5)Building a Quad Tree (5/5)Quad Tree ExampleQuad Trees Can SuckSlide 352-D Range Querying in Quad Trees2-D Range Query in a Quad TreeSlide 38Delete ExampleNearest Neighbor SearchQuad Trees vs. k-D TreesTo DoCSE 326: Data Structures Part 10, continued Data StructuresPick a CardRandomized Data StructuresWhat’s the Difference?Treap Dictionary Data StructureTreap InsertTree + Heap… Why Bother?Treap DeleteTreap Delete, cont.Treap SummaryOther Randomized Data Structures & AlgorithmsRandomized Primality TestingRandomized Search AlgorithmsN-Queens ProblemRandom Walk – Complexity?Traveling SalesmanLatin SquaresFinal ReviewBe Sure to BringFinal Review: What you need to knowSlide 63Slide 64Slide 65Slide 66Slide 67Slide 68Slide 691CSE 326: Data StructuresPart 10Advanced Data StructuresHenry KautzAutumn Quarter 20022Outline•Multidimensional search trees–Range Queries–k-D Trees–Quad Trees•Randomized Data Structures & Algorithms–Treaps–Primality testing–Local search for NP-complete problems3Multi-D Search ADT•Dictionary operations–create–destroy–find–insert–delete–range queries•Each item has k keys for a k-dimensional search tree•Searches can be performed on one, some, or all the keys or on ranges of the keys9,13,64,25,78,21,94,48,42,55,24Applications of Multi-D Search•Astronomy (simulation of galaxies) - 3 dimensions•Protein folding in molecular biology - 3 dimensions•Lossy data compression - 4 to 64 dimensions•Image processing - 2 dimensions•Graphics - 2 or 3 dimensions•Animation - 3 to 4 dimensions•Geographical databases - 2 or 3 dimensions•Web searching - 200 or more dimensions5Range QueryA range query is a search in a dictionary in which the exact key may not be entirely specified.Range queries are the primary interface with multi-D data structures.6Range Query Examples:Two Dimensions•Search for items based on just one key•Search for items based on ranges for all keys•Search for items based on a function of several keys: e.g., a circular range query7xRange Querying in 1-DFind everything in the rectangle…8xRange Querying in 1-D with a BSTFind everything in the rectangle…9xy1-D Range Querying in 2-D10xy2-D Range Querying in 2-D11k-D Trees•Split on the next dimension at each succeeding level•If building in batch, choose the median along the current dimension at each level–guarantees logarithmic height and balanced tree•In general, add as in a BSTk-D tree nodedimensionleft rightkeys valueThe dimension thatthis node splits on12Find in a k-D Treefind(<x1,x2, …, xk>, root) finds the node which has the given set of keys in it or returns null if there is no such nodeNode find(keyVector keys, Node root) { int dim = root.dimension; if (root == NULL) return NULL; else if (root.keys == keys) return root; else if (keys[dim] < root.keys[dim]) return find(keys, root.left); else return find(keys, root.right);}runtime:13Find Examplefind(<3,6>)find(<0,10>)5,78,21,94,48,42,55,29,13,64,214xBuilding a 2-D Tree (1/4)y15xyBuilding a 2-D Tree (2/4)16xyBuilding a 2-D Tree (3/4)17xyBuilding a 2-D Tree (4/4)18k-D Treeacihmdefbjkglldkfhgecj i mb a19xy2-D Range Querying in 2-D TreesSearch every partition that intersects the rectangle. Check whether each node (including leaves) falls into the range.20Range Query in a 2-D Tree runtime: O(N)print_range(int xlow, xhigh, ylow, yhigh, Node root) {if (root == NULL) return;if ( xlow <= root.x && root.x <= xhigh &&ylow <= root.y && root.y <= yhigh ){print(root);if ((root.dim == “x” && xlow <= root.x ) ||(root.dim == “y” && ylow <= root.y ))print_range(root.left);if ((root.dim == “x” && root.x <= xhigh) ||(root.dim == “y” && root.y <= yhigh)print_range(root.right);}21Range Query in a k-D Tree runtime: O(N)print_range(int low[MAXD], high[MAXD], Node root) {if (root == NULL) return;inrange = true;for (i=0; i<MAXD;i++){if ( root.coord[i] < low[i] ) inrange = false; if ( high[i] < root.coord[i] ) inrange = false; }if (inrange) print(root);if ((low[root.dim] <= root.coord[root.dim] ) print_range(root.left);if (root.coord[root.dim] <= high[root.dim])print_range(root.right);}22xyOther Shapes for Range QueryingSearch every partition that intersects the shape (circle). Check whether each node (including leaves) falls into the shape.23k-D Trees Can Be Inefficient(but not when built in batch!)insert(<5,0>)insert(<6,9>)insert(<9,3>)insert(<6,5>)insert(<7,7>)insert(<8,6>)6,95,06,59,38,67,7suck factor:24k-D Trees Can Be Inefficient(but not when built in batch!)insert(<5,0>)insert(<6,9>)insert(<9,3>)insert(<6,5>)insert(<7,7>)insert(<8,6>)6,95,06,59,38,67,7suck factor: O(n)25Quad Trees•Split on all (two) dimensions at each level•Split key space into equal size partitions (quadrants)•Add a new node by adding to a leaf, and, if the leaf is already occupied, split until only one node per leafquad tree nodeQuadrants:0,1 1,10,0 1,0quadrant0,0 1,0 0,1 1,1keys valueCenterx yCenter:26Find in a Quad Treefind(<x, y>, root) finds the node which has the given pair of keys in it or returns quadrant where the point should be if there is no such nodeNode find(Key x, Key y, Node root) { if (root == NULL) return NULL; // Empty tree if (root.isLeaf()) return root; // Key may not actually be here int quad = getQuadrant(x, y, root); return find(x, y, root.quadrants[quad]);}runtime: O(depth)Compares against center; always makes the same choice on ties.27Find Exampleagbefdcgafedcbfind(<10,2>) (i.e., c)find(<5,6>) (i.e., d)28xBuilding a Quad Tree (1/5)y29xBuilding a Quad Tree (2/5)y30xBuilding a Quad Tree (3/5)y31xBuilding a Quad Tree (4/5)y32xBuilding a Quad Tree (5/5)y33Quad Tree Exampleagbefdcgafedcb34Quad Trees Can Suckbasuck factor:35Quad Trees Can