Java: How to implement a universal binary search tree?

Question

So far I have written the Node class as

class Node { private value; private Node left; private Node right; public int getValue() { return value; } public void setValue(int value) { this.value = value; } public Node getLeft() { return left; } public void setLeft(Node left) { this.left = left; } public Node getRight() { return right; } public void setRight(Node right) { this.right = right; } } 

and binary search tree as

 public class BinarySearchTree { private Node root; public BinarySearchTree(int value) { root = new Node(value); } public void insert(int value) { Node node = new Node(value); // insert logic goes here to search and insert } } 

Now I would like to support BinarySearchTree to have a Node insert of any type, such as strings, people

How can I make it general for any type of storage?

Answer 1

Use generics:

 class Node<T extends Comparable<T>> { private T value; ... } public class BinarySearchTree<T extends Comparable<T>> { private Node<T> root; public BinarySearchTree(T value) { root = new Node<T>(value); } public void insert(T value) { Node<T> node = new Node<T>(value); // insert logic goes here to search and insert } } 

Answer 2

Just create each of the Node and BinarySearchTree classes:

 class Node<T extends Comparable<T>> { private T value; private Node<T> left; private Node<T> right; public Node(T value) { this.value = value; } public T getValue() { return value; } public void setValue(T value) { this.value = value; } public Node<T> getLeft() { return left; } public void setLeft(Node<T> left) { this.left = left; } public Node<T> getRight() { return right; } public void setRight(Node<T> right) { this.right = right; } } 

and:

 class BinarySearchTree<T extends Comparable<T>> { private Node<T> root; public BinarySearchTree(T value) { root = new Node<T>(value); } public void insert(T value) { Node<T> node = new Node<T>(value); // insert logic goes here to search and insert } } 

Note the limitation of the Comparable extension, which you will need later to ensure the ordering of the node in the tree. Thanks to Zaska for the offer.

Answer 3

Please, not your code does not compile.
Here you have a few problems -
A. Define Node as Common -

 public class Node<T> { private T value; //... here goes the rest of your code } 

B. Your search class must also be generic and the signature must be

 public class BinarySearchTree <T extends Comparable<T>> { public BinarySearchTree(T value) { //Do your logic here } public void insert(T value) { //Do your logic here } } 

This is necessary in order to force you to provide only types that implement Comparable so that you can search in the tree.

Answer 4

You have two options:

1) You can get into generics / templates.

2) Apply your tree to type Object instead of int and be responsible for casting the user.

Answer 5

I found SnapTreeMap that implements a parallel AVL tree here .

Answer 6

 Please find the BST using Generics, U can find more information on below link 

https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/code/BST.java

 public class BinarySearchTree< T extends Comparable<T>> { Node root; class Node { T data; Node left; Node right; public Node(T data) { this.data = data; } } public boolean isEmpty() { return root == null; } public void insert(T value) { if(isEmpty()) root = new Node(value); else insert(root, value); } private void insert(Node node, T value) { if(value.compareTo(node.data) < 0) { if(node.left == null) node.left = new Node(value); else insert(node.left, value); } else { if(node.right == null) node.right = new Node(value); else insert(node.right, value); } } } 

Answer 7

Returning to the second question, you should use the Template:

http://www.oracle.com/technetwork/articles/javase/generics-136597.html

First of all:

http://en.wikipedia.org/wiki/Binary_search_algorithm http://en.wikipedia.org/wiki/Tree_rotation (insert)

Maybe read faster:

http://www.roseindia.net/java/java-get-example/java-binary-tree-code.shtml

Good study!