CODEWITHSUNDEEP
data-structuresfindbinary-treetreenode
Joshua Mak
Joshua Mak

Reputation: 127

Tree storing multiple values per node

I'm trying to find a way to create a binary tree where 3 doubles are stored in each node and another tree where 6 doubles are stored in each node.

The problem I'm having is figuring out a way to implement find and insert methods (no need for remove).

Basically, my tree is holding x, y, z values and when I call find, I want it to return the node which contains x, y, and z values closest to those I am trying to find.

How should I be approaching this problem and what are some ideas for a solution?

Thanks!

Upvotes: 4

Views: 5054

Answers (3)

amit
amit

Reputation: 178481

It seems that you are looking for k-d tree data structure, which also allows finding nearest neighbor to a given element.

Upvotes: 4

bluevector
bluevector

Reputation: 3493

 public class BinaryTreeNode<T>
 {
    public T Value {get; set;}

    public BinaryTreeNode<T> Left {get; set;}
    public BinaryTreeNode<T> Right {get; set;}

    public BinaryTreeNode<T> Seach(T forWhat)
    {
       if(Value == forWhat) return this;

       BinaryTreeNode<T> leftResult = Left.Search(forWhat);
       if(leftResult != null) return leftResult;

       BinaryTreeNode<T> rightResult = Right.Search(forWhat);
       if(rightResult != null) return rightResult;

       return null;
    }
 }

 BinaryTreeNode<Tuple<double, double, double>> threeDoublesTree = new BinaryTreeNode<Tuple<double, double, double>>();

 BinaryTreeNode<Tuple<double, double, double, double, double, double>> sixDoublesTree = new BinaryTreeNode<Tuple<double, double, double, double, double, double>>();

Upvotes: 1

Michał Szczygieł
Michał Szczygieł

Reputation: 399

Basically you store 1 value per node. You can treat those x, y, z values as 3D points. On the left of one node you putpoint closer to (0, 0, 0) and on the right you hold further ones. If you have structure like this you can search and insert data as you would in ordinary binary tree.

Upvotes: 0

Related Questions