CSE 326 Data Structures Part 10 Advanced Data Structures Henry Kautz Autumn Quarter 2002 1 Outline Multidimensional search trees Range Queries k D Trees Quad Trees Randomized Data Structures Algorithms Treaps Primality testing Local search for NP complete problems 2 Multi D Search ADT Dictionary operations create destroy find insert delete range queries 5 2 2 5 4 4 4 2 8 4 1 9 3 6 8 2 5 7 9 1 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 keys 3 Applications 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 dimensions 4 Range Query A 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 5 Range 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 query 6 Range Querying in 1 D Find everything in the rectangle x 7 Range Querying in 1 D with a BST Find everything in the rectangle x 8 1 D Range Querying in 2 D y 9 x 2 D Range Querying in 2 D y 10 x k 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 BST k D tree node keys value dimension left right The dimension that this node splits on 11 Find in a k D Tree find x1 x2 xk root finds the node which has the given set of keys in it or returns null if there is no such node Node 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 12 Find Example 5 2 find 3 6 find 0 10 2 5 4 4 8 4 1 9 4 2 8 2 3 6 5 7 9 1 13 Building a 2 D Tree 1 4 y 14 x Building a 2 D Tree 2 4 y 15 x Building a 2 D Tree 3 4 y 16 x Building a 2 D Tree 4 4 y 17 x k D Tree a b d c e e f j g k h i l g m f b h k a j d c l i m18 2 D Range Querying in 2 D Trees y x Search every partition that intersects the rectangle Check whether each node including leaves falls into the range 19 Range Query in a 2 D Tree 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 runtime O N 20 Range Query in a k D Tree 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 runtime O N 21 Other Shapes for Range Querying y x Search every partition that intersects the shape circle Check whether each node including leaves falls into the shape 22 k 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 5 0 6 9 9 3 6 5 7 7 suck factor 8 6 23 k 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 5 0 6 9 9 3 6 5 7 7 suck factor O n 8 6 24 Quad 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 leaf quadrant quad tree node 0 1 1 1 keys value 0 0 1 0 Center Center x y Quadrants 0 0 1 0 0 1 1 1 25 Find in a Quad Tree find 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 node Node find Key x Key y Node root if root NULL return NULL Empty tree if root isLeaf Compares against return root Key may not actually be here center always makes the same choice on ties int quad getQuadrant x y root return find x y root quadrants quad runtime O depth 26 Find Example find 10 2 i e c find 5 6 i e d a e c b a g d f d e f g b c 27 Building a Quad Tree 1 5 y 28 x Building a Quad Tree 2 5 y 29 x Building a Quad Tree 3 5 y 30 x Building a Quad Tree 4 5 y 31 x Building a Quad Tree 5 5 y 32 x Quad Tree Example a e c b a g d f d e f g b c 33 Quad Trees Can Suck a b suck factor 34 Quad Trees Can Suck a b suck factor O log 1 minimum distance between nodes 35 2 D Range Querying in Quad Trees y 36 x 2 D Range Query in a Quad Tree 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 xlow root x ylow root y print range root lower left if xlow root x root y yhigh print range root upper left if root x x high ylow root x print range root lower right if root x xhigh root y yhigh print range root upper right runtime O N 37 Find in a Quad Tree find 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 …