data structurestrees
Most BST examples show a sample of a BST with unique values; mainly
to demonstrate the order of values. e.g. values in the left subtree are smaller than the root, and values in the right subtree are larger.
Is this because BSTs are normally just used to represents SETs ?
If I insert an element say 4 which already exists in the BST, what should happen ?
e.g. In my case, 4 is associated with a payload. Does it mean I override the existing node's payload.
There are some self-balanced trees such as Red-Black tree and AVL tree. For more information see:
Ok, so here's what I came up with. This contains Java, better get yourself some coffee. The Irish one. (for the same reason)
In a sense, a tree is self similar. After all, a tree is a graph. Each node knows a certain number of other nodes.
Speaking of Nodes:
import java.util.HashMap;
public class Node <Child extends ICanBeMergedWith<? super Child> & ICanBecomeImmutable> implements ICanBecomeImmutable, ICanBeMergedWith<Node<Child>>
{
private HashMap<Child, Child> children;
private String name;
private boolean mutable;
public Node(String name)
{
this.name = name;
children = new HashMap<Child,Child>();
mutable = true;
}
public boolean add(Child child)
{
if (!mutable)
{
return false;
}
if(!children.containsKey(child))
{
children.put(child, child);
}
else
{
children.get(child).merge(child);
}
return true;
}
@Override
public void merge(Node<Child> other)
{
if (!mutable || !equals(other))
{
return;
}
for(Child child : other.children.values())
{
add(child);
}
}
@Override
public String toString()
{
String s = name + ":";
for (Child child : children.values())
{
s += System.getProperty("line.separator") + child.toString().replaceAll("(?m)^", "\t");
}
return s;
}
@Override
public void petrify()
{
mutable = false;
for (Child child : children.values())
{
child.petrify();
}
}
@Override
public int hashCode()
{
return name.hashCode();
}
@Override
public boolean equals(Object obj)
{
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
if (name == null)
if (((Node<Child>) obj).name != null)
return false;
return name.equals(((Node<Child>) obj).name);
}
}
Sorry for serving that thing up front, but there's no way around it.
Javaland you have to do some shenanigans with equals() and hashCode(). I just copied that together from the web. You have to come up with your own implementation depending on what the actual implementations of X, Y etc. do in your use case. I my case they all just have a name. If two nodes of the same type have the same name, they are equal. HashMap<Child, Child> children;, which is the list of other known Nodes I was talking about above. Admittedly, a HashSet<Child> could also work, for all we need is some data structure that keeps its children unique, but it's kind of hard to get something back out of a HashSet, which is necessary to add more things to it. Basically speaking, HashMap<Child, Child> is used like a HashSet<Child>, but is more convenient (and faster).add(Child child) method. If the child is not in the list already, add it as is. If the child is in the list already, that means that this exact child is not necessarily already in the list, but some child that is considered equal, so the incoming child received as parameter is merged into the one that's in the list already. Think of this like placing two folders together that have the name: that doesn't mean they have the same sub folders. To do this, I had to create ICanBeMergedWith<T>, which you can find below, because I am unable to integrate big code blocks into list (editors?!)NullObject instance per class. So all the mutating method calls could be either delegated to this within the class or to the NullObject. It turns out that static and generic types do not go well together. I was no able to create a generic inner NullObject singleton. As can be seen above, I went for a simple flag variable that prevents access to the internal data structure. I created ICanBecomeImmutable for that.Node<Child> and Child. I think this would all be a lot easier if there were self types (that is, being able to type something to whatever class this is) But for a lack thereof and my lack of skills, this is the solution I came up with. You can explicitly type things, which soon becomes as ugly with Node<Node<Node<V>>>. Or maybe I'm just totally wrong here.So much for Node. The actual classes a a tad bit simpler, here they are:
V:
public class V extends Node<W>
{
public V(String name)
{
super(name);
}
}
W:
public class W extends Node<X>
{
public W(String name)
{
super(name);
}
}
X:
public class X extends Node<Y>
{
public X(String name)
{
super(name);
}
}
Y:
public class Y extends Node<Z>
{
public Y(String name)
{
super(name);
}
}
Z:
public class Z implements ICanBecomeImmutable, ICanBeMergedWith <Z>
{
@Override
public String toString()
{
return "Z";
}
@Override
public void petrify()
{
// nothing to do
}
@Override
public void merge(Z other)
{
// whatever
}
}
Only Z is a little different, because it can be known to Node but is not a Node itself. Two empty methods aren't too bad I guess.
Last but not least, the above mentioned interfaces:
interface for merging:
public interface ICanBeMergedWith<T>
{
void merge(T other);
}
interface for making object immutable:
public interface ICanBecomeImmutable
{
void petrify();
}
I created a little test application:
public class Main
{
public static void main(String[] args)
{
// building main tree
System.out.println("========= main tree ========= ");
V v1 = new V("v1");
W w1 = new W("w1");
W w2 = new W("w2");
X x1 = new X("x1");
X x2 = new X("x2");
Y y1 = new Y("y1");
Y y2 = new Y("y2");
v1.add(w1);
// v1.petrify();
v1.add(w2);
w1.add(x1);
w2.add(x2);
x1.add(y1);
// v1.petrify();
x2.add(y2);
y1.add(new Z());
y1.add(new Z());
y1.add(new Z());
// v1.petrify();
y1.add(new Z());
y2.add(new Z());
y2.add(new Z());
System.out.println(v1);
System.out.println("========= sub tree ========= ");
// building second tree
V v2 = new V("v1"); // !!! same name as v1 object, should be merged to one
W w3 = new W("w2"); // !!! same name as w2 object, should be merged to one
X x3 = new X("x2"); // !!! same name as x2 object, should be merged to one
X x4 = new X("x4");
Y y3 = new Y("y2"); // !!! same name as y2 object, should be merged to one
v2.add(w3);
w3.add(x3);
w3.add(x4);
x3.add(y3);
y3.add(new Z());
y3.add(new Z());
y3.add(new Z());
y3.add(new Z());
y3.add(new Z());
System.out.println(v2);
System.out.println("========= merge tree ========= ");
v1.merge(v2);
System.out.println(v1);
}
}
There are a few v1.petrify(); scattered around to stop further expansion of the tree.
The output is as follows for me:
========= main tree =========
v1:
w1:
x1:
y1:
Z
Z
Z
Z
w2:
x2:
y2:
Z
Z
========= sub tree =========
v1:
w2:
x2:
y2:
Z
Z
Z
Z
Z
x4:
========= merge tree =========
v1:
w1:
x1:
y1:
Z
Z
Z
Z
w2:
x2:
y2:
Z
Z
Z
Z
Z
Z
Z
x4:
This is where my partial answer ends, because I do not know how the DataChunks look like. What you have to do now is to transform the data into a tree, then merge the tree with the main tree. As far as I could tell. Every DataChunk has to start at some V Node, because it would otherwise be impossible to which parent Node this subtree belongs to. But even if it wasn't, you have the ability now to add and merge Nodes at every level of the tree. When the stream is finished, call petrify() on the rootV Node to prevent any further mutation of the data.
Also, do some more testing.
Something should probably be final. It looks more professional if something is final. No seriously, this is to show that not every detail was thought through entirely. This is to prove that from the types and the stated requirements, this can be possible. Nothing more nothing less.
disclaimer: I don't have much experience with generics so far. Chances are this is the worst horrible nonsense ever. I was about to deem this impossible, when I gave it a last try, typed "super" to create and upper bound and all the red lines disappeared. Magic!
Also: yeah WTF, how dare I post an implementation on programmers.SE? The thing is: you can do stuff on the whiteboard for sure, but there ain't no result without implementation. And what is supported by the language you choose in the end makes a huge difference on the effort it takes to do the actual implementation. You cannot hit "compile" and the compiler is always right. That's why I went for a concrete implementation.
Best Answer
The classic examples of the BST demonstrate a set where there is one entry for a given value in the structure. An example of this is the TreeSet in Java (yes, thats a red-black tree behind the scenes - but its a tree and a set).
However, there's nothing saying that there can't be additional values stored at the location indicated by the value. Once you decide to do this, it becomes an associative array (sometimes called a map). Again, going to Java for the example, there is the TreeMap.
An example of this could be:
The structure of this would look like:
A balanced binary tree (the red-black part of that structure) with a left child and a right child. You access it by looking for the value 4, or 16, or 25 and get back the associated data stored in that node.
One aspect of the tree is that you can't have two different values with the same index. There is no way with this design to insert David at age 16 also. However, one could put another data structure such as a list instead of the
Stringat the node and allow you to store multiple items in that list.But the (binary) tree, by itself, is a set that requires the indexes into it to be comparable (orderable) and that it will contain only distinct values (no duplicates).
Realize that everyone is free to implement their own trees and sets and how they deal with the addition of another item with the same key. With a TreeSet, if you add an already existing value, the add function returns false and leaves the set unchanged. With a TreeMap, if you call put with a key that already exists, it replaces the old value and returns the replaced value (null if nothing was there).
What should happen is whatever you need to have happen for that implementation. There's no inscribed tablet that all the computer scientists signed that dictates how any abstract data structure should behave. They behave as they should and when they need to behave other ways, document it and do it that way.