fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6. import java.security.Key;
  7.  
  8. /**
  9.  * Created by green on 26.11.15.
  10.  */
  11. class BST <Key extends Comparable<Key>, Value> {
  12.  
  13.     private class Node {
  14.         Key key;
  15.         Value value;
  16.         Node left, right, father;
  17.         public Node (Key key, Value value) {
  18.             this.key = key;
  19.             this.value = value;
  20.             this.left = this.right = null;
  21.             this.father = null;
  22.         }
  23.         public Node (Key key, Value value, Node father) {
  24.             this.key = key;
  25.             this.value = value;
  26.             this.left = this.right = null;
  27.             this.father = father;
  28.         }
  29.     }
  30.  
  31.     private Node root;
  32.  
  33.     private Node add (Node node,Key key, Value value, Node father){
  34.         if (node == null){
  35.             Node newnode = new Node(key,value, father);
  36.             return newnode;
  37.         }
  38.         int compareResult = key.compareTo(node.key);
  39.         if (compareResult > 0) node.right = add(node.right, key, value, node);
  40.         else if(compareResult < 0) node.left = add(node.left, key, value, node);
  41.         else{
  42.             node.value = value;
  43.         }
  44.         return node;
  45.     }
  46.  
  47.     public void add(Key key, Value value) {
  48.         root = add(root, key, value, root);
  49.     }
  50.  
  51.     private Node delete(Node node, Key key){
  52.         if(node == null) return null;
  53.         int compareResult = key.compareTo(node.key);
  54.         if(compareResult > 0){
  55.             node.right = delete(node.right, key);
  56.         }else if(compareResult < 0){
  57.             node.left = delete(node.left, key);
  58.         }else{
  59.             if(node.right == null && node.left == null){
  60.                 return node = null;
  61.             }else if(node.right == null){
  62.                 return node = node.left;
  63.             }else if(node.left == null){
  64.                 return node = node.right;
  65.             }else{
  66.                 if(node.right.left == null){
  67.                     node.right.left = node.left;
  68.                     node.right.father = node.father;
  69.                     return node = node.right;
  70.                 }else{
  71.                     Node res = min(node.right);
  72.                     node.key = res.key;
  73.                     node.value = res.value;
  74.                     delete(node.right, node.key);
  75.                     return node;
  76.                 }
  77.             }
  78.         }
  79.         return node;
  80.     }
  81.  
  82.     public void delete(Key key) {
  83.         root = delete(root, key);
  84.     }
  85.  
  86.     public Value minKey(){
  87.         return min(root).value;
  88.     }
  89.  
  90.     public Value maxKey(){
  91.         return max(root).value;
  92.     }
  93.  
  94.     private Node min(Node node){
  95.         if(node.left == null) return node;
  96.         return min(node.left);
  97.     }
  98.  
  99.     private Node max(Node node){
  100.         if(node.right == null) return node;
  101.         return min(node.right);
  102.     }
  103.  
  104.     private Value get(Node node, Key key){
  105.         if(node == null) return null;
  106.         int compareResult = key.compareTo(node.key);
  107.         if(compareResult == 0){
  108.             return node.value;
  109.         }else if(compareResult > 0){
  110.             return get(node.right, key);
  111.         }else{
  112.             return get(node.left, key);
  113.         }
  114.     }
  115.  
  116.     public Value get(Key key) {
  117.         return get(root, key);
  118.     }
  119.  
  120.     private void print(Node node, int level) {
  121.         if (node != null) {
  122.             print(node.right,level+1);
  123.             for (int i=0;i<level;i++) {
  124.                 System.out.print("\t");
  125.             }
  126.             System.out.println(node.key + "->" + node.value);
  127.             print(node.left,level+1);
  128.         }
  129.     }
  130.  
  131.     public void print() {
  132.         print(root,0);
  133.     }
  134.  
  135. }
  136.  
  137. /* Name of the class has to be "Main" only if the class is public. */
  138. class Ideone
  139. {
  140. 	public static void main (String[] args) throws java.lang.Exception
  141. 	{
  142. 		BST<Integer, String> tree = new BST<>();
  143.         tree.add(10, "Test1");
  144.         tree.add(12, "Test2");
  145.         tree.add(1, "Test3");
  146.         tree.add(5, "Test4");
  147.         tree.add(6, "Test5");
  148.         tree.add(3, "Test6");
  149.         tree.print();
  150.         tree.delete(5);
  151.         tree.print();
  152.         System.out.println(tree.get(1));
  153.         System.out.println(tree.minKey());
  154.         System.out.println(tree.maxKey());
  155.         System.out.println(tree.get(3));
  156. 	}
  157. }
Success #stdin #stdout 0.12s 320576KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
	12->Test2
10->Test1
			6->Test5
		5->Test4
			3->Test6
	1->Test3
	12->Test2
10->Test1
		6->Test5
			3->Test6
	1->Test3
Test3
Test3
Test2
Test6
https://ideone.com/y2HpOt
language:
Java (12.0.1)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!