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.
Last updated
Was this helpful?
