09/08/2022

## What is a kd tree used for?

K Dimensional tree (or k-d tree) is a tree data structure that is used to represent points in a k-dimensional space. It is used for various applications like nearest point (in k-dimensional space), efficient storage of spatial data, range search etc.

## What is 2d tree?

A 2d-tree is a generalization of a BST to two-dimensional keys. The idea is to build a BST with points in the nodes, using the x- and y-coordinates of the points as keys in strictly alternating sequence, starting with the x-coordinates.

Are kd trees balanced?

Kd tree is not always balanced. AVL and Red-Black will not work with K-D Trees, you will have either construct some balanced variant such as K-D-B-tree or use other balancing techniques.

### Who invented kd tree?

Jon Louis Bentley

k-d tree
Invented 1975
Invented by Jon Louis Bentley
Time complexity in big O notation
Algorithm Average Worst case Space Search Insert Delete

### Does uber use quad tree?

Uber uses Google S2 library (which uses a quadtree data structure). This library divides the map data into tiny cells (for example 2km) and gives the unique ID to each cell. This is a fairly easy way to spread data in a distributed system and store it easily.