What is the most efficient way to create unsorted binary tree in java?

Question

I need to create an unsorted binary tree (one requirement is unsorted) that contains String as the value. My class diagram looks like this:

 public class Node { private String desc; private Node leftNode = null; private Node rightNode = null; public Node(String desc) { this.desc = desc; } public String getDesc() { return desc; } public Node getLeftNode() { return leftNode; } public Node getRightNode() { return rightNode; } } 

In the end, I want to replace any node that matches the String description with a new node that has a new description (including duplicates with the old description).

So my question is: what's the best way to handle a Node insert when creating an unsorted binary tree?

I thought of two ways. The first would be to simply have two methods: setLeftNode(Node root, String desc) and setRightNode(Node root, String desc) , which someone could call using Node of their choice as the root. If there is already a left / right Node , then it will simply move down until it hits a node that has no left Node left. But this can introduce problems producing super large heights.

The second way, which I thought was to have a dedicated root Node , in this case create the first Node , and then just create a new Node in order.

So what is the best way to create an unsorted binary tree?

Answer 1

 public class BinaryTree{ private BinaryTree right; private BinaryTree left; private String data; public BinaryTree(String s){ data = s; right = null; left = null; } public void setLeft (BinaryTree l){ left = l; } public void setRight(BinaryTree r){ right = r; } } 

Your question assumes the tree should be balanced, etc. when inserting an element, you must recursively check the number of nodes on each side of the tree:

 public int checkTree(){ if(left == null && right == null){ return 1; }else if(left == null){ return 1 + right.checkTree(); }else if(right == null){ return 1 + left.checkTree(); }else{ return 1 + left.checkTree() + right.checkTree(); } } public void insert(BinaryTree bt){ if(left == null){ setLeft(bt); }else if(right == null){ setRight(bt); }else{ if(left.checkTree() <= right.checkTree()){ left.insert(bt); }else{ right.insert(bt); } } } 

:


Edition:

 public class BinaryTree { private BinaryTree right; private BinaryTree left; private String data; private int weight; public BinaryTree(String s){ data = s; right = null; left = null; weight = 1; } public void setLeft (BinaryTree l){ left = l; weight++; } public void setRight(BinaryTree r){ right = r; weight++; } public int getWeight(){ return weight; } public void insert(BinaryTree bt){ if(left == null){ setLeft(bt); }else if(right == null){ setRight(bt); }else{ if(left.getWeight() <= right.getWeight()){ left.insert(bt); weight++; }else{ right.insert(bt); weight++; } } } } 

Answer 2

by definition, a binary tree has the lowest elements on the left and the highest on the right. But if you really want everything to go wrong (sorted), you can call the rand function, which leads to 0 or 1, and if 0, then go left, if 1 go right, randomly. This will result in an unsorted tree

Answer 3

In the end, I want to be able to replace any node that matches the description lines with a new node that has a new description (including duplicates with the old description).

To do this, you have to look for the whole tree:

 private Node searchBasedOnValue(String desc, Node currentNode) { Node result = null if (currentNode == null) return null; if (currentNode.getDesc().equals(desc)) return currentNode ; if (currentNode.getLeftNode() != null) result = searchBasedOnValue(desc,currentNode.getLeftNode()); if (result == null) result = searchBasedOnValue(desc,currentNode.getRightNode()); return result; } 

IMO, the regular Binary Tree never sorted, the one that is sorted is called the Binary Search Tree . To insert you need to handle the way you want it. Maybe you can insert nodes alternatively into the left and right children of your tree so that they are balanced to some extent. It is up to you how you take care of this.

I have not seen much practical use for regular Binary Tree , since most of the time we use Binary Search Tree , which have the best performance ( lg(n) ) in terms of insertion, deletion and search.

Answer 4

If it is unsorted, why build a binary tree at all? You cannot perform a search without a full scan, so you can place everything in an array, since access to any element will be O (n) due to the inability to search.

Answer 5

This is the fastest way to build an unsorted binary tree without any restrictions on its shape:

First you need a constructor like this:

  public Node(String desc, Node left, Node right) { this.desc = desc; this.left = left; this.right = right; } 

Then build the tree as follows:

  Node root = null; for (String input: ...) { root = new Node(input, root, null); } 

Obviously, this gives you an unbalanced, unsorted tree, for which searching involves looking at all the nodes. However, if the tree is unsorted, then the fact that the tree is unbalanced does not matter.

In general, finding an unsorted tree has the same complexity as searching a list, and the code is more complex.