Comment on page

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