# 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

### 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? by Kevin Beyer et al.

For: When is ‘nearest neighbour’ meaningful: A converse theorem and implications by Robert Durrant et al. (Bob's answer on Stack Exchange)

More discussions on Stackoverflow: Nearest neighbors in high-dimensional data?

Last updated