Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 3 of 3

Thread: basic binary search tree implementation

  1. #1
    Junior Member
    Join Date
    Oct 2013
    Posts
    1
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default basic binary search tree implementation

    public class BST<Key extends Comparable<Key>,Value>{

    private Node root;

    private class Node{
    private Key key;
    private Value val;
    private Node left, right;
    private int N;

    public Node(Key key,Value val,int N)
    { this.key = key; this.val=val; this.N=N;}
    }
    return size(root);
    }
    public int size(Node x){
    if(x==null) return 0;
    else
    return x.N;
    public int size(){
    }
    public Value get(Key key){
    return get(root,key);
    }
    private Value get(Node x, Key key){
    if(x==null) return null;
    int cmp = key.compareTo(x.key);
    if (cmp<0) return get(x.left,key);
    else if (cmp<0) return get(x.right,key);
    else return x.val;
    }
    public Node put(Key key,Value val){
    root = put(root,Key,val);
    }
    private Node put(Node x, Key key, Value val){
    if(x==null ) return new Node(key ,val,1);
    int cmp =key.compareTo(x.key);
    if(cmp<0) x.left= put(x.left,key,val);
    else if(cmp>0) x.right= put(x.right,key,val);
    else x.val=val;
    x.N=size(x.left)+size(x.right)+1;
    return x;
    }

    public Key min(){
    return min(root).key;
    }
    private Node min(Node x){
    if(x.left==null) return x;
    return min(x.left);
    }
    public Key max(){
    return min(root).key;
    }
    private Node max(Node x){
    if(x.right==null) return x;
    return max(x.right);
    }
    public Key select(int k){
    return select(root,k).key;
    }
    private Node select(Node x,int k)
    {
    if(x=null)return null;
    int t=size(x.left);
    if(t>k) return(x.left,k);
    else if(t<k) return(x.right,k-t-1);
    else return x;
    }
    public int rank(Key key,Node x)
    { return rank(key,root); }
    private int rank(Key key,Node x){
    if(x==null) return 0;
    int cmp =key.compareTo(x.key);
    if(cmp<0) return rank(key,x.left);
    else if(cmp>0) return 1+size(x.left)+rank(key,x.right);
    else return size(x.left);
    }
    public void deleteMin(){
    root= deleteMin(root);
    }
    private Node deleteMin(Node x){
    if(x.left==null) return x.right;
    x.left=deleteMin(x.left);
    x.N =size(x.left)+size(x.right)+1;
    return x;
    }

    public void delete(Key key){
    root=delete(root,key)
    }
    private Node delete(Node x,Key key){
    if(x==null) return null;
    int cmp = key.compareTo(x.key);
    if(cmp<0)x.left = delete(x.left,key);
    else if(cmp>0) x.right= delete(x.right,key);
    else{
    if(x.right==null) return x.left;
    if(x.left==null) return x.right;
    Node t =x;
    x=min(t.right);
    x.right=deleteMin(t.right);
    x.left=t.left;
    }
    x.N=size(x.left)+size(x.right)+1;
    return x;
    }

    }

    --- Update ---

    ive got this from the internet but when i debug it.. it does'nt work (many errors ! what should i do)


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: basic binary search tree implementation

    Please edit your post and wrap your code with code tags:
    [code=java]
    <YOUR CODE HERE>
    [/code]
    to get highlighting and preserve formatting.
    it does'nt work (many errors !
    If you are getting error messages, copy the full text and paste it here. Otherwise please explain about the errors and "doesn't work".
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Junior Member
    Join Date
    Oct 2013
    Posts
    3
    Thanks
    0
    Thanked 1 Time in 1 Post

    Default Re: basic binary search tree implementation

    I say get the algo then build yourself it will be easy for you to debug.
    And please wrap your post in [code] tags

Similar Threads

  1. Binary Search Tree Recursion Implementation
    By ambientplanet in forum What's Wrong With My Code?
    Replies: 0
    Last Post: June 8th, 2013, 03:46 PM
  2. Binary Search Tree inorder tree traversal
    By Maukkv in forum What's Wrong With My Code?
    Replies: 17
    Last Post: January 26th, 2013, 05:28 PM
  3. Data Structures(Binary Search Tree to AVL Tree)ASAP
    By jfAdik in forum Algorithms & Recursion
    Replies: 2
    Last Post: April 5th, 2010, 03:58 AM
  4. Binary Search Tree
    By Koren3 in forum What's Wrong With My Code?
    Replies: 9
    Last Post: November 12th, 2009, 09:27 AM
  5. Binary Search Tree implementation
    By Ceasar in forum Java Theory & Questions
    Replies: 3
    Last Post: October 9th, 2009, 12:23 AM