fork download
copy 
  1.  
  2. import java.util.*;
  3. import java.lang.*;
  4. import java.io.*;
  5.  
  6. class Tree <Key extends Comparable<Key>, Value> {
  7.  
  8. 	private class Node {
  9. 		Key key;
  10. 		Value value;
  11. 		Node left, right;
  12. 		public Node (Key key, Value value) {
  13. 			this.key = key;
  14. 			this.value = value;
  15. 			this.left = this.right = null;
  16. 		}
  17. 	}
  18.  
  19. 	private Node root;
  20.  
  21. 	public Key getRootKey(){
  22. 		return root.key;
  23. 	}
  24. 	public Value getRootValue(){
  25. 		return root.value;
  26. 	}
  27.  
  28. 	private Node add (Node node,Key key, Value value){
  29. 		//возвращает измененный узел (после добавления значения)
  30. 		if (node == null){
  31. 			Node newnode = new Node(key,value);
  32. 			return newnode;
  33. 		}
  34. 		int compareResult = key.compareTo(node.key);
  35.                 if(compareResult == 0) {
  36.                     node.value = value;
  37.                     return node;
  38.                 }
  39.                 else if(compareResult < 0)
  40.                     node.left = add(node.left, key, value);
  41.                 else 
  42.                     node.right = add(node.right, key, value);
  43.         return node;
  44. 	}
  45.  
  46.         public Key MinKey(){
  47.            Node cur = root;
  48.            // спускаемся к самому левому листу, по свойству дерева - наименьший ключ там
  49.            for(; cur.left != null; cur = cur.left){}
  50.            return cur.key;
  51.         }
  52.         public Key MaxKey(){
  53.            Node cur = root;
  54.            // спускаемся к самому правому листу, по свойству дерева - наибольший ключ там
  55.            for(; cur.right != null; cur = cur.right){}
  56.            return cur.key;
  57.         }
  58.  
  59.         //вспомогательная функция, которая нигде не используется.
  60.         private Node NodeMinKey(Node node){
  61.            Node cur = node;
  62.            for(; cur.left != null; cur = cur.left){}
  63.            return cur;
  64.         }
  65.  
  66. 	public void add(Key key, Value value) {
  67. 		root = add(root, key, value);
  68. 	}
  69.  
  70.         //удаление вершины
  71. 	public void delete(Key key) {
  72.             Node cur = root;
  73.             Node prev = null;
  74.             //спускаемся по дереву, пока не найдем вершину или не уткнемся в null
  75.             for(; true; ){
  76.                 if(cur == null) return;
  77.                 if(key.compareTo(cur.key) < 0){
  78.                     prev = cur; cur = cur.left;
  79.                 }
  80.                 else if(key.compareTo(cur.key) > 0){
  81.                     prev = cur;
  82.                     cur = cur.right;
  83.                 }
  84.                 else break;
  85.             }
  86.             /*
  87.              * Итак, у нас есть элемент, который нужно удалить (cur) и его предок (prev)
  88.              * Теперь нас ждет разбор частных случаев:
  89.              *      1)Если правый сын удаляемого элемента не существует, мы можем просто выкинуть этот элемент из
  90.              *        цепи prev -> cur -> left, оставив prev -> left.
  91.              *      2)Если же правый сын существует, так просто выкинуть вершину мы не можем. 
  92.              *        Чтобы сохранить свойство дерева мы найдем узел с наименьшим ключом в правом поддереве cur,
  93.              *        присоединим к найденному узлу левого сына cur и заменим cur на этот узел.
  94.              */
  95.             if(cur.right == null)
  96.                 if(cur == prev.right)
  97.                     prev.right = cur.left;
  98.                 else
  99.                     prev.left = cur.left;
  100.             else{
  101.                 Node mostLeft = cur.right;
  102.                 prev = null;
  103.                 for(; mostLeft.left != null;){
  104.                     prev = mostLeft;
  105.                     mostLeft = mostLeft.left;
  106.                 }
  107.                 if(prev != null)
  108.                     prev.left = mostLeft.right;
  109.                 else
  110.                     cur.right = mostLeft.right;
  111.                 cur.key = mostLeft.key;
  112.                 cur.value = mostLeft.value;
  113.             }
  114.  
  115. 	}
  116.  
  117. 	public Value get(Key key) {
  118.             Node cur = root;
  119.             for(; true; ){
  120.                 if(cur == null) break;
  121.                 if(key.compareTo(cur.key) < 0)
  122.                     cur = cur.left;
  123.                 else if(key.compareTo(cur.key) > 0)
  124.                     cur = cur.right;
  125.                 else break;
  126.             }
  127.             return cur != null? cur.value : (Value)null;
  128. 	}
  129.  
  130. 	private void print(Node node, int level) {
  131. 		if (node != null) {
  132. 			print(node.right, level+1);
  133. 			for (int i=0; i < level; i++) {
  134. 				System.out.print("\t");
  135. 			}
  136. 			System.out.println(node.key + " => " + node.value); 
  137. 			print(node.left, level + 1);
  138. 		}
  139. 	}
  140.  
  141. 	public void print() {
  142. 		print(root, 0);
  143. 	}
  144.  
  145.  
  146.  
  147. public static void main (String[] args){
  148. 		Tree<Double, Double> a = new Tree<Double, Double>();
  149. 		int n = 100;
  150. 		for(int i = 0; i < n; i++){
  151. 			a.add( Math.round(Math.random() * 1000.0) + 1.0*i,  Math.round(Math.random() * 1000000.0) + 1.0*i);
  152. 		}
  153. 		System.out.println(a.MaxKey() + " => " + a.get(a.MaxKey()));
  154. 		System.out.println(a.MinKey() + " => " + a.get(a.MinKey()));
  155.                 System.out.println();
  156.                 System.out.println();
  157.                 System.out.println();
  158.                 System.out.println("First print");
  159. 		a.print();
  160. 		a.delete(a.getRootKey());
  161.                 System.out.println();
  162.                 System.out.println();
  163.                 System.out.println();
  164.                 System.out.println("Second print");
  165. 		a.print();
  166. 	}
  167. }
