package Level1 import java util Date import java util regex Matcher pu

package Level1;

import java.util.Date;
import java.util.regex.Matcher;

public class BSTRandomize {
class Node{
    Student student;
    Node left;
    Node right;
    int countNodes;

    Node(Student student){
        this.student = student;
    }
}
private Node root;
public void insert (Student newElem){
    root = insertTree(root, newElem);
}
private Node insertTree(Node current, Student newElem){
    if(current == null){
        Node newNode = new Node(newElem);
        newNode.countNodes = 1;
        return newNode;
    }
    if(Math.random()*current.countNodes<1.0){
        current = insertRoot(current, newElem);
    }
    else if(newElem.readerTicket.compareTo(current.student.readerTicket) < 0){
        current.left = insertTree(current.left, newElem);
    }
    else {
        current.right = insertTree(current.right, newElem);
    }
    current.countNodes = count(current);
    return current;
}
private Node insertRoot(Node current, Student newElem){
    if(current == null){
        Node node = new Node(newElem);
        node.countNodes = 1;
        return node;
    }
    if(newElem.readerTicket.compareTo(current.student.readerTicket) < 0){
        current.left = insertRoot(current.left, newElem);
        current.countNodes = current.countNodes - current.left.countNodes;
        current = rotationR(current);
        current.right.countNodes = count(current.right);
    }
    else {
        current.right = insertRoot(current.right, newElem);
        current.countNodes = current.countNodes -current.right.countNodes;
        current = rotationL(current);
        current.left.countNodes = count(current.left);
    }
    current.countNodes = count(current);
    return current;
}
private int count(Node current){
    if (current.left!=null) {
        if (current.right != null)
            current.countNodes = current.left.countNodes + current.right.countNodes;
        else current.countNodes = current.left.countNodes;
    }
    else if(current.right!=null)
        current.countNodes = current.right.countNodes;
    return ++current.countNodes;
    }
    private Node rotationR(Node current){
    Node temp = current.left;
    current.left = temp.right;
    temp.right = current;
    current = temp;
    return current;
}
private Node rotationL(Node current){
    Node temp = current.right;
    current.right = temp.left;
    temp.left = current;
    current = temp;
    return current;
}
public void printBST(){
    print(root);
}
private void print(Node current){
    if(current == null){
        return;
    }
    System.out.println(current.student.lastName +
            " - " + current.student.ticketExpirationDate +
            " - " + current.student.readerTicket +
            " - " + current.student.gender.toString() +
            " - " + current.countNodes);
            print(current.left);
            print(current.right);
}
public void find(Integer key){
    System.out.println("Element with key " + key);
    Node findN = findNode(root, key);
    if(findN == null){
        System.out.println("No elements with such key!");
    }
    else{
        System.out.println(findN.student.lastName +
                " - " + findN.student.ticketExpirationDate +
                " - " + findN.student.readerTicket +
                " - " + findN.student.gender.toString());
    }
}
private Node findNode(Node current, Integer key){
    if(current == null){
        return null;
    }
    if(current.student.readerTicket.compareTo(key)> 0){
        current = findNode(current.left, key);
    } else if(current.student.readerTicket.compareTo(key) < 0){
        current = findNode(current, key);
    }
    else return current;
    return current;
    }
}