Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Scanner;
- public class Main {
- public static void main(String[] args) {
- Scanner in = new Scanner(System.in);
- int jack = in.nextInt();
- int jill = in.nextInt();
- int cd;
- AVL tree = new AVL();
- int counter = 0;
- while (jack!=0 && jill!=0) {
- for (int i = 0; i < jack; i++) {
- cd = in.nextInt();
- tree.root = tree.insert(tree.root, cd);
- }
- for (int i = 0; i < jill; i++) {
- cd = in.nextInt();
- boolean finded = tree.find(tree.root, cd);
- if (finded == true) {
- counter++;
- } else {
- tree.root = tree.insert(tree.root, cd);
- }
- }
- System.out.println(counter);
- counter = 0;
- jack = in.nextInt();
- jill = in.nextInt();
- }
- }
- }
- class BSTNode{
- int number;
- int height;
- BSTNode left;
- BSTNode right;
- BSTNode(int num){
- this.number = num;
- this.left = null;
- this.right = null;
- this.height = 0;
- }
- }
- class AVL{
- BSTNode root;
- AVL(){
- this.root = null;
- }
- public BSTNode insert(BSTNode rt,int num){
- if (rt==null){
- BSTNode node = new BSTNode(num);
- return node;
- }
- if (num<rt.number){
- rt.left = insert(rt.left, num);
- }else if (num>rt.number){
- rt.right = insert(rt.right, num);
- }else{
- rt.right = insert(rt.right, num);
- }
- rt.height = 1 + Math.max(getHeight(rt.left), getHeight(rt.right));
- int balance = getBalance(rt);
- if (balance > 1 && num < rt.left.number) {
- return rightRotate(rt);
- }else if (balance >1 && num >= rt.left.number) {
- rt.left = leftRotate(rt.left);
- return rightRotate(rt);
- }else if (balance < -1 && num >= rt.right.number) {
- return leftRotate(rt);
- }else if (balance <-1 && num <rt.right.number) {
- rt.right = rightRotate(rt.right);
- return leftRotate(rt);
- }
- return rt;
- }
- public int getBalance(BSTNode rt){
- if (rt == null){
- return 0;
- }
- return getHeight(rt.left) - getHeight(rt.right);
- }
- public int getHeight(BSTNode rt){
- if (rt==null){
- return -1;
- }else{
- return rt.height;
- }
- }
- public BSTNode leftRotate(BSTNode rt){
- BSTNode r = rt.right;
- BSTNode rl = r.left;
- r.left = rt;
- rt.right = rl;
- rt.height = Math.max(getHeight(rt.left), getHeight(rt.right)) + 1;
- r.height = Math.max(r.left.height, r.right.height) + 1;
- return r;
- }
- public BSTNode rightRotate(BSTNode rt){
- BSTNode l = rt.left;
- BSTNode lr = l.right;
- l.right = rt;
- rt.left = lr;
- rt.height = Math.max(getHeight(rt.left), getHeight(rt.right)) + 1;
- l.height = Math.max(getHeight(l.left),getHeight(l.right.left)) + 1;
- return l;
- }
- public boolean find (BSTNode rt, int num){
- if (rt==null){
- return false;
- }else if(rt.number==num){
- return true;
- }else if (num<rt.number){
- return find(rt.left, num);
- }else {
- return find(rt.right, num);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement