# K-D Tree

### Binary Search Tree (BST)

#### Tree

* In graph theory, a **tree** is a connected **acyclic undirected graph**, and a **forest** is a disjoint union of trees.
* In computer science, a **tree** is a widely used abstract data type (ADT) that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes. (This "linked" relation can be implemented by a linked list or an array with certain indexing rules.)

#### Binary Tree

* A binary tree is a tree data structure in which each node has at most two children. (This is the only constraint.)

**Binary Search Tree (BST)**

* In computer science, a binary search tree (BST), also called an **ordered** or **sorted** binary tree, is a rooted binary tree data structure whose internal nodes each store a key greater than all the keys in the node's left subtree and less than those in its right subtree. 
* Used for sorting: the construction step takes O(n log n) time, then the sorted list can be obtained by traversing all nodes in O(log n) time. 
* | Algorithm |   | Average  | Worst case |
  | --------- | - | -------- | ---------- |
  | Space     |   | O(n)     | O(n)       |
  | Search    |   | O(log n) | O(n)       |
  | Insert    |   | O(log n) | O(n)       |
  | Delete    |   | O(log n) | O(n)       |

### K-D Tree

* In computer science, a k-d tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space
* k-d trees are a special case of binary space partitioning trees.
* | Algorithm |   | Average  | Worst case |
  | --------- | - | -------- | ---------- |
  | Space     |   | O(n)     | O(n)       |
  | Search    |   | O(log n) | O(n)       |
  | Insert    |   | O(log n) | O(n)       |
  | Delete    |   | O(log n) | O(n)       |

### Comparison of various data structures

![](/files/-Mglybe2N54822Dvyf1p)

### Discussions on K-D Tree

* It is said that Euclidean distance is a bad metric in high dimensional space.
* There are debates on using K-D Tree for high dimensional data.
  * Against: [When Is "Nearest Neighbor" Meaningful?](https://link.springer.com/content/pdf/10.1007%2F3-540-49257-7_15.pdf) by Kevin Beyer et al.
  * For: [When is ‘nearest neighbour’ meaningful: A converse theorem and implications](https://www.sciencedirect.com/science/article/pii/S0885064X09000260) by Robert Durrant et al. ([Bob's answer on Stack Exchange](https://stats.stackexchange.com/a/10976))
* More discussions on [Stackoverflow: Nearest neighbors in high-dimensional data?](https://stackoverflow.com/questions/5751114/nearest-neighbors-in-high-dimensional-data)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wiki.hanzheteng.com/algorithm/slam/k-d-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.