Comment on page

# 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.
- AlgorithmAverageWorst caseSpaceO(n)O(n)SearchO(log n)O(n)InsertO(log n)O(n)DeleteO(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.
- AlgorithmAverageWorst caseSpaceO(n)O(n)SearchO(log n)O(n)InsertO(log n)O(n)DeleteO(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.
- For: When is ‘nearest neighbour’ meaningful: A converse theorem and implications by Robert Durrant et al. (Bob's answer on Stack Exchange)

Last modified 2mo ago