kdtree

README

K-D Tree

An implementation of KD-Trees written in Go, by Rishit Chaudhary.

Supported Operations

1. Efficiently find the nearest neighbor for a given node
2. Find the node with the minimum value in a particular dimension
3. Add a node to the KD-Tree
4. Delete a node from the KD-Tree
5. Stringify the KD-Tree to visualize it
6. Encode the tree into bytes
7. Decode the tree from bytes

Note: I have used FlatBuffers to encode and decode the KD-Tree.

Tests

The tests cover all API usages and are a great place to start to understand how to use them.

References

I've listed below all the references I've used to learn about KD-Trees working on this project.

1. KD-Tree Nearest Neighbor Data Structure by Stable Sort
   1. Linked Java Implementation
2. Good KD Tree Visualization Fall 2019
   1. Alternate Link
3. Good KD Tree Visualization Spring 2019
4. K-D Tree: build and search for the nearest neighbor by Algokodabra
5. K-d Trees - Computerphile
6. Advanced Data Structures: K-D Trees by Niema Moshiri
7. Advanced Data Structures: KDT Grid Representation by Niema Moshiri
8. Advanced Data Structures: KDT Insertion Order and Balance by Niema Moshiri
9. Node Deletion in KD-Tree
   1. The last example in this video lecture has an error. I've described and corrected this in my test case.

Documentation

Index

• Variables
• func NewKDNode[T Comparable[T]](value T) *kdNode[T]
• type Comparable
• type KDTree
  • func NewKDTreeFromBytes[T Comparable[T]](encodedBytes []byte, decodeItemFunc func([]byte) T) *KDTree[T]
  • func NewKDTreeWithValues[T Comparable[T]](d int, vs []T) *KDTree[T]
  • func (t *KDTree[T]) Add(value T) bool
  • func (t *KDTree[T]) Delete(value T) bool
  • func (t *KDTree[T]) Encode() []byte
  • func (t *KDTree[T]) FindMin(targetDimension int) (T, bool)
  • func (t *KDTree[T]) NearestNeighbor(value T) (T, bool)
  • func (t *KDTree[T]) Query(getRelativePosition func(T, int) RelativePosition) []T
  • func (t *KDTree[T]) String() string
  • func (t *KDTree[T]) Values() []T
• type Relation
• type RelativePosition

Variables

var ErrTreeNotSetup = fmt.Errorf("tree is not setup, make sure you create the tree using NewTree")

Functions

func NewKDNode

func NewKDNode[T Comparable[T]](value T) *kdNode[T]

Types

type Comparable

type Comparable[T any] interface {
	fmt.Stringer
	Order(rhs T, dim int) Relation
	Dist(rhs T) int
	DistDim(rhs T, dim int) int
	Encode() []byte
}

type KDTree

type KDTree[T Comparable[T]] struct {
	// contains filtered or unexported fields
}

func NewKDTreeFromBytes

func NewKDTreeFromBytes[T Comparable[T]](encodedBytes []byte, decodeItemFunc func([]byte) T) *KDTree[T]

func NewKDTreeWithValues

func NewKDTreeWithValues[T Comparable[T]](d int, vs []T) *KDTree[T]

func (*KDTree[T]) Add

func (t *KDTree[T]) Add(value T) bool

func (*KDTree[T]) Delete

func (t *KDTree[T]) Delete(value T) bool

func (*KDTree[T]) Encode

func (t *KDTree[T]) Encode() []byte

func (*KDTree[T]) FindMin

func (t *KDTree[T]) FindMin(targetDimension int) (T, bool)

func (*KDTree[T]) NearestNeighbor

func (t *KDTree[T]) NearestNeighbor(value T) (T, bool)

func (*KDTree[T]) Query

func (t *KDTree[T]) Query(getRelativePosition func(T, int) RelativePosition) []T

func (*KDTree[T]) String

func (t *KDTree[T]) String() string

func (*KDTree[T]) Values

func (t *KDTree[T]) Values() []T

type Relation

type Relation int

const (
	Lesser Relation = iota
	Equal
	Greater
)

type RelativePosition

type RelativePosition int

const (
	BeforeRange RelativePosition = iota
	InRange
	AfterRange
)