-
Notifications
You must be signed in to change notification settings - Fork 0
/
BTree.h
210 lines (184 loc) · 8.21 KB
/
BTree.h
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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
#pragma once
#include<iostream>
#include"Others.h"
using namespace std;
#define N 4
class BNode {
public:
// key of N-1 BNodes
int key[N - 1];
// Child array of 'N' length
BNode* child[N];
// To state whether a leaf or not; if BNode is a leaf, isleaf=True else isleaf=False
bool isleaf=false;
// Counts the number of filled keys in a BNode
int numkeys;
// Keeps track of the parent BNode
BNode* parent;
};
// This function searches for the leaf
// into which to insert element 'k'
class BTree {
BNode* searchforleaf( BNode* root, int k, BNode* parent, int chindex){
if (root) {
// If the passed root is a leaf BNode, then
// k can be inserted in this BNode itself
if (root->isleaf)
return root;
// If the passed root is not a leaf BNode,
// implying there are one or more children
else {
int i;
/*If passed root's initial key is itself g
reater than the element to be inserted,
we need to insert to a new leaf left of the root*/
if (k < root->key[0])
root = searchforleaf(root->child[0], k, root, 0);
else
{
// Find the first key whose value is greater
// than the insertion value
// and insert into child of that key
for (i = 0; i < root->numkeys; i++)
if (root->key[i] > k)
root = searchforleaf(root->child[i], k, root, i);
// If all the keys are less than the insertion
// key value, insert to the right of last key
if (root->key[i - 1] < k)
root = searchforleaf(root->child[i], k, root, i);
}
}
}
else {
// If the passed root is NULL (there is no such
// child BNode to search), then create a new leaf
// BNode in that location
BNode* newleaf = new BNode;
newleaf->isleaf = true;
newleaf->numkeys = 0;
parent->child[chindex] = newleaf;
newleaf->parent = parent;
return newleaf;
}
}
BNode* insert( BNode* root, int k)
{
if (root) {
BNode* p = searchforleaf(root, k, NULL, 0);
BNode* q = NULL;
int e = k;
// If the leaf BNode is empty, simply
// add the element and return
for (int e = k; p; p = p->parent) {
if (p->numkeys == 0) {
p->key[0] = e;
p->numkeys = 1;
return root;
}
// If number of filled keys is less than maximum
if (p->numkeys < N - 1) {
int i;
for (i = 0; i < p->numkeys; i++) {
if (p->key[i] > e) {
for (int j = p->numkeys - 1; j >= i; j--)
p->key[j + 1] = p->key[j];
break;
}
}
p->key[i] = e;
p->numkeys = p->numkeys + 1;
return root;
}
// If number of filled keys is equal to maximum
// and it's not root and there is space in the parent
if (p->numkeys == N - 1 && p->parent && p->parent->numkeys < N) {
int m;
for (int i = 0; i < p->parent->numkeys; i++)
if (p->parent->child[i] == p) {
m = i;
break;
}
// If right sibling is possible
if (m + 1 <= N - 1)
{
// q is the right sibling
q = p->parent->child[m + 1];
if (q) {
// If right sibling is full
if (q->numkeys == N - 1) {
BNode* r = new BNode;
int* z = new int[((2 * N) / 3)];
int parent1, parent2;
int* marray = new int[2 * N];
int i;
for (i = 0; i < p->numkeys; i++)
marray[i] = p->key[i];
int fege = i;
marray[i] = e;
marray[i + 1] = p->parent->key[m];
for (int j = i + 2; j < ((i + 2) + (q->numkeys)); j++)
marray[j] = q->key[j - (i + 2)];
// marray=bubblesort(marray, 2*N)
// a more rigorous implementation will
// sort these elements
// Put first (2*N-2)/3 elements into keys of p
for (int i = 0; i < (2 * N - 2) / 3; i++)
p->key[i] = marray[i];
parent1 = marray[(2 * N - 2) / 3];
// Put next (2*N-1)/3 elements into keys of q
for (int j = ((2 * N - 2) / 3) + 1; j < (4 * N) / 3; j++)
q->key[j - ((2 * N - 2) / 3 + 1)] = marray[j];
parent2 = marray[(4 * N) / 3];
// Put last (2*N)/3 elements into keys of r
for (int f = ((4 * N) / 3 + 1); f < 2 * N; f++)
r->key[f - ((4 * N) / 3 + 1)] = marray[f];
// Because m=0 and m=1 are children of the same key,
// a special case is made for them
if (m == 0 || m == 1) {
p->parent->key[0] = parent1;
p->parent->key[1] = parent2;
p->parent->child[0] = p;
p->parent->child[1] = q;
p->parent->child[2] = r;
return root;
}
else {
p->parent->key[m - 1] = parent1;
p->parent->key[m] = parent2;
p->parent->child[m - 1] = p;
p->parent->child[m] = q;
p->parent->child[m + 1] = r;
return root;
}
}
}
else // If right sibling is not full
{
int put;
if (m == 0 || m == 1)
put = p->parent->key[0];
else
put = p->parent->key[m - 1];
for (int j = (q->numkeys) - 1; j >= 1; j--)
q->key[j + 1] = q->key[j];
q->key[0] = put;
p->parent->key[m == 0 ? m : m - 1] = p->key[p->numkeys - 1];
}
}
}
}
/*Cases of root splitting, etc. are omitted
as this implementation is just to demonstrate
the two-three split operation*/
}
else
{
// Create new BNode if root is NULL
BNode* root = new BNode;
root->key[0] = k;
root->isleaf = true;
root->numkeys = 1;
root->parent = NULL;
}
}
};