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

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
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;
}
}