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;
}
}