K-D 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.)

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)

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)

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 1 year ago