StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Here is the implementation of Binary Search Tree</p> <pre><code>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;} } public int size(){ return size(root); } public int size(Node x){ if(x==null) return 0; else return x.N; } 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){ return 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 max(root).key;//min() changed to max() } 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;//conditinoal equals 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 deleteMax(){ root= deleteMax(root);//recursive call deleteMax() } private Node deleteMax(Node x){ if(x.right==null) return x.left; x.right=deleteMax(x.right); x.N =size(x.right)+size(x.left)+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; } } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload