首页 >
> 详细

Lab4: 2D-Tree

In this assignment, you will implement a special data structure called a 2D-Tree (short for “2-dimensional

tree”) that efficiently supports to search “what value in the container is X most similar to?”.

1. Story

At a high level, a kd-tree(short for “k-dimensional tree”) is a generalization of a binary search tree that

stores points in k-dimensional space. That is, you could use a kd-tree to store a collection of points in the

Cartesian plane, in three-dimensional space, etc. You could also use a kd-tree to store biometric data, for

example, by representing the data as an ordered tuple, perhaps (height, weight, blood pressure,

cholesterol). However, a kd-tree cannot be used to store collections of other data types, such as strings.

Also note that while it's possible to build a kd-tree to hold data of any dimension, all of the data stored in

a kd-tree must have the same dimension. That is, you can't store points in two-dimensional space in the

same kd-tree as points in four-dimensional space.

It's easiest to understand how a kd-tree works by seeing an example. Below is a kd-tree that stores points

in three-dimensional space:

Notice that in each level of the kd-tree, a certain component of each node has been bolded. If we zeroindex

the components (i.e. the first component is component zero, the second component is component

one, etc.), in level n of the tree, the (n % 3)-th component of each node is shown in bold. The reason that

these values are bolded is because each node acts like a binary search tree node that discriminates only

along the bolded component. For example, the first component of every node in the left subtree is less

than the first component of the root of the tree, while the first component of every node in the right subtree

has a first component at least as a large as the root node's. Similarly, consider the kd-tree's left subtree.

The root of this tree has the value (2, 3, 7), with the three in bold. If you look at all the nodes in its left

subtree, you'll notice that the second component has a value strictly less than three. Similarly, in the right

subtree the second component of each node is at least three. This trend continues throughout the tree.

Given how kd-trees store their data, we can efficiently query whether a given point is stored in a kd-tree

as follows. Given a point P, start at the root of the tree. If the root node is P, return the root node. If the

first component of P is strictly less than the first component of the root node, then look for P in the left

subtree, this time comparing the second component of P. Otherwise, then the first component of P is at

least as large as the first component of the root node, and we descend into the right subtree and next time

compare the second component of P. We continue this process, cycling through which component is

considered at each step, until we fall off the tree or find the node in question. Inserting into a kd-tree is

similarly analogous to inserting into a regular BST, except that each level only considers one part of the

point.

2. Lab Requirement

You should implement the TreeNode and BinaryDimonTree(2D-Tree) classes.

TreeNode is a class which is used to store the binary dimension data. You should provide the following

functions (at least):

1. int getX(): return x(the first value in the tree node);

2. int getY(): return y(the second value in the tree node);

BinaryDimonTree is a class for the Tree which supports the following functions (at least):

1. BinaryDimonTree(): the construct function of class BDT;

2. istream &operator>>(istream &in, BinaryDimonTree &tree): input a 2D-Tree and the rule is

given below;

3. TreeNode* find_nearest_node(int x, int y): search the 2D-Tree and find the point whose

distance is smallest to the Point(x, y), and output the result to the console;

p.s. the distance between Point(x1, y1) and Point(x2, y2) is equal to [(x1-x2)^2 + (y1-

y2)^2]^(1/2);

p.s. If there are two points that have the same distance to the Point(x, y), then you are supposed

to choose the point whose x is smaller. If their x’s are also the same, then choose the point

whose y is smaller;

4. ~BinaryDimonTree(): the deconstruct function which is used to reclaim all the data in the 2DTree,

and you should explain your implementation to us when your lab is examined.

You must implement the Tree completely by yourself. And the names of the classes and their functions

must be same with the above.

We have provided the main function and the test cases, you should just run the main.cpp and check if you

can pass through all the test cases.

3. Guidance

The algorithm to find the nearest node in the 2D-Tree:

Let the test point be (a0, a1).

Maintain a global best estimate of the nearest neighbor, called 'guess.'

Maintain a global value of the distance to that neighbor, called 'bestDist'

Set 'guess' to NULL.

