Algorithm-Part-I Assignment 5:Kd-Trees

编程作业5:Kd-Trees

编写一个数据结构用于描绘单位正方形内的一系列点(所有的点都有x坐标和y坐标的值都在0-1之间),通过2d-tree来实现高效的范围查找(range search)(找出所有在查询的长方形区域中的点),同时实现最佳相邻点查询(nearest-neighbor search)(找出对于查询点距离最短的点)。2d-tree有相当多的应用,电脑动画天体物体分类,加速神经网络,数据挖掘,图像修复。

几何图元 Geometric primitives 首先,使用以下的几何图元来表示平面上的点和轴对称的长方形。

不要更改这些数据结构。

暴力算法实现 Brute-force implementation 编写一个不可修改的数据结构PointSET.java用于描绘单位正方形内一系列的点。通过红黑树(red–black BST)实现下列API:


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) 
}

实现要求 Implementation requirements 你必须使用SET或者java.util.TreeSet;不要自己实现红黑树。

边缘情况 Corner cases 如果任何参数为空,抛出`java.lang.IllegalArgumentException 异常。

性能要求 Performance requirements 你的实现必须保证在最坏情况下,insert()contains()方法用时正比与点集合中所有点的数量的对数;保证nearest()range()方法用时正比与点集合中点的数量。

2d-tree实现 2d-tree implementation 编写一个可修改的数据结构KdTree.java,使用2d-tree实现相同二API(将PointSETKdTree替代)。2d-tree是使用二为键值(keys)二叉查找树(BST),其思想就是建立一个指向节点的BST,以严格的交替顺序将点的x坐标值和y坐标值作为键值(keys).

2d-tree相对于BST来说主要的优势在于2d-tree能够高效的实现范围查找和最近相邻查找。每一个结点对应着一个单元长方形中轴对称矩形,该矩形包含了所有其子树中的点。根部对应着单元矩形;根部左右两个子节点对应着根部点x坐标分开的两个矩形,这样重复下去。

客户端 Clients 你可能需要以下交互性的客户端程序用于检测和调试你的代码。

运行时间和内存使用的分析(可选,不计入成绩) Analysis of running time and memory usage (optional and not graded)

提交的作业 Submission 只需要提交文件PointSET.javaKdTree.java。我们提供algs4.jar。你不得调用java.lang,java.utilalgs4.jar之外的库函数。

This assignment was developed by Kevin Wayne.

comments powered by Disqus