java-algorithms/BTree.java at main · rishitydv/java-algorithms · GitHub

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
// Inserting a key on a B-tree in Java

publicclassBTree {

privateintT;

publicclassNode {
intn;
intkey[] = newint[2 * T - 1];
Nodechild[] = newNode[2 * T];
booleanleaf = true;

publicintFind(intk) {
for (inti = 0; i < this.n; i++) {
if (this.key[i] == k) {
returni;
 }
 }
return -1;
 };
 }

publicBTree(intt) {
T = t;
root = newNode();
root.n = 0;
root.leaf = true;
 }

privateNoderoot;

privatevoidsplit(Nodex, intpos, Nodey) {
Nodez = newNode();
z.leaf = y.leaf;
z.n = T - 1;
for (intj = 0; j < T - 1; j++) {
z.key[j] = y.key[j + T];
 }
if (!y.leaf) {
for (intj = 0; j < T; j++) {
z.child[j] = y.child[j + T];
 }
 }
y.n = T - 1;
for (intj = x.n; j >= pos + 1; j--) {
x.child[j + 1] = x.child[j];
 }
x.child[pos + 1] = z;

for (intj = x.n - 1; j >= pos; j--) {
x.key[j + 1] = x.key[j];
 }
x.key[pos] = y.key[T - 1];
x.n = x.n + 1;
 }

publicvoidinsert(finalintkey) {
Noder = root;
if (r.n == 2 * T - 1) {
Nodes = newNode();
root = s;
s.leaf = false;
s.n = 0;
s.child[0] = r;
split(s, 0, r);
_insert(s, key);
 } else {
_insert(r, key);
 }
 }

finalprivatevoid_insert(Nodex, intk) {

if (x.leaf) {
inti = 0;
for (i = x.n - 1; i >= 0 && k < x.key[i]; i--) {
x.key[i + 1] = x.key[i];
 }
x.key[i + 1] = k;
x.n = x.n + 1;
 } else {
inti = 0;
for (i = x.n - 1; i >= 0 && k < x.key[i]; i--) {
 }
 ;
i++;
Nodetmp = x.child[i];
if (tmp.n == 2 * T - 1) {
split(x, i, tmp);
if (k > x.key[i]) {
i++;
 }
 }
_insert(x.child[i], k);
 }

 }

publicvoiddisplay() {
display(root);
 }

privatevoiddisplay(Nodex) {
assert (x == null);
for (inti = 0; i < x.n; i++) {
System.out.print(x.key[i] + " ");
 }
if (!x.leaf) {
for (inti = 0; i < x.n + 1; i++) {
display(x.child[i]);
 }
 }
 }

publicstaticvoidmain(String[] args) {
BTreeb = newBTree(3);
b.insert(8);
b.insert(9);
b.insert(10);
b.insert(11);
b.insert(15);
b.insert(20);
b.insert(17);

b.display();
 }
}