fork(2) 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.  * 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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
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
https://ideone.com/0t9pkZ
language:
Java (12.0.1)
created:
8 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!