Skip to content

Commit 79dcaca

Browse files
Tanmay-Saxena10Tanmay-Saxena10
committed
I have added a deletion program in cpp
1 parent 998dc00 commit 79dcaca

2 files changed

Lines changed: 378 additions & 0 deletions

File tree

‎cpp/Untitled-1.cpp‎

Lines changed: 378 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,378 @@
1+
// Deleting a key from a B-tree in C++
2+
3+
#include <iostream>
4+
using namespace std;
5+
6+
class BTreeNode {
7+
int *keys;
8+
int t;
9+
BTreeNode **C;
10+
int n;
11+
bool leaf;
12+
13+
public:
14+
BTreeNode(int _t, bool _leaf);
15+
16+
void traverse();
17+
18+
int findKey(int k);
19+
void insertNonFull(int k);
20+
void splitChild(int i, BTreeNode *y);
21+
void deletion(int k);
22+
void removeFromLeaf(int idx);
23+
void removeFromNonLeaf(int idx);
24+
int getPredecessor(int idx);
25+
int getSuccessor(int idx);
26+
void fill(int idx);
27+
void borrowFromPrev(int idx);
28+
void borrowFromNext(int idx);
29+
void merge(int idx);
30+
friend class BTree;
31+
};
32+
33+
class BTree {
34+
BTreeNode *root;
35+
int t;
36+
37+
public:
38+
BTree(int _t) {
39+
root = NULL;
40+
t = _t;
41+
}
42+
43+
void traverse() {
44+
if (root != NULL)
45+
root->traverse();
46+
}
47+
48+
void insertion(int k);
49+
50+
void deletion(int k);
51+
};
52+
53+
// B tree node
54+
BTreeNode::BTreeNode(int t1, bool leaf1) {
55+
t = t1;
56+
leaf = leaf1;
57+
58+
keys = new int[2 * t - 1];
59+
C = new BTreeNode *[2 * t];
60+
61+
n = 0;
62+
}
63+
64+
// Find the key
65+
int BTreeNode::findKey(int k) {
66+
int idx = 0;
67+
while (idx < n && keys[idx] < k)
68+
++idx;
69+
return idx;
70+
}
71+
72+
// Deletion operation
73+
void BTreeNode::deletion(int k) {
74+
int idx = findKey(k);
75+
76+
if (idx < n && keys[idx] == k) {
77+
if (leaf)
78+
removeFromLeaf(idx);
79+
else
80+
removeFromNonLeaf(idx);
81+
} else {
82+
if (leaf) {
83+
cout << "The key " << k << " is does not exist in the tree\n";
84+
return;
85+
}
86+
87+
bool flag = ((idx == n) ? true : false);
88+
89+
if (C[idx]->n < t)
90+
fill(idx);
91+
92+
if (flag && idx > n)
93+
C[idx - 1]->deletion(k);
94+
else
95+
C[idx]->deletion(k);
96+
}
97+
return;
98+
}
99+
100+
// Remove from the leaf
101+
void BTreeNode::removeFromLeaf(int idx) {
102+
for (int i = idx + 1; i < n; ++i)
103+
keys[i - 1] = keys[i];
104+
105+
n--;
106+
107+
return;
108+
}
109+
110+
// Delete from non leaf node
111+
void BTreeNode::removeFromNonLeaf(int idx) {
112+
int k = keys[idx];
113+
114+
if (C[idx]->n >= t) {
115+
int pred = getPredecessor(idx);
116+
keys[idx] = pred;
117+
C[idx]->deletion(pred);
118+
}
119+
120+
else if (C[idx + 1]->n >= t) {
121+
int succ = getSuccessor(idx);
122+
keys[idx] = succ;
123+
C[idx + 1]->deletion(succ);
124+
}
125+
126+
else {
127+
merge(idx);
128+
C[idx]->deletion(k);
129+
}
130+
return;
131+
}
132+
133+
int BTreeNode::getPredecessor(int idx) {
134+
BTreeNode *cur = C[idx];
135+
while (!cur->leaf)
136+
cur = cur->C[cur->n];
137+
138+
return cur->keys[cur->n - 1];
139+
}
140+
141+
int BTreeNode::getSuccessor(int idx) {
142+
BTreeNode *cur = C[idx + 1];
143+
while (!cur->leaf)
144+
cur = cur->C[0];
145+
146+
return cur->keys[0];
147+
}
148+
149+
void BTreeNode::fill(int idx) {
150+
if (idx != 0 && C[idx - 1]->n >= t)
151+
borrowFromPrev(idx);
152+
153+
else if (idx != n && C[idx + 1]->n >= t)
154+
borrowFromNext(idx);
155+
156+
else {
157+
if (idx != n)
158+
merge(idx);
159+
else
160+
merge(idx - 1);
161+
}
162+
return;
163+
}
164+
165+
// Borrow from previous
166+
void BTreeNode::borrowFromPrev(int idx) {
167+
BTreeNode *child = C[idx];
168+
BTreeNode *sibling = C[idx - 1];
169+
170+
for (int i = child->n - 1; i >= 0; --i)
171+
child->keys[i + 1] = child->keys[i];
172+
173+
if (!child->leaf) {
174+
for (int i = child->n; i >= 0; --i)
175+
child->C[i + 1] = child->C[i];
176+
}
177+
178+
child->keys[0] = keys[idx - 1];
179+
180+
if (!child->leaf)
181+
child->C[0] = sibling->C[sibling->n];
182+
183+
keys[idx - 1] = sibling->keys[sibling->n - 1];
184+
185+
child->n += 1;
186+
sibling->n -= 1;
187+
188+
return;
189+
}
190+
191+
// Borrow from the next
192+
void BTreeNode::borrowFromNext(int idx) {
193+
BTreeNode *child = C[idx];
194+
BTreeNode *sibling = C[idx + 1];
195+
196+
child->keys[(child->n)] = keys[idx];
197+
198+
if (!(child->leaf))
199+
child->C[(child->n) + 1] = sibling->C[0];
200+
201+
keys[idx] = sibling->keys[0];
202+
203+
for (int i = 1; i < sibling->n; ++i)
204+
sibling->keys[i - 1] = sibling->keys[i];
205+
206+
if (!sibling->leaf) {
207+
for (int i = 1; i <= sibling->n; ++i)
208+
sibling->C[i - 1] = sibling->C[i];
209+
}
210+
211+
child->n += 1;
212+
sibling->n -= 1;
213+
214+
return;
215+
}
216+
217+
// Merge
218+
void BTreeNode::merge(int idx) {
219+
BTreeNode *child = C[idx];
220+
BTreeNode *sibling = C[idx + 1];
221+
222+
child->keys[t - 1] = keys[idx];
223+
224+
for (int i = 0; i < sibling->n; ++i)
225+
child->keys[i + t] = sibling->keys[i];
226+
227+
if (!child->leaf) {
228+
for (int i = 0; i <= sibling->n; ++i)
229+
child->C[i + t] = sibling->C[i];
230+
}
231+
232+
for (int i = idx + 1; i < n; ++i)
233+
keys[i - 1] = keys[i];
234+
235+
for (int i = idx + 2; i <= n; ++i)
236+
C[i - 1] = C[i];
237+
238+
child->n += sibling->n + 1;
239+
n--;
240+
241+
delete (sibling);
242+
return;
243+
}
244+
245+
// Insertion operation
246+
void BTree::insertion(int k) {
247+
if (root == NULL) {
248+
root = new BTreeNode(t, true);
249+
root->keys[0] = k;
250+
root->n = 1;
251+
} else {
252+
if (root->n == 2 * t - 1) {
253+
BTreeNode *s = new BTreeNode(t, false);
254+
255+
s->C[0] = root;
256+
257+
s->splitChild(0, root);
258+
259+
int i = 0;
260+
if (s->keys[0] < k)
261+
i++;
262+
s->C[i]->insertNonFull(k);
263+
264+
root = s;
265+
} else
266+
root->insertNonFull(k);
267+
}
268+
}
269+
270+
// Insertion non full
271+
void BTreeNode::insertNonFull(int k) {
272+
int i = n - 1;
273+
274+
if (leaf == true) {
275+
while (i >= 0 && keys[i] > k) {
276+
keys[i + 1] = keys[i];
277+
i--;
278+
}
279+
280+
keys[i + 1] = k;
281+
n = n + 1;
282+
} else {
283+
while (i >= 0 && keys[i] > k)
284+
i--;
285+
286+
if (C[i + 1]->n == 2 * t - 1) {
287+
splitChild(i + 1, C[i + 1]);
288+
289+
if (keys[i + 1] < k)
290+
i++;
291+
}
292+
C[i + 1]->insertNonFull(k);
293+
}
294+
}
295+
296+
// Split child
297+
void BTreeNode::splitChild(int i, BTreeNode *y) {
298+
BTreeNode *z = new BTreeNode(y->t, y->leaf);
299+
z->n = t - 1;
300+
301+
for (int j = 0; j < t - 1; j++)
302+
z->keys[j] = y->keys[j + t];
303+
304+
if (y->leaf == false) {
305+
for (int j = 0; j < t; j++)
306+
z->C[j] = y->C[j + t];
307+
}
308+
309+
y->n = t - 1;
310+
311+
for (int j = n; j >= i + 1; j--)
312+
C[j + 1] = C[j];
313+
314+
C[i + 1] = z;
315+
316+
for (int j = n - 1; j >= i; j--)
317+
keys[j + 1] = keys[j];
318+
319+
keys[i] = y->keys[t - 1];
320+
321+
n = n + 1;
322+
}
323+
324+
// Traverse
325+
void BTreeNode::traverse() {
326+
int i;
327+
for (i = 0; i < n; i++) {
328+
if (leaf == false)
329+
C[i]->traverse();
330+
cout << " " << keys[i];
331+
}
332+
333+
if (leaf == false)
334+
C[i]->traverse();
335+
}
336+
337+
// Delete Operation
338+
void BTree::deletion(int k) {
339+
if (!root) {
340+
cout << "The tree is empty\n";
341+
return;
342+
}
343+
344+
root->deletion(k);
345+
346+
if (root->n == 0) {
347+
BTreeNode *tmp = root;
348+
if (root->leaf)
349+
root = NULL;
350+
else
351+
root = root->C[0];
352+
353+
delete tmp;
354+
}
355+
return;
356+
}
357+
358+
int main() {
359+
BTree t(3);
360+
t.insertion(8);
361+
t.insertion(9);
362+
t.insertion(10);
363+
t.insertion(11);
364+
t.insertion(15);
365+
t.insertion(16);
366+
t.insertion(17);
367+
t.insertion(18);
368+
t.insertion(20);
369+
t.insertion(23);
370+
371+
cout << "The B-tree is: ";
372+
t.traverse();
373+
374+
t.deletion(20);
375+
376+
cout << "\nThe B-tree is: ";
377+
t.traverse();
378+
}

‎cpp/Untitled-1.exe‎

50.1 KB
Binary file not shown.

0 commit comments

Comments
 (0)