keywords: Algorithms, Binary Tree, Quadtree and Octree


Binary tree




Binary Tree Applications
  • Binary Search Tree - Used in many search applications where data is constantly entering/leaving, such as the map and set objects in many languages’ libraries.
  • Binary Space Partition - Used in almost every 3D video game to determine what objects need to be rendered.
  • Binary Tries - Used in almost every high-bandwidth router for storing router-tables.
  • Hash Trees - used in p2p programs and specialized image-signatures in which a hash needs to be verified, but the whole file is not available.
  • Heaps - Used in implementing efficient priority-queues, which in turn are used for scheduling processes in many operating systems, Quality-of-Service in routers, and A* (path-finding algorithm used in AI applications, including robotics and video games). Also used in heap-sort.
  • Huffman Coding Tree (Chip Uni) - used in compression algorithms, such as those used by the .jpeg and .mp3 file-formats.
  • GGM Trees - Used in cryptographic applications to generate a tree of pseudo-random numbers.
  • Syntax Tree - Constructed by compilers and (implicitly) calculators to parse expressions.
  • Treap - Randomized data structure used in wireless networking and memory allocation.
  • T-tree - Though most databases use some form of B-tree to store data on the drive, databases which keep all (most) their data in memory often use T-trees to do so.

What are the applications of binary trees?

Quadtree Applications
  • Image processing
  • Mesh generation
  • Spatial indexing, point location queries, and range queries
  • Efficient collision detection in two dimensions
  • View frustum culling of terrain data
  • Storing sparse data, such as a formatting information for a spreadsheet or for some matrix calculations
  • Solution of multidimensional fields (computational fluid dynamics, electromagnetism)
  • Conway’s Game of Life simulation program.
  • State estimation
  • Quadtrees are also used in the area of fractal image analysis
  • Maximum disjoint sets
Octree Applications
  • Level of detail rendering in 3D computer graphics
  • Spatial indexing
  • Nearest neighbor search
  • Efficient collision detection in three dimensions
  • View frustum culling
  • Fast multipole method
  • Unstructured grid
  • Finite element analysis
  • Sparse voxel octree
  • State estimation
  • Set estimation


KD Tree

Fast KDTree for Unity, with thread-safe querying.

There will always be people who'll hurt you, so you need to continue trusting, just be careful. ― Gabriel Garcí­a Márquez