Results 1 to 2 of 2
  1. #1
    danylo is offline Member
    Join Date
    Mar 2008
    Posts
    1
    Rep Power
    0

    Default Can anybody help with cuncurrent binary search tree guys)

    Good afternoon, I'v got a problem with concurency in java program, wonder wether somebody can give me a couple of hints on how to improve the program sothat it could be cuncurrent and run cuncurrent processes.
    Briefly about the task- i have to construct a binary search tree and implement it using cuncurency. I managed to write program in a slightly usual way, and could not do much about ncurrent bit. So thats the shorten code so far

    class Node {
    Object data;
    Node left, right;

    public Node (Object d, Node Lef, Node Rig) {

    data = d;
    left = Lef;
    right = Rig;
    }
    public synchronized void setLeft(Node obj) { left = obj;}
    setRight()
    getLeft() - other methods in my Node class
    getData()
    setData()


    }

    public class BinarySearchTree {
    private Node root;
    public static void main(String arg[]){

    }

    BinarySearchTree(){
    root = null;

    }

    boolean isEmpty(){
    if(root==null) return true;
    return false;
    }

    boolean search(Object x) {
    return search(root, x);
    }

    boolean search(Node T, Object x) {
    if (T == null) return false;
    if (T.getData().equals(x)) return true;
    if (((Comparable)x).compareTo(T.getData()) < 0) {
    return search(T.left, x);
    }
    else {
    return search(T.right, x);
    }
    }


    boolean insert(Object x) {
    if(search(x)) return false;
    if (isEmpty()) {
    root = new Node(x, null, null);
    return true;
    }
    else insert(root, x);
    return true;
    }

    boolean insert(Node t , Object x) {
    if( t == null )
    t = new Node( x , null , null );
    else if(((Comparable)x).compareTo(t.getData()) < 0) {
    if(t.getLeft() == null ) {t.left = new Node(x , null , t);}
    else {insert(t.getLeft() , x);} }
    else if(((Comparable)x).compareTo(t.getData()) > 0){
    if(t.getRight() == null ) {t.right = new Node(x , t , null);}
    else {insert(t.getRight(), x);}

    } return true;
    }


    public boolean delete(Object x) {

    delete(root, x);
    return true;
    }

    private Node delete(Node T, Object x) {
    if (T == null) return null;
    if (x.equals(T.getData())) {
    if (T.left == null && T.right == null) return null;
    if (T.left == null) return T.right;
    if (T.right == null) return T.left;

    Node tmp = smallest (T.right);
    T.setData( tmp.getData() );

    T.right = (delete(T.right, tmp.getData()) );
    return T;

    }
    else if (((Comparable)x).compareTo(T.getData()) < 0) {
    T.left = delete(T.left, x);
    return T;
    }
    else {
    T.right = delete(T.right, x);
    return T;
    }
    }
    private static Node smallest(Node T)
    {
    if (T.left == null) return T;
    else return smallest(T.left);
    }
    }

    The program complis and runs and pretty much does the job. And i dont kno how to upgrade it and there quite a number of cuncurrency methods at which im not good at all. Can somebody give me some hins on how to start and which concurny method is more appropriate for the task

    Thank You

  2. #2
    danielstoner's Avatar
    danielstoner is offline Senior Member
    Join Date
    Apr 2008
    Location
    Canada
    Posts
    191
    Rep Power
    7

    Default

    Synchronize the public methods of the BinarySearchTree class or create a synchronized decorator class ConcurrentBinarySearchTree which keeps inside an instance of BinarySearchTree. It will have the same interface as BinarySearchTree but all the public methods will be synchronized.
    Daniel @ [www.littletutorials.com]
    Language is froth on the surface of thought

Similar Threads

  1. Binary Tree Implementation in Java
    By Java Tip in forum java.lang
    Replies: 0
    Last Post: 04-16-2008, 10:35 PM
  2. Binary Search in Java
    By Java Tip in forum Algorithms
    Replies: 0
    Last Post: 04-15-2008, 07:43 PM
  3. hi guys!!!
    By surenani in forum Introductions
    Replies: 4
    Last Post: 01-23-2008, 05:24 AM
  4. binary search
    By tranceluv in forum New To Java
    Replies: 10
    Last Post: 01-14-2008, 07:13 PM
  5. problem with recursive binary search program
    By imran_khan in forum New To Java
    Replies: 3
    Last Post: 08-02-2007, 03:08 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •