fork(2) download
  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.  * Created by green on 19.12.15.
  9.  */
  10.  
  11. class AVL <Key extends Comparable<Key>, Value> {
  12. public class Node {
  13. private int h;
  14. private int balance;
  15. Key key;
  16. Value value;
  17. private Node left, right, father;
  18. public Node (Key key, Value value, Node father) {
  19. this.key = key;
  20. this.value = value;
  21. this.left = this.right = null;
  22. this.father = father;
  23. this.h = 1;
  24. this.balance = 0;
  25. }
  26. public Node next(){
  27. return getHigherNode(this.key);
  28. }
  29. public Node previus(){
  30. return getLowerNode(this.key);
  31. }
  32. }
  33.  
  34. private Node root;
  35.  
  36. //Возвращает ближайщий узел , больше данного ключа, если узла с таким ключом нет, то возвращает ближайщий узел, больше заданного ключа. Если нет ближайщего большего позначению,чем заданый ключ, то возвращает null
  37. private Node getHigherNode(Key key) {
  38. Node p = root;
  39. while (p != null) {
  40. int cmp = key.compareTo(p.key);
  41. if (cmp < 0) {
  42. if (p.left != null)
  43. p = p.left;
  44. else
  45. return p;
  46. } else {
  47. if (p.right != null) {
  48. p = p.right;
  49. } else {
  50. Node father = p.father;
  51. Node ch = p;
  52. while (father != null && ch == father.right) {
  53. ch = father;
  54. father = father.father;
  55. }
  56. return father;
  57. }
  58. }
  59. }
  60. return null;
  61. }
  62.  
  63. //Возвращает ближайщий узел , меньше данного ключа, если узла с таким ключом нет, то возвращает ближайщий узел, меньше заданного ключа. Если нет ближайщего большего позначению,чем заданый ключ, то возвращает null
  64. private Node getLowerNode(Key key) {
  65. Node p = root;
  66. while (p != null) {
  67. int cmp = key.compareTo(p.key);
  68. if (cmp > 0) {
  69. if (p.right != null)
  70. p = p.right;
  71. else
  72. return p;
  73. } else {
  74. if (p.left != null) {
  75. p = p.left;
  76. } else {
  77. Node father = p.father;
  78. Node ch = p;
  79. while (father != null && ch == father.left) {
  80. ch = father;
  81. father = father.father;
  82. }
  83. return father;
  84. }
  85. }
  86. }
  87. return null;
  88. }
  89.  
  90. public Node getFirstNode(){
  91. return min(root);
  92. }
  93.  
  94. public Node getLastNode(){
  95. return max(root);
  96. }
  97.  
  98. private int height(Node x, Node y){
  99. if(x == null && y == null) return 0;
  100. else if(x == null) return y.h;
  101. else if(y == null) return x.h;
  102. else return Math.max(x.h, y.h);
  103. }
  104.  
  105. private int balance(Node x, Node y){
  106. if(x == null && y == null) return 0;
  107. else if(x == null) return - y.h;
  108. else if(y == null) return x.h;
  109. else return x.h - y.h;
  110. }
  111.  
  112. private Node add (Node node,Key key, Value value, Node father){
  113. if (node == null){
  114. Node newnode = new Node(key,value, father);
  115. return newnode;
  116. }
  117. int compareResult = key.compareTo(node.key);
  118. if (compareResult > 0){node.right = add(node.right, key, value, node); node.h = height(node.left, node.right) + 1;}
  119. else if(compareResult < 0){node.left = add(node.left, key, value, node); node.h = height(node.left, node.right) + 1;}
  120. else{
  121. node.value = value;
  122. }
  123. node.balance = balance(node.left, node.right);
  124. if(node.balance == -2){
  125. node = leftRotation(node);
  126. }else if(node.balance == 2){
  127. node = rightRotation(node);
  128. }
  129. return node;
  130. }
  131.  
  132. private Node leftRotation(Node node) {
  133. if(node.right.right == null && node.right.left != null){
  134. node.right = rightRotation(node.right);
  135. node = leftRotation(node);
  136. }else if(node.right.left == null || node.right.left.h <= node.right.right.h){
  137. Node newnode = node.right;
  138. newnode.father = node.father;
  139. node.right = newnode.left;
  140. if(node.right != null)
  141. node.right.father = node;
  142. node.h = height(node.left, node.right)+1;
  143. node.father = newnode;
  144. node.balance = balance(node.left, node.right);
  145. newnode.left = node;
  146. node = newnode;
  147. node.balance = balance(node.left, node.right);
  148. node.h = height(node.left, node.right)+1;
  149. }else{
  150. node.right = rightRotation(node.right);
  151. node = leftRotation(node);
  152. }
  153. return node;
  154. }
  155. private Node rightRotation(Node node){
  156. if(node.left.right != null && node.left.left == null){
  157. node.left = leftRotation(node.left);
  158. node = rightRotation(node);
  159. }else if(node.left.right == null || node.left.right.h <= node.left.left.h){
  160. Node newnode = node.left;
  161. newnode.father = node.father;
  162. node.left = newnode.right;
  163. if(node.left != null)
  164. node.left.father = node;
  165. node.h = height(node.left, node.right)+1;
  166. node.father = newnode;
  167. node.balance = balance(node.left, node.right);
  168. newnode.right = node;
  169. node = newnode;
  170. node.balance = balance(node.left, node.right);
  171. node.h = height(node.left, node.right)+1;
  172. }else{
  173. node.left = leftRotation(node.left);
  174. node = rightRotation(node);
  175. }
  176. return node;
  177. }
  178.  
  179. public void add(Key key, Value value) {
  180. root = add(root, key, value, null);
  181. }
  182.  
  183. private Node delete(Node node, Key key){
  184. if(node == null) return null;
  185. int compareResult = key.compareTo(node.key);
  186. if(compareResult > 0){
  187. node.right = delete(node.right, key);
  188. }else if(compareResult < 0){
  189. node.left = delete(node.left, key);
  190. }else{
  191. if(node.right == null && node.left == null){
  192. node = null;
  193. }else if(node.right == null){
  194. node.left.father = node.father;
  195. node = node.left;
  196. }else if(node.left == null){
  197. node.right.father = node.father;
  198. node = node.right;
  199. }else{
  200. if(node.right.left == null){
  201. node.right.left = node.left;
  202. node.right.father = node.father;
  203. node.right.father = node.father;
  204. node.left.father = node.right;
  205. node = node.right;
  206. }else{
  207. Node res = min(node.right);
  208. node.key = res.key;
  209. node.value = res.value;
  210. delete(node.right, node.key);
  211. }
  212. }
  213. }
  214. if(node != null) {
  215. node.h = height(node.left, node.right) + 1;
  216. node.balance = balance(node.left, node.right);
  217. if (node.balance == -2) {
  218. node = leftRotation(node);
  219. } else if (node.balance == 2) {
  220. node = rightRotation(node);
  221. }
  222. }
  223. return node;
  224. }
  225.  
  226. public void delete(Key key) {
  227. root = delete(root, key);
  228. }
  229.  
  230. public Key minKey(){
  231. return min(root).key;
  232. }
  233.  
  234. public Key maxKey(){
  235. return max(root).key;
  236. }
  237.  
  238. private Node min(Node node){
  239. if(node.left == null) return node;
  240. return min(node.left);
  241. }
  242.  
  243. private Node max(Node node){
  244. if(node.right == null) return node;
  245. return min(node.right);
  246. }
  247.  
  248. private Value get(Node node, Key key){
  249. if(node == null) return null;
  250. int compareResult = key.compareTo(node.key);
  251. if(compareResult == 0){
  252. return node.value;
  253. }else if(compareResult > 0){
  254. return get(node.right, key);
  255. }else{
  256. return get(node.left, key);
  257. }
  258. }
  259.  
  260. public Value get(Key key) {
  261. return get(root, key);
  262. }
  263.  
  264. private void print(Node node, int level) {
  265. if (node != null) {
  266. print(node.right,level+1);
  267. for (int i=0;i<level;i++) {
  268. System.out.print("\t");
  269. }
  270. System.out.println(node.key + "->" + node.value+" h="+node.h+" balance="+node.balance);
  271. print(node.left,level+1);
  272. }
  273. }
  274.  
  275. public void print() {
  276. print(root,0);
  277. }
  278.  
  279. }
  280.  
  281.  
  282. class Ideone
  283. {
  284. public static void main (String[] args) throws java.lang.Exception
  285. {
  286. AVL<Integer, Integer> tree = new AVL<>();
  287. tree.add(10,10);
  288. tree.print();
  289. tree.add(11,11);
  290. tree.print();
  291. tree.add(15,12);
  292. tree.print();
  293. tree.add(13,12);
  294. tree.print();
  295. tree.add(16,12);
  296. tree.print();
  297. tree.add(12,12);
  298. tree.print();
  299. tree.add(3,2);
  300. tree.print();
  301. tree.add(1,1);
  302. tree.print();
  303. tree.add(0,1);
  304. tree.print();
  305. tree.add(2,1);
  306. tree.print();
  307. tree.delete(13);
  308. tree.print();
  309. tree.delete(10);
  310. tree.print();
  311. for(AVL.Node e = tree.getFirstNode(); e != null; e = e.next()){
  312. System.out.println(e.key);
  313. }
  314. }
  315. }
Success #stdin #stdout 0.11s 320704KB
stdin
Standard input is empty
stdout
10->10 h=1 balance=0
	11->11 h=1 balance=0
10->10 h=2 balance=-1
	15->12 h=1 balance=0
11->11 h=2 balance=0
	10->10 h=1 balance=0
	15->12 h=2 balance=1
		13->12 h=1 balance=0
11->11 h=3 balance=-1
	10->10 h=1 balance=0
		16->12 h=1 balance=0
	15->12 h=2 balance=0
		13->12 h=1 balance=0
11->11 h=3 balance=-1
	10->10 h=1 balance=0
		16->12 h=1 balance=0
	15->12 h=2 balance=-1
13->12 h=3 balance=0
		12->12 h=1 balance=0
	11->11 h=2 balance=0
		10->10 h=1 balance=0
		16->12 h=1 balance=0
	15->12 h=2 balance=-1
13->12 h=4 balance=1
		12->12 h=1 balance=0
	11->11 h=3 balance=1
		10->10 h=2 balance=1
			3->2 h=1 balance=0
		16->12 h=1 balance=0
	15->12 h=2 balance=-1
13->12 h=4 balance=1
		12->12 h=1 balance=0
	11->11 h=3 balance=1
			10->10 h=1 balance=0
		3->2 h=2 balance=0
			1->1 h=1 balance=0
		16->12 h=1 balance=0
	15->12 h=2 balance=-1
13->12 h=4 balance=1
			12->12 h=1 balance=0
		11->11 h=2 balance=0
			10->10 h=1 balance=0
	3->2 h=3 balance=0
		1->1 h=2 balance=1
			0->1 h=1 balance=0
		16->12 h=1 balance=0
	15->12 h=2 balance=-1
13->12 h=4 balance=1
			12->12 h=1 balance=0
		11->11 h=2 balance=0
			10->10 h=1 balance=0
	3->2 h=3 balance=0
			2->1 h=1 balance=0
		1->1 h=2 balance=0
			0->1 h=1 balance=0
		16->12 h=1 balance=0
	15->12 h=3 balance=1
			12->12 h=1 balance=0
		11->11 h=2 balance=0
			10->10 h=1 balance=0
3->2 h=4 balance=-1
		2->1 h=1 balance=0
	1->1 h=2 balance=0
		0->1 h=1 balance=0
		16->12 h=1 balance=0
	15->12 h=3 balance=1
			12->12 h=1 balance=0
		11->11 h=2 balance=-1
3->2 h=4 balance=-1
		2->1 h=1 balance=0
	1->1 h=2 balance=0
		0->1 h=1 balance=0
0
1
2
3
11
12
15
16