Runtime error #stdin #stdout 0.56s 320704KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
10947.0 => 121331.0
36.0 => 364655.0



First print
																																																																																																																																																																																																																																																																																																																																																																																																									10947.0 => 121331.0
																																																																																																																																																																																																																																																																																																																																																																																																								10937.0 => 868119.0
																																																																																																																																																																																																																																																																																																																																																																																																									10929.0 => 241163.0
																																																																																																																																																																																																																																																																																																																																																																																																							10928.0 => 467767.0
																																																																																																																																																																																																																																																																																																																																																																																																								10912.0 => 124017.0
																																																																																																																																																																																																																																																																																																																																																																																																									10911.0 => 70442.0
																																																																																																																																																																																																																																																																																																																																																																																																						10896.0 => 496723.0
																																																																																																																																																																																																																																																																																																																																																																																																					10870.0 => 618565.0
																																																																																																																																																																																																																																																																																																																																																																																																						10859.0 => 660267.0
																																																																																																																																																																																																																																																																																																																																																																																																									10854.0 => 719352.0
																																																																																																																																																																																																																																																																																																																																																																																																								10852.0 => 925744.0
																																																																																																																																																																																																																																																																																																																																																																																																							10847.0 => 724074.0
																																																																																																																																																																																																																																																																																																																																																																																																				10846.0 => 862117.0
																																																																																																																																																																																																																																																																																																																																																																																																						10841.0 => 257875.0
																																																																																																																																																																																																																																																																																																																																																																																																							10840.0 => 767328.0
																																																																																																																																																																																																																																																																																																																																																																																																					10835.0 => 287696.0
																																																																																																																																																																																																																																																																																																																																																																																																							10822.0 => 524952.0
																																																																																																																																																																																																																																																																																																																																																																																																						10820.0 => 834691.0
																																																																																																																																																																																																																																																																																																																																																																																																							10806.0 => 226934.0
																																																																																																																																																																																																																																																																																																																																																																																																								10804.0 => 527329.0
																																																																																																																																																																																																																																																																																																																																																																																																			10803.0 => 462781.0
																																																																																																																																																																																																																																																																																																																																																																																																				10799.0 => 933182.0
																																																																																																																																																																																																																																																																																																																																																																																																		10789.0 => 123904.0
																																																																																																																																																																																																																																																																																																																																																																																																	10788.0 => 964127.0
																																																																																																																																																																																																																																																																																																																																																																																																				10782.0 => 165237.0
																																																																																																																																																																																																																																																																																																																																																																																																					10773.0 => 36538.0
																																																																																																																																																																																																																																																																																																																																																																																																			10770.0 => 177432.0
																																																																																																																																																																																																																																																																																																																																																																																																					10765.0 => 578827.0
																																																																																																																																																																																																																																																																																																																																																																																																						10761.0 => 81988.0
																																																																																																																																																																																																																																																																																																																																																																																																				10759.0 => 873198.0
																																																																																																																																																																																																																																																																																																																																																																																																							10758.0 => 521694.0
																																																																																																																																																																																																																																																																																																																																																																																																						10756.0 => 23943.0
																																																																																																																																																																																																																																																																																																																																																																																																					10740.0 => 190792.0
																																																																																																																																																																																																																																																																																																																																																																																																		10737.0 => 562952.0
																																																																																																																																																																																																																																																																																																																																																																																																			10733.0 => 1008577.0
																																																																																																																																																																																																																																																																																																																																																																																																10725.0 => 354729.0
																																																																																																																																																																																																																																																																																																																																																																																																	10717.0 => 576502.0
																																																																																																																																																																																																																																																																																																																																																																																																		10712.0 => 509091.0
																																																																																																																																																																																																																																																																																																																																																																																															10706.0 => 431992.0
																																																																																																																																																																																																																																																																																																																																																																																																10700.0 => 107898.0
																																																																																																																																																																																																																																																																																																																																																																																														10693.0 => 382393.0
																																																																																																																																																																																																																																																																																																																																																																																																10688.0 => 747887.0
																																																																																																																																																																																																																																																																																																																																																																																																	10682.0 => 125153.0
																																																																																																																																																																																																																																																																																																																																																																																															10680.0 => 816736.0
																																																																																																																																																																																																																																																																																																																																																																																																10679.0 => 407427.0
																																																																																																																																																																																																																																																																																																																																																																																																		10674.0 => 294963.0
																																																																																																																																																																																																																																																																																																																																																																																																	10672.0 => 341139.0
																																																																																																																																																																																																																																																																																																																																																																																													10663.0 => 607765.0
																																																																																																																																																																																																																																																																																																																																																																																															10654.0 => 949381.0
																																																																																																																																																																																																																																																																																																																																																																																														10652.0 => 512324.0
																																																																																																																																																																																																																																																																																																																																																																																												10644.0 => 486287.0
																																																																																																																																																																																																																																																																																																																																																																																															10640.0 => 480791.0
																																																																																																																																																																																																																																																																																																																																																																																																	10637.0 => 871681.0
																																																																																																																																																																																																																																																																																																																																																																																																10629.0 => 891283.0
																																																																																																																																																																																																																																																																																																																																																																																														10626.0 => 675083.0
																																																																																																																																																																																																																																																																																																																																																																																													10621.0 => 541776.0
																																																																																																																																																																																																																																																																																																																																																																																														10620.0 => 1006448.0
																																																																																																																																																																																																																																																																																																																																																																																																10614.0 => 126161.0
																																																																																																																																																																																																																																																																																																																																																																																																	10613.0 => 28674.0
																																																																																																																																																																																																																																																																																																																																																																																															10611.0 => 192907.0
																																																																																																																																																																																																																																																																																																																																																																																											10610.0 => 810087.0
																																																																																																																																																																																																																																																																																																																																																																																															10603.0 => 927702.0
																																																																																																																																																																																																																																																																																																																																																																																																10600.0 => 684815.0
																																																																																																																																																																																																																																																																																																																																																																																														10598.0 => 142765.0
																																																																																																																																																																																																																																																																																																																																																																																													10596.0 => 520602.0
																																																																																																																																																																																																																																																																																																																																																																																														10594.0 => 524910.0
																																																																																																																																																																																																																																																																																																																																																																																															10592.0 => 480709.0
																																																																																																																																																																																																																																																																																																																																																																																																10591.0 => 953015.0
																																																																																																																																																																																																																																																																																																																																																																																																	10590.0 => 136679.0
																																																																																																																																																																																																																																																																																																																																																																																												10586.0 => 927657.0
																																																																																																																																																																																																																																																																																																																																																																																													10585.0 => 75676.0
																																																																																																																																																																																																																																																																																																																																																																																															10584.0 => 631638.0
																																																																																																																																																																																																																																																																																																																																																																																														10582.0 => 388147.0
																																																																																																																																																																																																																																																																																																																																																																																															10569.0 => 606537.0
																																																																																																																																																																																																																																																																																																																																																																																										10567.0 => 530765.0
																																																																																																																																																																																																																																																																																																																																																																																																10566.0 => 830464.0
																																																																																																																																																																																																																																																																																																																																																																																															10565.0 => 23814.0
																																																																																																																																																																																																																																																																																																																																																																																														10563.0 => 122605.0
																																																																																																																																																																																																																																																																																																																																																																																													10558.0 => 1009504.0
																																																																																																																																																																																																																																																																																																																																																																																														10551.0 => 684053.0
																																																																																																																																																																																																																																																																																																																																																																																												10548.0 => 497229.0
																																																																																																																																																																																																																																																																																																																																																																																													10547.0 => 289553.0
																																																																																																																																																																																																																																																																																																																																																																																											10546.0 => 951367.0
																																																																																																																																																																																																																																																																																																																																																																																												10544.0 => 525962.0
																																																																																																																																																																																																																																																																																																																																																																																									10542.0 => 843101.0
																																																																																																																																																																																																																																																																																																																																																																																												10538.0 => 183351.0
																																																																																																																																																																																																																																																																																																																																																																																											10536.0 => 979500.0
																																																																																																																																																																																																																																																																																																																																																																																														10533.0 => 509290.0
																																																																																																																																																																																																																																																																																																																																																																																													10530.0 => 940811.0
																																																																																																																																																																																																																																																																																																																																																																																												10529.0 => 340305.0
																																																																																																																																																																																																																																																																																																																																																																																										10522.0 => 908906.0
																																																																																																																																																																																																																																																																																																																																																																																													10521.0 => 664031.0
																																																																																																																																																																																																																																																																																																																																																																																														10520.0 => 940982.0
																																																																																																																																																																																																																																																																																																																																																																																												10516.0 => 19242.0
																																																																																																																																																																																																																																																																																																																																																																																														10515.0 => 530433.0
																																																																																																																																																																																																																																																																																																																																																																																													10513.0 => 654013.0
																																																																																																																																																																																																																																																																																																																																																																																														10507.0 => 831290.0
																																																																																																																																																																																																																																																																																																																																																																																											10506.0 => 608737.0
																																																																																																																																																																																																																																																																																																																																																																																												10504.0 => 733794.0
																																																																																																																																																																																																																																																																																																																																																																																													10500.0 => 497494.0
																																																																																																																																																																																																																																																																																																																																																																																								10498.0 => 531166.0
																																																																																																																																																																																																																																																																																																																																																																																										10495.0 => 39004.0
																																																																																																																																																																																																																																																																																																																																																																																														10493.0 => 952497.0
																																																																																																																																																																																																																																																																																																																																																																																													10490.0 => 653929.0
																																																																																																																																																																																																																																																																																																																																																																																														10487.0 => 640405.0
																																																																																																																																																																																																																																																																																																																																																																																												10486.0 => 847264.0
																																																																																																																																																																																																																																																																																																																																																																																														10485.0 => 150936.0
																																																																																																																																																																																																																																																																																																																																																																																																10484.0 => 81201.0
																																																																																																																																																																																																																																																																																																																																																																																															10482.0 => 935989.0
																																																																																																																																																																																																																																																																																																																																																																																													10478.0 => 584024.0
																																																																																																																																																																																																																																																																																																																																																																																											10475.0 => 747977.0
																																																																																																																																																																																																																																																																																																																																																																																												10473.0 => 157328.0
																																																																																																																																																																																																																																																																																																																																																																																													10472.0 => 445136.0
																																																																																																																																																																																																																																																																																																																																																																																									10471.0 => 361817.0
																																																																																																																																																																																																																																																																																																																																																																																										10467.0 => 382369.0
																																																																																																																																																																																																																																																																																																																																																																																							10465.0 => 37541.0
																																																																																																																																																																																																																																																																																																																																																																																									10464.0 => 638047.0
																																																																																																																																																																																																																																																																																																																																																																																								10463.0 => 444058.0
																																																																																																																																																																																																																																																																																																																																																																																										10462.0 => 734801.0
																																																																																																																																																																																																																																																																																																																																																																																									10461.0 => 294716.0
																																																																																																																																																																																																																																																																																																																																																																																										10460.0 => 857731.0
																																																																																																																																																																																																																																																																																																																																																																																											10458.0 => 209540.0
																																																																																																																																																																																																																																																																																																																																																																																												10456.0 => 959900.0
																																																																																																																																																																																																																																																																																																																																																																																						10454.0 => 971551.0
																																																																																																																																																																																																																																																																																																																																																																																									10452.0 => 830355.0
																																																																																																																																																																																																																																																																																																																																																																																								10449.0 => 62910.0
																																																																																																																																																																																																																																																																																																																																																																																										10447.0 => 629361.0
																																																																																																																																																																																																																																																																																																																																																																																									10445.0 => 400360.0
																																																																																																																																																																																																																																																																																																																																																																																							10443.0 => 112325.0
																																																																																																																																																																																																																																																																																																																																																																																								10441.0 => 186040.0
																																																																																																																																																																																																																																																																																																																																																																																					10440.0 => 355743.0
																																																																																																																																																																																																																																																																																																																																																																																				10433.0 => 839546.0
																																																																																																																																																																																																																																																																																																																																																																																						10430.0 => 969826.0
																																																																																																																																																																																																																																																																																																																																																																																								10429.0 => 378865.0
																																																																																																																																																																																																																																																																																																																																																																																							10428.0 => 159099.0
																																																																																																																																																																																																																																																																																																																																																																																									10427.0 => 752653.0
																																																																																																																																																																																																																																																																																																																																																																																								10426.0 => 127497.0
																																																																																																																																																																																																																																																																																																																																																																																									10422.0 => 624261.0
																																																																																																																																																																																																																																																																																																																																																																																					10419.0 => 498381.0
																																																																																																																																																																																																																																																																																																																																																																																							10418.0 => 889201.0
																																																																																																																																																																																																																																																																																																																																																																																						10415.0 => 486637.0
																																																																																																																																																																																																																																																																																																																																																																																							10412.0 => 95017.0
																																																																																																																																																																																																																																																																																																																																																																																									10407.0 => 647527.0
																																																																																																																																																																																																																																																																																																																																																																																								10404.0 => 304451.0
																																																																																																																																																																																																																																																																																																																																																																																			10401.0 => 453706.0
																																																																																																																																																																																																																																																																																																																																																																																					10397.0 => 633707.0
																																																																																																																																																																																																																																																																																																																																																																																				10396.0 => 453252.0
																																																																																																																																																																																																																																																																																																																																																																																								10394.0 => 80088.0
																																																																																																																																																																																																																																																																																																																																																																																									10393.0 => 986533.0
																																																																																																																																																																																																																																																																																																																																																																																							10392.0 => 326354.0
																																																																																																																																																																																																																																																																																																																																																																																								10391.0 => 695622.0
																																																																																																																																																																																																																																																																																																																																																																																										10390.0 => 146569.0
																																																																																																																																																																																																																																																																																																																																																																																									10386.0 => 831221.0
																																																																																																																																																																																																																																																																																																																																																																																						10385.0 => 524102.0
																																																																																																																																																																																																																																																																																																																																																																																							10379.0 => 918314.0
																																																																																																																																																																																																																																																																																																																																																																																					10378.0 => 791623.0
																																																																																																																																																																																																																																																																																																																																																																																						10377.0 => 399169.0
																																																																																																																																																																																																																																																																																																																																																																																		10376.0 => 386356.0
																																																																																																																																																																																																																																																																																																																																																																																				10375.0 => 497538.0
																																																																																																																																																																																																																																																																																																																																																																																			10374.0 => 142872.0
																																																																																																																																																																																																																																																																																																																																																																																				10373.0 => 172468.0
																																																																																																																																																																																																																																																																																																																																																																																						10371.0 => 983962.0
																																																																																																																																																																																																																																																																																																																																																																																					10368.0 => 681040.0
https://ideone.com/GSlwc0
Binary Search Tree
language:
Java (12.0.1)
created:
8 years ago
visibility:
public

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!