Advertisement
Guest User

Untitled

a guest
Apr 24th, 2019
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.56 KB | None | 0 0
  1. import java.util.Scanner;
  2.  
  3. public class Main {
  4.  
  5. public static void main(String[] args) {
  6. Scanner in = new Scanner(System.in);
  7. int jack = in.nextInt();
  8. int jill = in.nextInt();
  9. int cd;
  10. AVL tree = new AVL();
  11. int counter = 0;
  12.  
  13. while (jack!=0 && jill!=0) {
  14. for (int i = 0; i < jack; i++) {
  15. cd = in.nextInt();
  16. tree.root = tree.insert(tree.root, cd);
  17. }
  18.  
  19. for (int i = 0; i < jill; i++) {
  20. cd = in.nextInt();
  21. boolean finded = tree.find(tree.root, cd);
  22. if (finded == true) {
  23. counter++;
  24. } else {
  25. tree.root = tree.insert(tree.root, cd);
  26. }
  27. }
  28.  
  29. System.out.println(counter);
  30.  
  31. counter = 0;
  32.  
  33. jack = in.nextInt();
  34. jill = in.nextInt();
  35.  
  36.  
  37. }
  38. }
  39. }
  40.  
  41. class BSTNode{
  42. int number;
  43. int height;
  44. BSTNode left;
  45. BSTNode right;
  46.  
  47.  
  48. BSTNode(int num){
  49. this.number = num;
  50. this.left = null;
  51. this.right = null;
  52. this.height = 0;
  53. }
  54.  
  55.  
  56. }
  57.  
  58. class AVL{
  59. BSTNode root;
  60.  
  61. AVL(){
  62. this.root = null;
  63. }
  64.  
  65. public BSTNode insert(BSTNode rt,int num){
  66.  
  67. if (rt==null){
  68. BSTNode node = new BSTNode(num);
  69. return node;
  70. }
  71. if (num<rt.number){
  72. rt.left = insert(rt.left, num);
  73. }else if (num>rt.number){
  74. rt.right = insert(rt.right, num);
  75. }else{
  76. rt.right = insert(rt.right, num);
  77. }
  78.  
  79. rt.height = 1 + Math.max(getHeight(rt.left), getHeight(rt.right));
  80. int balance = getBalance(rt);
  81.  
  82. if (balance > 1 && num < rt.left.number) {
  83. return rightRotate(rt);
  84. }else if (balance >1 && num >= rt.left.number) {
  85. rt.left = leftRotate(rt.left);
  86. return rightRotate(rt);
  87.  
  88. }else if (balance < -1 && num >= rt.right.number) {
  89. return leftRotate(rt);
  90. }else if (balance <-1 && num <rt.right.number) {
  91. rt.right = rightRotate(rt.right);
  92. return leftRotate(rt);
  93. }
  94.  
  95. return rt;
  96.  
  97. }
  98.  
  99.  
  100. public int getBalance(BSTNode rt){
  101. if (rt == null){
  102. return 0;
  103. }
  104. return getHeight(rt.left) - getHeight(rt.right);
  105. }
  106.  
  107. public int getHeight(BSTNode rt){
  108. if (rt==null){
  109. return -1;
  110. }else{
  111. return rt.height;
  112. }
  113. }
  114.  
  115. public BSTNode leftRotate(BSTNode rt){
  116.  
  117. BSTNode r = rt.right;
  118. BSTNode rl = r.left;
  119. r.left = rt;
  120. rt.right = rl;
  121. rt.height = Math.max(getHeight(rt.left), getHeight(rt.right)) + 1;
  122. r.height = Math.max(r.left.height, r.right.height) + 1;
  123.  
  124. return r;
  125. }
  126.  
  127.  
  128. public BSTNode rightRotate(BSTNode rt){
  129.  
  130. BSTNode l = rt.left;
  131. BSTNode lr = l.right;
  132. l.right = rt;
  133. rt.left = lr;
  134. rt.height = Math.max(getHeight(rt.left), getHeight(rt.right)) + 1;
  135. l.height = Math.max(getHeight(l.left),getHeight(l.right.left)) + 1;
  136. return l;
  137. }
  138.  
  139. public boolean find (BSTNode rt, int num){
  140. if (rt==null){
  141. return false;
  142. }else if(rt.number==num){
  143. return true;
  144. }else if (num<rt.number){
  145. return find(rt.left, num);
  146. }else {
  147. return find(rt.right, num);
  148. }
  149. }
  150.  
  151. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement