public class Point2D implements Comparable<Point2D> { public Point2D(double x, double y) // construct the point (x, y) public double x() // x-coordinate public double y() // y-coordinate public double distanceTo(Point2D that) // Euclidean distance between two points public double distanceSquaredTo(Point2D that) // square of Euclidean distance between two points public int compareTo(Point2D that) // for use in an ordered symbol table public boolean equals(Object that) // does this point equal that object? public void draw() // draw to standard draw public String toString() // string representation }

public class RectHV { public RectHV(double xmin, double ymin, // construct the rectangle [xmin, xmax] x [ymin, ymax] double xmax, double ymax) // throw an IllegalArgumentException if (xmin > xmax) or (ymin > ymax) public double xmin() // minimum x-coordinate of rectangle public double ymin() // minimum y-coordinate of rectangle public double xmax() // maximum x-coordinate of rectangle public double ymax() // maximum y-coordinate of rectangle public boolean contains(Point2D p) // does this rectangle contain the point p (either inside or on boundary)? public boolean intersects(RectHV that) // does this rectangle intersect that rectangle (at one or more points)? public double distanceTo(Point2D p) // Euclidean distance from point p to closest point in rectangle public double distanceSquaredTo(Point2D p) // square of Euclidean distance from point p to closest point in rectangle public boolean equals(Object that) // does this rectangle equal that object? public void draw() // draw to standard draw public String toString() // string representation }

public class PointSET { public PointSET() // construct an empty set of points public boolean isEmpty() // is the set empty? public int size() // number of points in the set public void insert(Point2D p) // add the point to the set (if it is not already in the set) public boolean contains(Point2D p) // does the set contain point p? public void draw() // draw all points to standard draw public Iterable<Point2D> range(RectHV rect) // all points that are inside the rectangle (or on the boundary) public Point2D nearest(Point2D p) // a nearest neighbor in the set to point p; null if the set is empty public static void main(String[] args) // unit testing of the methods (optional) }

insert (0.7, 0.2) insert (0.5, 0.4) insert (0.2, 0.3) insert (0.4, 0.7) insert (0.9, 0.6) --> insert (0.8, 0.1) --> -->

private class Node { private Point2D p; // the point private Value value; // the symbol table maps the point to this value private RectHV rect; // the axis-aligned rectangle corresponding to this node private Node lb; // the left/bottom subtree private Node rt; // the right/top subtree }

private Value get(Node x, Key key) { if (x == null) return null; int cmp = key.compareTo(x.key); if (cmp < 0) return get(x.left, key); else if (cmp > 0) return get(x.right, key); else return x.value } private Value overlyComplicatedGet(Node x, Key key) { if (x == null) return null; int cmp = key.compareTo(x.key); if (cmp < 0) { if (x.left == null) return null; else return overlyComplicatedGet(x.left, key); } else if (cmp > 0) { if (x.right == null) return null; else return overlyComplicatedGet(x.right, key); } else return x.value }

Composing and testing a complex data structure from scratch, again. 1

## Learning Goals

Compose algorithms via iterative improvement.

Encapsulate complex behavior beneath a simple interface.

## Table of contents

## Getting the Assignment

Before you begin the assignment, you might find the following visual resources helpful:

If you end up incorporating any resources into your own code, be sure to cite them!

Read over Point and begin implementing NaivePointSet per the spec.

## PointSet API

## NaivePointSet

NaivePointSet will only be tested for correctness, not efficiency.

## KDTreePointSet

## Data Structures and Algorithms - Fall 2015

- Gain an appreciation for the power of binary trees and the types of operations a binary tree can support.
- Know how to code a particular type of binary tree called a kD-tree.
- Gain experience developing code from a less formal explanation of a data structure and its operations than full-fledged pseudo-code.

## Getting Started

First download and decompress one of the starter files:

## The bst/ folder

This folder contains the bst.h/c files and the files needed for the bst/main tester program.

- bst.h/c : The binary search tree files.
- drawtree.h/c : Tree drawing functions (uses turtle graphics).
- dynarray.h/c : Dynamic array (used for getting output from the range search function).
- main.c : The main test program.
- turtle.h/c : The turtle graphics library.

## The kdtree/ folder

- dynarray.h/c : Dynamic array (used for getting output from the range search functions).
- helpers.h/c : Contains a few helper structures and functions including the point_t and bbox_t types and functions for computing the distances between points.
- kdtree.h/c : The kD-tree implementation.
- main.c : The main tester program that generates a "screenshot" of the game.

## COMING SOON: The rangefighter/ folder

## Part 1: Range Finding in Binary Search Trees

## Building a BST

- Presort the items array to obtain sorted-items .
- Select the median ( sorted-items[n/2] ) and make it the value of the root node.
- Recursively create the left subtree from sorted-items[0:n/2-1] .
- Recursively create the right subtree from sorted-items[n/2+1:n] .

## Task 1: Implement a Range Search BST

void bst_build(bst_t *tree, int array[], size_t length);

IMPORTANT : This function should run in O ( n log n ) time.

bool bst_find(bst_t *tree, int x);

Returns true if the value x is contained in the tree, false otherwise.

IMPORTANT : This function should run in O (log n ) time.

void bst_range_search(bst_t *tree, int range_min, int range_max, dynarray_t *output_array);

And of course, the usual memory management functions:

Initializes an empty binary search tree. (We have provided this for you.)

Frees any memory (i.e. the nodes) for this binary search tree.

The ./main test program we have included should output the following to the console when run:

Furthermore, it should produce a turtle graphics image named output.bmp that looks like this:

## Part 2: kD-Trees

## Range searching a kD-tree

## Motivation: Range Fighter

Here is a screenshot of the game:

## Task 2: kD-Tree Implementation

void kdtree_init(kdtree_t *tree)

Initializes an empty kD-tree. (We have provided this for you.)

void kdtree_free(kdtree_t *tree)

void kdtree_build(kdtree_t *tree debris_t array[], size_t length)

void kdtree_box_range_search(kdtree_t *tree, bbox_t range, dynarray_t *debris_in_range)

Adds all active debris that fall within the range to the dynamic array debris_in_range .

void kdtree_circ_range_search(kdtree_t *tree, point_t p, float radius, dynarray_t *debris_in_range);

## Suggested Progression

Next, implement the box range searching. Once this is working you should see this:

## Final Submission

DUE DATE: Friday, December 11, 2015 at 23:59 EST (11:59pm)

## IMAGES

## VIDEO

## COMMENTS

My solution to week 5 programming assignment: Kd-Trees - GitHub - maximkir/coursera-algorithms-part1-kdtree: My solution to week 5 programming assignment:

algorithms-princeton-coursera/Codes of Programming Assignments/part1/pa5-kdtree/KdTree.java · Footer.

Write a data type to represent a set of points in the unit square (all points have x- and y-coordinates between 0 and 1) using a 2d-tree to support

Programming Assignment 5 Checklist: Kd-Trees · Write isEmpty() and size(). · Write a simplified version of put() which does everything except set up the RectHV

Programming Assignment 5: Kd-Trees (Part II). Write a data type KdTree with the same public methods as PointSET to represent a set of points in the unit

Programming Assignment 2: Wrapped k-d Trees. Handed out: Tue, Apr 6. Due: Wed, Apr 21, 11pm. (Submission via Gradescope.) Overview: In this assignment you

k-d Tree · Learning Goals · Table of contents · Overview · Getting the Assignment · Point · PointSet API · Submission.

in the same kd-tree as points in four-dimensional space. ... to complete the assignment, I've broken the program down into a series of five.

Question: Programming Assignment 5: Kd-Trees Create a symbol table data type whose keys are two-dimensional points. Use a 2d-tree to support efficient range

We are giving you some information on the kD-tree data structure (which you will be coding), but not everything you will need to know to

In this assignment, you will implement a special data structure called a kd-tree (short for “k-dimensional tree”) that efficiently supports