CODEWITHSUNDEEP
javatreebinary-tree
Raju Kumar
Raju Kumar

Reputation: 1265

Inserting into binary tree (without order)

How would you implement a tree without ordering it?

Upvotes: 1

Views: 2527

Answers (6)

Marsellus Wallace
Marsellus Wallace

Reputation: 18611

If you want to master this kind of problem you should take a look at HeapSort.

Assuming that your input is stored in an inputArray[] input;, what's the index of the first node that is not a leaf??

input.length / 2 - 1  =>  7 / 2 - 1  =>  2  =>  input[2] is 2

Now, given any node in the array by its index, what's the position of its children?

leftChild = parentIndex * 2 + 1;
rightChild = parentIndex * 2 + 2;
EG: Children of node at index 2 (value 2): left=5 (value 6), right=6(value 8)
NOTE: Watch for ArrayIndexOutOfBound that means that children are missing

An easy way to design an algorithm is to create an array of Node (something with an int value and a Node reference) and then add to each non-leaf node its children. You can probably think at better algorithms that require less extra memory or that use recursion as an additional homework!

Upvotes: 0

vextorspace
vextorspace

Reputation: 934

You could also have an object that is ordered by an index which you put in a normal binary tree

class indexedObject implements Comparable{
    public Int index;
    public int data;

    @Override
    public int compareTo(Object t) {
        if (t instanceof indexedObject) {
            return index.compareTo(((indexedObject)t).index);
        }
    }      
}

this can then be inserted into a binary tree

Upvotes: 0

sc_ray
sc_ray

Reputation: 8043

So if you are thinking of breaking up your tree as follows: Every layer is a power of 2...

Layer0 - root -> 2^0 = 1 (first element) 
Layer1 --------> 2^1 = 2 (next two elements) 
Layer2 --------> 2^2 = 4 (next four elements)

Its relatively trivial to break down the structure in the following form: [4], [5|2],[7|3|6|8]

What you probably want is to have a relationship where 4 has children 5 and 2, 5's children are 7 and 3 and 2's children are 6 and 8.

So the question is while iteration through this array how do I find out what a given number's children are? Assuming you have arranged the elements sequentially in an indexable data-structure such as an array and every element has exactly two children or none, you can craft your "tree-traversal" as follows:

Children of 4, which as at index 0(root), would be indexes 2^0 and 2^1 (indexes 1 and 2) Children for indexes 1 and 2 would be (2^1 + 1) and (2^1 + 2). Children for index 2 would be 2^2+1 and 2^2 + 2.

So the pattern boils down to 2^i+1(for the left child),2^i+2(for the right child). I hope this would help with your tree implementation.

Upvotes: 1

Sirko
Sirko

Reputation: 74096

I just can think of one way to create a tree like the one given

size( n ) = size of the subtree rooted in n
left( n ) = left child of n
right( n ) = right child of n

it then follows for the insert (x the node to be inserted, n the root of the current [sub]tree)

insert( x, n ) {

 if ( left(n) == null ) {
    left(n) = x;
    return;
 } else if ( right(n) == null ) {
    right(n) = x;
    return;
 } else {
    if ( size( left(n) ) <= size( right(n) ) {
       insert( x, left(n) );
    } else {
       insert( x, right(n) );
    }
 }

basically one tries to insert the new value on the side of the tree, which right now is the smaller one. if both are of the same size, left is favored before right.

I don't really know, whether this is what you asked for, but it at least creates the above tree out of the given order of input values.

Upvotes: 0

AlexZam
AlexZam

Reputation: 1196

The simpliest way to do it. Although it should never happen in real life. 8)

Queue queue = new Queue();

function add(input){
  element = input.popFirst();
  if(element == null) return false;

  node = queue.get();
  node.value = element;
  node.left = new Node();
  queue.put(node.left);
  node.right = new Node();
  queue.put(node.right);
  return true;
}

Node root = new Node();
queue.put(root);
while(add(input)){}
while(!queue.isEmpty){
  destroy queue.get();
}

Upvotes: 1

Sam
Sam

Reputation: 2969

The simplest solution is to let your data be a simple array you append to. Appending to the array, when representing the array as a binary tree, gives you a compacted, balanced tree. Accesses into that array are then computed by:

first_node_of_a_level = (branches^level)-1

Then choose the child node of that level you want. For instance, the root node is at (2^0)-1 which is index 0.

The first node on level 1 is (2^1)-1 = 1.
The first node on level 2 is (2^2)-1 = 3.
The first node on level 3 is (2^3)-1 = 7.

This is a very common implementation used in binary heaps. The Wikipedia article gives you the basics of finding the "child of" or "parent of" given a node's index in the array.

Upvotes: 1

Related Questions