Database Operations on a Binary Search Tree (Java)
aggOut.txt
Results for aggregate operation number 1 Filter: true Aggregate expression: pid Operator: min Result is aardsda01 Results for aggregate operation number 2 Filter: true Aggregate expression: year Operator: min Result is 1980.00000 Results for aggregate operation number 3 Filter: true Aggregate expression: team Operator: min Result is ANA Results for aggregate operation number 4 Filter: true Aggregate expression: league Operator: min Result is AL Results for aggregate operation number 5 Filter: true Aggregate expression: ab Operator: min Result is 1.00000 Results for aggregate operation number 6 Filter: true Aggregate expression: h Operator: min Result is 0.00000 Results for aggregate operation number 7 Filter: true Aggregate expression: b2 Operator: min Result is 0.00000 Results for aggregate operation number 8 Filter: true Aggregate expression: b3 Operator: min Result is 0.00000 Results for aggregate operation number 9 Filter: true Aggregate expression: hr Operator: min Result is 0.00000 Results for aggregate operation number 10 Filter: true Aggregate expression: rbi Operator: min Result is 0.00000 Results for aggregate operation number 11 Filter: true Aggregate expression: bb Operator: min Result is 0.00000 Results for aggregate operation number 12 Filter: true Aggregate expression: so Operator: min Result is 0.00000 Results for aggregate operation number 13 Filter: true Aggregate expression: hbp Operator: min Result is 0.00000 Results for aggregate operation number 14 Filter: true Aggregate expression: sf Operator: min Result is 0.00000 Results for aggregate operation number 15 Filter: true Aggregate expression: pid Operator: max Result is zuvelpa01 Results for aggregate operation number 16 Filter: true Aggregate expression: year Operator: max Result is 2018.00000 Results for aggregate operation number 17 Filter: true Aggregate expression: team Operator: max Result is WAS Results for aggregate operation number 18 Filter: true Aggregate expression: league Operator: max Result is NL Results for aggregate operation number 19 Filter: true Aggregate expression: hr Operator: max Result is 73.00000 Results for aggregate operation number 20 Filter: true Aggregate expression: ab Operator: max Result is 716.00000 Results for aggregate operation number 21 Filter: true Aggregate expression: h Operator: max Result is 262.00000 Results for aggregate operation number 22 Filter: true Aggregate expression: b2 Operator: max Result is 59.00000 Results for aggregate operation number 23 Filter: true Aggregate expression: b3 Operator: max Result is 23.00000 Results for aggregate operation number 24 Filter: true Aggregate expression: hr Operator: max Result is 73.00000 Results for aggregate operation number 25 Filter: true Aggregate expression: rbi Operator: max Result is 165.00000 Results for aggregate operation number 26 Filter: true Aggregate expression: bb Operator: max Result is 232.00000 Results for aggregate operation number 27 Filter: true Aggregate expression: so Operator: max Result is 223.00000 Results for aggregate operation number 28 Filter: true Aggregate expression: hbp Operator: max Result is 35.00000 Results for aggregate operation number 29 Filter: true Aggregate expression: sf Operator: max Result is 18.00000 Results for aggregate operation number 30 Filter: true Aggregate expression: ab Operator: avg Result is 169.25730 Results for aggregate operation number 31 Filter: true Aggregate expression: h Operator: avg Result is 44.15301 Results for aggregate operation number 32 Filter: true Aggregate expression: b2 Operator: avg Result is 8.39600 Results for aggregate operation number 33 Filter: true Aggregate expression: b3 Operator: avg Result is 0.97788 Results for aggregate operation number 34 Filter: true Aggregate expression: hr Operator: avg Result is 4.82298 Results for aggregate operation number 35 Filter: true Aggregate expression: rbi Operator: avg Result is 21.23121 Results for aggregate operation number 36 Filter: true Aggregate expression: bb Operator: avg Result is 16.20344 Results for aggregate operation number 37 Filter: true Aggregate expression: so Operator: avg Result is 32.02825 Results for aggregate operation number 38 Filter: true Aggregate expression: hbp Operator: avg Result is 1.44953 Results for aggregate operation number 39 Filter: true Aggregate expression: sf Operator: avg Result is 1.40334 Results for aggregate operation number 40 Filter: year = 2018.0 Aggregate expression: ab Operator: avg Result is 156.20397 Results for aggregate operation number 41 Filter: year = 2018.0 Aggregate expression: h Operator: avg Result is 38.73371 Results for aggregate operation number 42 Filter: year = 2018.0 Aggregate expression: b2 Operator: avg Result is 7.80453 Results for aggregate operation number 43 Filter: year = 2018.0 Aggregate expression: b3 Operator: avg Result is 0.79981 Results for aggregate operation number 44 Filter: year = 2018.0 Aggregate expression: hr Operator: avg Result is 5.27384 Results for aggregate operation number 45 Filter: year = 2018.0 Aggregate expression: rbi Operator: avg Result is 19.45798 Results for aggregate operation number 46 Filter: year = 2018.0 Aggregate expression: bb Operator: avg Result is 14.81020 Results for aggregate operation number 47 Filter: year = 2018.0 Aggregate expression: so Operator: avg Result is 38.91029 Results for aggregate operation number 48 Filter: year = 2018.0 Aggregate expression: hbp Operator: avg Result is 1.81398 Results for aggregate operation number 49 Filter: year = 2018.0 Aggregate expression: sf Operator: avg Result is 1.16619 Results for aggregate operation number 50 Filter: (team = 'BOS') & (year = 2018.0) Aggregate expression: hr Operator: max Result is 43.00000 Results for aggregate operation number 51 Filter: (team = 'BOS') & (year = 2018.0) Aggregate expression: ab Operator: max Result is 579.00000 Results for aggregate operation number 52 Filter: (team = 'BOS') & (year = 2018.0) Aggregate expression: h Operator: max Result is 188.00000 Results for aggregate operation number 53 Filter: (team = 'BOS') & (year = 2018.0) Aggregate expression: b2 Operator: max Result is 47.00000 Results for aggregate operation number 54 Filter: (team = 'BOS') & (year = 2018.0) Aggregate expression: b3 Operator: max Result is 6.00000 Results for aggregate operation number 55 Filter: (team = 'BOS') & (year = 2018.0) Aggregate expression: hr Operator: max Result is 43.00000 Results for aggregate operation number 56 Filter: (team = 'BOS') & (year = 2018.0) Aggregate expression: rbi Operator: max Result is 130.00000 Results for aggregate operation number 57 Filter: (team = 'BOS') & (year = 2018.0) Aggregate expression: bb Operator: max Result is 81.00000 Results for aggregate operation number 58 Filter: (team = 'BOS') & (year = 2018.0) Aggregate expression: so Operator: max Result is 146.00000 Results for aggregate operation number 59 Filter: (team = 'BOS') & (year = 2018.0) Aggregate expression: hbp Operator: max Result is 11.00000 Results for aggregate operation number 60 Filter: (team = 'BOS') & (year = 2018.0) Aggregate expression: sf Operator: max Result is 7.00000 Results for aggregate operation number 61 Filter: (team = 'BOS') & (year = 2018.0) Aggregate expression: ab Operator: avg Result is 208.25926 Results for aggregate operation number 62 Filter: (team = 'BOS') & (year = 2018.0) Aggregate expression: h Operator: avg Result is 55.88889 Results for aggregate operation number 63 Filter: (team = 'BOS') & (year = 2018.0) Aggregate expression: b2 Operator: avg Result is 13.14815 Results for aggregate operation number 64 Filter: (team = 'BOS') & (year = 2018.0) Aggregate expression: b3 Operator: avg Result is 1.14815 Results for aggregate operation number 65 Filter: (team = 'BOS') & (year = 2018.0) Aggregate expression: hr Operator: avg Result is 7.70370 Results for aggregate operation number 66 Filter: (team = 'BOS') & (year = 2018.0) Aggregate expression: rbi Operator: avg Result is 30.70370 Results for aggregate operation number 67 Filter: (team = 'BOS') & (year = 2018.0) Aggregate expression: bb Operator: avg Result is 21.07407 Results for aggregate operation number 68 Filter: (team = 'BOS') & (year = 2018.0) Aggregate expression: so Operator: avg Result is 46.40741 Results for aggregate operation number 69 Filter: (team = 'BOS') & (year = 2018.0) Aggregate expression: hbp Operator: avg Result is 2.03704 Results for aggregate operation number 70 Filter: (team = 'BOS') & (year = 2018.0) Aggregate expression: sf Operator: avg Result is 1.77778 Results for aggregate operation number 71 Filter: team = 'BOS' Aggregate expression: ab Operator: avg Result is 202.26905 Results for aggregate operation number 72 Filter: team = 'BOS' Aggregate expression: h Operator: avg Result is 55.34713 Results for aggregate operation number 73 Filter: team = 'BOS' Aggregate expression: b2 Operator: avg Result is 11.53622 Results for aggregate operation number 74 Filter: team = 'BOS' Aggregate expression: b3 Operator: avg Result is 1.05644 Results for aggregate operation number 75 Filter: team = 'BOS' Aggregate expression: hr Operator: avg Result is 6.10724 Results for aggregate operation number 76 Filter: team = 'BOS' Aggregate expression: rbi Operator: avg Result is 27.67357 Results for aggregate operation number 77 Filter: team = 'BOS' Aggregate expression: bb Operator: avg Result is 20.85042 Results for aggregate operation number 78 Filter: team = 'BOS' Aggregate expression: so Operator: avg Result is 35.62559 Results for aggregate operation number 79 Filter: team = 'BOS' Aggregate expression: hbp Operator: avg Result is 1.84008 Results for aggregate operation number 80 Filter: team = 'BOS' Aggregate expression: sf Operator: avg Result is 1.82502 Results for aggregate operation number 81 Filter: ((year = 2018.0) & (team = 'BOS')) & (ab >= 100.0) Aggregate expression: h / ab Operator: max Result is 0.34615 Results for aggregate operation number 82 Filter: ((year = 2018.0) & (team = 'BOS')) & (ab >= 25.0) Aggregate expression: h / ab Operator: avg Result is 0.25732 Results for aggregate operation number 83 Filter: ((year = 2018.0) & (team = 'BOS')) & (hr >= 10.0) Aggregate expression: hr / so Operator: max Result is 0.35165 Results for aggregate operation number 84 Filter: ((year = 2018.0) & (team = 'BOS')) & (hr >= 10.0) Aggregate expression: hr / so Operator: avg Result is 0.19788 Results for aggregate operation number 85 Filter: ((year = 2018.0) & (team = 'BOS')) & (hr >= 15.0) Aggregate expression: hr Operator: max Result is 43.00000 Results for aggregate operation number 86 Filter: ((year = 2018.0) & (team = 'BOS')) & (hr >= 15.0) Aggregate expression: 1.0 Operator: sum Result is 6.00000 Results for aggregate operation number 87 Filter: ((year = 2018.0) & (team = 'BOS')) & (ab >= 100.0) Aggregate expression: ((h + bb) + hbp) / (((ab + bb) + hbp) + sf) Operator: max Result is 0.43811 Results for aggregate operation number 88 Filter: ((year = 2018.0) & (team = 'BOS')) & (ab >= 100.0) Aggregate expression: ((h + bb) + hbp) / (((ab + bb) + hbp) + sf) Operator: avg Result is 0.32862 Results for aggregate operation number 89 Filter: ((year = 2018.0) & (team = 'BOS')) & (ab >= 100.0) Aggregate expression: (so * 1000.0) + h Operator: min Result is 24032.00000 Results for aggregate operation number 90 Filter: (((year = 2018.0) & (team = 'BOS')) & (ab >= 100.0)) & (hr >= 20.0) Aggregate expression: 1.0 Operator: count Result is 4 Results for aggregate operation number 91 Filter: (((year = 2018.0) & (team = 'BOS')) & (ab >= 100.0)) & (rbi >= 90.0) Aggregate expression: 1.0 Operator: count Result is 2
aggregateExprs.txt
true pid 0 true year 0 true team 0 true league 0 true ab 0 true h 0 true b2 0 true b3 0 true hr 0 true rbi 0 true bb 0 true so 0 true hbp 0 true sf 0 true pid 1 true year 1 true team 1 true league 1 true hr 1 true ab 1 true h 1 true b2 1 true b3 1 true hr 1 true rbi 1 true bb 1 true so 1 true hbp 1 true sf 1 true ab 3 true h 3 true b2 3 true b3 3 true hr 3 true rbi 3 true bb 3 true so 3 true hbp 3 true sf 3 year = 2018 ab 3 year = 2018 h 3 year = 2018 b2 3 year = 2018 b3 3 year = 2018 hr 3 year = 2018 rbi 3 year = 2018 bb 3 year = 2018 so 3 year = 2018 hbp 3 year = 2018 sf 3 team = "BOS" & year = 2018 hr 1 team = "BOS" & year = 2018 ab 1 team = "BOS" & year = 2018 h 1 team = "BOS" & year = 2018 b2 1 team = "BOS" & year = 2018 b3 1 team = "BOS" & year = 2018 hr 1 team = "BOS" & year = 2018 rbi 1 team = "BOS" & year = 2018 bb 1 team = "BOS" & year = 2018 so 1 team = "BOS" & year = 2018 hbp 1 team = "BOS" & year = 2018 sf 1 team = "BOS" & year = 2018 ab 3 team = "BOS" & year = 2018 h 3 team = "BOS" & year = 2018 b2 3 team = "BOS" & year = 2018 b3 3 team = "BOS" & year = 2018 hr 3 team = "BOS" & year = 2018 rbi 3 team = "BOS" & year = 2018 bb 3 team = "BOS" & year = 2018 so 3 team = "BOS" & year = 2018 hbp 3 team = "BOS" & year = 2018 sf 3 team = "BOS" ab 3 team = "BOS" h 3 team = "BOS" b2 3 team = "BOS" b3 3 team = "BOS" hr 3 team = "BOS" rbi 3 team = "BOS" bb 3 team = "BOS" so 3 team = "BOS" hbp 3 team = "BOS" sf 3 year = 2018 & team = "BOS" & ab >= 100 h/ab 1 year = 2018 & team = "BOS" & ab >= 25 h/ab 3 year = 2018 & team = "BOS" & hr >= 10 hr / so 1 year = 2018 & team = "BOS" & hr >= 10 hr/so 3 year = 2018 & team = "BOS" & hr >= 15 hr 1 year = 2018 & team = "BOS" & hr >= 15 1 4 year = 2018 & team = "BOS" & ab >= 100 (h + bb + hbp)/(ab + bb + hbp + sf) 1 year = 2018 & team = "BOS" & ab >= 100 (h + bb + hbp)/(ab + bb + hbp + sf) 3 year = 2018 & team = "BOS" & ab >= 100 so * 1000 + h 0 year = 2018 & team = "BOS" & ab >= 100 & hr >= 20 1 2 year = 2018 & team = "BOS" & ab >= 100 & rbi >= 90 1 2
BinarySearchTree.java
BinarySearchTree.java
/*
A modified version of the generic BinarySearchTree class for the
database project
Note, the empty tree as an object will have rootOfSubtree == null;
*/
import
java
.
util
.
List
;
import
java
.
util
.
ListIterator
;
import
java
.
util
.
LinkedList
;
public
class
BinarySearchTree
<
T
extends
Comparable
<
T
>
&
DBRecord
>
{
// all of these will be null if the tree is empty
private
T rootOfSubtree
;
private
BinarySearchTree
<
T
>
left
,
right
,
parent
;
// creates the empty tree
public
BinarySearchTree
()
{
}
// create a one node tree
public
BinarySearchTree
(
T x
)
throws
Exception
{
// do not allow the insertion of null
if
(
x
==
null
)
throw
new
Exception
(
"attempt to create a tree with null root"
);
rootOfSubtree
=
x
;
// links are already null
}
// perform the insert, preserving the ordering property that
// is the characteristic of a binary search tree;
// return true if the insert is accomplished, else false
public
boolean
insert
(
T x
)
throws
Exception
{
// do not allow the insertion of null
if
(
x
==
null
)
throw
new
Exception
(
"attempt to create a tree with null root"
);
if
(
rootOfSubtree
==
null
)
{
// the tree is empty
// and all the links are empty
rootOfSubtree
=
x
;
return
true
;
}
else
{
int
compResult
=
rootOfSubtree
.
compareTo
(
x
);
BinarySearchTree
<
T
>
aux
;
if
(
compResult
==
0
)
// x already in the tree
return
false
;
else
if
(
compResult
<
0
)
// x > rootOfSubtree
if
(
right
==
null
)
{
// hang a new node on the right
aux
=
new
BinarySearchTree
<
T
>
(
x
);
right
=
aux
;
aux
.
parent
=
this
;
}
else
return
right
.
insert
(
x
);
else
// x < rootOfSubtree
if
(
left
==
null
)
{
// hang a new node on the left
aux
=
new
BinarySearchTree
<
T
>
(
x
);
left
=
aux
;
aux
.
parent
=
this
;
}
else
return
left
.
insert
(
x
);
// if control gets here, the insert happened
return
true
;
}
}
/*
if the tree rooted at this node has a node with x,
delete it from the tree and return true, else
return false;
*****************************************************/
public
boolean
delete
(
T x
)
{
// do the easy cases first
if
(
rootOfSubtree
==
null
)
// the tree is empty
return
false
;
else
{
int
compResult
=
rootOfSubtree
.
compareTo
(
x
);
if
(
compResult
<
0
)
// rootOfSubtree < x
if
(
right
==
null
)
// not in the tree
return
false
;
else
return
right
.
delete
(
x
);
else
if
(
compResult
>
0
)
// x < rootOfSubtree
if
(
left
==
null
)
// not in the tree
return
false
;
else
return
left
.
delete
(
x
);
else
{
// rootOfSubtree = x; note, this node may not be the root
// of the whole tree, but this is the node with
// the value that must be deleted
if
(
left
==
null
)
if
(
right
==
null
)
// both subT's are null; this
// is a leaf node
if
(
parent
==
null
)
// the last node of the tree!
rootOfSubtree
=
null
;
else
{
// still a leaf, but has a parent
if
(
parent
.
left
==
this
)
// deleting a leaf from
// the parent's left
parent
.
left
=
null
;
else
// must be parent's right subtree is this leaf
parent
.
right
=
null
;
}
else
{
// left subtree is null, so promote the right
if
(
parent
==
null
){
// this is the root of the whole tree
rootOfSubtree
=
right
.
rootOfSubtree
;
left
=
right
.
left
;
right
=
right
.
right
;
}
else
{
right
.
parent
=
parent
;
if
(
parent
.
left
==
this
)
parent
.
left
=
right
;
else
parent
.
right
=
right
;
}
}
else
// left subtree of this is NOT null
if
(
right
==
null
)
{
// right subtree is null, left not, promote the left
if
(
parent
==
null
){
// this is the root of the whole tree
rootOfSubtree
=
left
.
rootOfSubtree
;
left
=
left
.
left
;
right
=
left
.
right
;
}
else
{
left
.
parent
=
parent
;
if
(
parent
.
left
==
this
)
parent
.
left
=
left
;
else
parent
.
right
=
left
;
}
}
else
{
// gulp! neither is null; just have to roll up our
// sleeves and do it!
boolean
goLeft
=
Math
.
random
()
<
0.5
;
T valToDelete
;
if
(
goLeft
)
{
// tricksy Hobbitses!! these recursive calls make
// it easy cheesy!!
valToDelete
=
left
.
maximum
();
left
.
delete
(
valToDelete
);
rootOfSubtree
=
valToDelete
;
}
else
{
valToDelete
=
right
.
minimum
();
right
.
delete
(
valToDelete
);
rootOfSubtree
=
valToDelete
;
}
}
// if control gets here, the delete took place
return
true
;
}
}
}
// return true when this object is the empty tree
public
boolean
isEmpty
()
{
return
rootOfSubtree
==
null
;
}
// return the value at the root, which may be null if
// this is the empty tree
public
T getRoot
(){
return
rootOfSubtree
;
}
/*
return the left subtree if this is not the empty
tree, or throw an exception if it is the empty tree
***********************************************************/
public
BinarySearchTree
<
T
>
getLeft
()
throws
Exception
{
if
(
rootOfSubtree
==
null
)
throw
new
Exception
(
"getLeft called on empty tree"
);
else
return
left
;
}
/*
return the right subtree if this is not the empty
tree, or throw an exception if it is the empty tree
***********************************************************/
public
BinarySearchTree
<
T
>
getRight
()
throws
Exception
{
if
(
rootOfSubtree
==
null
)
throw
new
Exception
(
"getRight called on empty tree"
);
else
return
right
;
}
// returns null when x is not in the tree, else the value
// stored in the tree that matches x
public
T lookup
(
T x
)
{
if
(
rootOfSubtree
==
null
)
// empty tree
return
null
;
else
{
int
compResult
=
rootOfSubtree
.
compareTo
(
x
);
if
(
compResult
<
0
)
// rootOfSubtree < x
if
(
right
==
null
)
return
null
;
else
return
right
.
lookup
(
x
);
else
if
(
compResult
>
0
)
// x < rootOfSubtree
if
(
left
==
null
)
return
null
;
else
return
left
.
lookup
(
x
);
else
// as Goldilocks put it so well, "Just right!"
return
rootOfSubtree
;
}
}
// this is straightforward if you think about it
// for a minute
public
T minimum
(){
if
(
rootOfSubtree
==
null
)
return
null
;
else
if
(
left
==
null
)
return
rootOfSubtree
;
else
return
left
.
minimum
();
}
// the mirror image of minimum
public
T maximum
(){
if
(
rootOfSubtree
==
null
)
return
null
;
else
if
(
right
==
null
)
return
rootOfSubtree
;
else
return
right
.
maximum
();
}
// return a list of the nodes in a symmetric(in) order
// traversal
public
List
<
T
>
list
(){
List
<
T
>
aux
;
if
(
rootOfSubtree
==
null
)
// empty list
return
new
LinkedList
<
T
>
();
else
{
if
(
left
==
null
)
if
(
right
==
null
)
{
// one node tree
aux
=
new
LinkedList
<
T
>
();
aux
.
add
(
rootOfSubtree
);
}
else
{
// left null, right not
aux
=
right
.
list
();
aux
.
add
(
0
,
rootOfSubtree
);
}
else
{
// left is not empty
aux
=
left
.
list
();
aux
.
add
(
rootOfSubtree
);
if
(
right
!=
null
)
aux
.
addAll
(
right
.
list
());
}
return
aux
;
}
}
// I will leave these methods in, just in case you want to display
// the tree during development
// returns a string with a list of the values from the tree in their
// sorted order; this does NOT show the tree structure
public
String
toString
()
{
List
<
T
>
ordered
;
if
(
rootOfSubtree
==
null
)
return
"()"
;
else
{
ordered
=
list
();
if
(
ordered
.
size
()
==
1
)
return
"("
+
rootOfSubtree
.
toString
()
+
")"
;
else
{
StringBuilder
bldr
=
new
StringBuilder
();
bldr
.
append
(
'('
);
ListIterator
<
T
>
iter
=
ordered
.
listIterator
();
bldr
.
append
(
iter
.
next
().
toString
());
while
(
iter
.
hasNext
())
{
bldr
.
append
(
", "
);
bldr
.
append
(
iter
.
next
().
toString
());
}
bldr
.
append
(
')'
);
return
bldr
.
toString
();
}
}
}
// to show some differences, we'll do a level by level display, too
private
void
displayLevelByLevel
()
{
List
<
BinarySearchTree
<
T
>>
q
=
new
LinkedList
<
BinarySearchTree
<
T
>>
();
int
nodesOnNextLevel
=
0
,
nodesOnCurrentLevel
,
level
=
0
;
BinarySearchTree
<
T
>
currNode
;
if
(
rootOfSubtree
==
null
)
System
.
out
.
println
(
"the tree is empty"
);
else
{
q
.
add
(
this
);
nodesOnCurrentLevel
=
1
;
while
(
!
q
.
isEmpty
())
{
System
.
out
.
print
(
"Level "
+
level
+
" "
);
while
(
nodesOnCurrentLevel
>
0
)
{
currNode
=
q
.
remove
(
0
);
if
(
currNode
.
left
!=
null
)
{
nodesOnNextLevel
++
;
q
.
add
(
currNode
.
left
);
}
if
(
currNode
.
right
!=
null
)
{
nodesOnNextLevel
++
;
q
.
add
(
currNode
.
right
);