- Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathAVLTree.java
More file actions
Latest commit
159 lines (141 loc) · 3.04 KB
/
Copy pathAVLTree.java
File metadata and controls
159 lines (141 loc) · 3.04 KB
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
importjava.io.BufferedWriter;
importjava.io.FileWriter;
importjava.io.IOException;
/**
* The Class that represents an AVL tree.
*/
publicclassAVLTree {
/** The root. */
protectedAVLNoderoot;
/** The comparator. */
protectedComparatorcomp;
/**
* Instantiates a new AVL tree.
*
* @param comp the {@link Comparator} to be used in the tree
*/
publicAVLTree(Comparatorcomp) {
this.root = null;
this.comp = comp;
}
/**
* Gets the root of the tree.
*
* @return the root
*/
publicAVLNodegetRoot(){
returnthis.root;
}
/**
* Adds a new Node into the tree.
*
* @param key the key of the new node
* @param data the data of the new node
*/
publicvoidadd(Objectkey,Objectdata){
if (isEmpty()){
this.root = newAVLNode(key,data,comp);
}
else{
root = this.root.add(key,data);
}
}
/**
* Removes a node n from the tree where n.key is equal (by {@link Comparator}) to the given key.
*
* @param key the key
*/
publicvoidremove(Objectkey){
if (isEmpty()){
return;
}
else
root = this.root.remove(key);
}
/**
* Finds a node n from the tree where n.key is equal (by {@link Comparator}) to the given key.
*
* @param key the key
* @return the data of the found node, null if node isn't found
*/
publicObjectfind(Objectkey){
if (isEmpty()){
returnnull;
}
else
returnthis.root.find(key);
}
/**
* Finds a node n from the tree where n is the K'th element in the in-Order sequence of the tree.
*
* @param k a number between 1 and {@link #size()}
* @return the data of the found node, null if node isn't found
*/
publicObjectfindKthElement(intk){
if (isEmpty()){
returnnull;
}
else
returnthis.root.findKthElement(k);
}
/**
* Gets all the elements in the tree that are between the K'th element and the H'th element (in the in-Order sequence).
*
* @param k A number between 1 and {@link #size()}
* @param h A number between k and {@link #size()}
* @return the elements in the tree between the arguments
*/
publicLinkedListgetKthTillHth(intk,inth) {
if (isEmpty())
returnnewLinkedList();
returnroot.getKthTillHth(k,h);
}
/**
* Print the tree in an in-order to a dot file format.
*/
publicvoidtoDotFile(Stringfilename){
if (root == null)
return;
StringBuildersb = newStringBuilder();
sb.append("digraph Blahblah{\n");
sb.append("{rank = same ; \""+root.getKey()+"\"};\n");
root.inOrderToString(sb);
sb.append("}");
try {
BufferedWriterout = newBufferedWriter(newFileWriter(filename));
out.write(sb.toString());
out.close();
}catch (IOExceptione) {
e.printStackTrace();
}
}
/**
* Size of the tree.
*
* @return the int
*/
publicintsize(){
if (isEmpty())
return0;
returnroot.size();
}
/**
* Height of the tree.
*
* @return the int
*/
publicintheight(){
if (isEmpty()){
return0;
}
returnroot.height();
}
/**
* Checks if the tree is empty.
*
* @return true, if is empty
*/
publicbooleanisEmpty(){
returnthis.root == null;
}
}