Set 'bestDist' to infinity.

Starting at the root, execute the following procedure:

if curr == NULL

return

/*

* If the current location is better than the best known location,

* update the best known location.

*/

if distance(curr, guess) < bestDist

bestDist = distance(curr, guess)

guess = curr

/*

* Recursively search the half of the tree that contains the test point.

* i means the dimension index which is used to discriminate in the current

level,

* for example: the i = 0 when curr is the root

*/

if ai < curri

recursively search the left subtree on the next axis

else

recursively search the right subtree on the next axis

/*

* If the vertical distance between the points is smaller than the best

distance,

* look on the other side of the plane by examining the other subtree.

*/

if |curri – ai| < bestDist

recursively search the other subtree on the next axis

4. Test

Input & Output Format:

The test file is divided into two parts.

The first part is for constructing a 2D-tree.

The first line contains an integer M which represents the number of nodes in the tree.

Next, there are M lines following, each contains two integers divided by a space. The two integers at the

same line represent the values on two dimensions respectively for the corresponding node.

The second part contains the test cases for find_nearest_node method.

The first line contains an integer N which represents the number of test cases.

Next, there are M lines following, each contains four integers divided by spaces. In each line, the first two

integers represent the node to search and the other two integers are correct answer of the search.

The code for the second part has been already completed in main.cpp. Please refer to the rules and

construct your own 2D-tree.

Coding format：

1. Please add your own functions and variables in file Tree.h and do not change or delete those

functions with tag /* DO NOT CHANGE */. Do not include other headers or libraries.

2. Please write your code in Tree.cpp and do not include other headers or libraries.

3. Do not modify main.cpp

Submission：

1. Please compress your source code into a 7z file and rename it to lab4.7z.

2. Only Tree.h and Tree.cpp are supposed to be submitted.

3. Upload it to canvas

Hint：

1. 1000 <= M <= 5000, 30000 <= N <= 100000。

2. In real-world cases, search time is more important, so you are supposed to reduce the execution

time of find_nearest_node.

5. Example

Testcase 1:

In this case, M=7 and N=1. You can construct a 2D tree with 7 nodes like this:

We have only one testcase, that is to find the point whose distance is smallest to Point(3,6).

As both Point(3,5) and Point(3,7) have the same distance to Point(3,6), we choose

Point(3,5) as it has smaller y.

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp2

- Cs2461-10实验程序代做、代写java，C/C++，Python编程设 2021-03-02
- 代写program程序语言、代做python，C++课程程序、代写java编 2021-03-02
- Programming课程代做、代写c++程序语言、Algorithms编程 2021-03-02
- 代写csc1-Ua程序、代做java编程设计、Java实验编程代做 代做留学 2021-03-02
- 代做program编程语言、代写python程序、代做python设计编程 2021-03-02
- 代写data编程设计、代做python语言程序、Python课程编程代写 代 2021-03-02
- Cse 13S程序实验代做、代写c++编程、C/C++程序语言调试 代写留学 2021-03-02
- Mat136h5编程代做、C/C++程序调试、Python，Java编程设计 2021-03-01
- 代写ee425x实验编程、代做python，C++，Java程序设计 帮做c 2021-03-01
- Cscc11程序课程代做、代写python程序设计、Python编程调试 代 2021-03-01
- 代写program编程、Python语言程序调试、Python编程设计代写 2021-03-01
- 代做r语言编程|代做database|代做留学生p... 2021-03-01
- Data Structures代写、代做r编程课程、代做r程序实验 帮做ha 2021-03-01
- 代做data留学生编程、C++，Python语言代写、Java程序代做 代写 2021-03-01
- 代写aps 105编程实验、C/C++程序语言代做 代写r语言程序|代写py 2021-03-01
- Fre6831 Computational Finance 2021-02-28
- Sta141b Assignment 5 Interactive Visu... 2021-02-28
- Eecs2011a-F20 2021-02-28
- Comp-251 Final Asssessment 2021-02-28
- 代写cs1027课程程序、代做java编程语言、代写java留学生编程帮做h 2021-02-28