Mixing
Calculating maximum number of splits that can occur during insertion of $n$ keys in B Tree of order $m$
$begingroup$
(I dont know if this question is valid candidate for math.stackexchange, but puttin it anyway as I believe this might require maths expertise)
I can calculate this by trying out manually inserting $n$ keys in $m$ order B Tree as follows:
- Assume median to be selected for split be left biased. That is $m/2$. For example, if $m=4$, then a node
[1,2,3,4]need to be split with 2 as a median and resulting in nodes[1]and[3,4]. So, we selected 2 as a median, whereas 3 could also be the candidate for the median and 2 is on left of 3, so "left biased". (I just made up the term "left biased median" for convenience, it might sound bad) Left biased median will leave more keys in right child than left child.
- Insert elements in increasing order, which will further result in insertion in right children nodes, which were already more filled in comparison to left children due to left biased median.
For example, if $m=4$ and $n=10$, and we insert keys:1,2,3,4,5,6,7,8,9,10, then there will be 5 splits as follows:
Insert 1,2,3
=================
[1,2,3]
Insert 4
============
[2]
/
[1] [3,4] (Split:[1,2,3,4])
Insert 5,6
===============
[2,4]
/ |
[1] [3] [5,6] (Split:[3,4,5,6])
Insert 7,8
===============
[2,4,6]
/ /
[1] [3] [5] [7,8] (Split:[5,6,7,8])
Insert 9,10
===============
[4]
/
[2] [6,8]
/ | / |
[1] [3][5][7] [9,10] (Split:[5,6,7,8],[2,4,6,8])
Total splits: 5
However, can we derive the closed formula (if not closed formula, then a summation series?) for this for given $m$ and $n$? It seems that splits are occurring on every two insertions, but how can we capture in formula, number of splits that occur for each such iterations?
graph-theory algorithms trees data-structure
asked Jan 29 at 21:39
aniranir
418211
$endgroup$
add a comment |
$begingroup$
(I dont know if this question is valid candidate for math.stackexchange, but puttin it anyway as I believe this might require maths expertise)
I can calculate this by trying out manually inserting $n$ keys in $m$ order B Tree as follows:
- Assume median to be selected for split be left biased. That is $m/2$. For example, if $m=4$, then a node
[1,2,3,4]need to be split with 2 as a median and resulting in nodes[1]and[3,4]. So, we selected 2 as a median, whereas 3 could also be the candidate for the median and 2 is on left of 3, so "left biased". (I just made up the term "left biased median" for convenience, it might sound bad) Left biased median will leave more keys in right child than left child.
- Insert elements in increasing order, which will further result in insertion in right children nodes, which were already more filled in comparison to left children due to left biased median.
For example, if $m=4$ and $n=10$, and we insert keys:1,2,3,4,5,6,7,8,9,10, then there will be 5 splits as follows:
Insert 1,2,3
=================
[1,2,3]
Insert 4
============
[2]
/
[1] [3,4] (Split:[1,2,3,4])
Insert 5,6
===============
[2,4]
/ |
[1] [3] [5,6] (Split:[3,4,5,6])
Insert 7,8
===============
[2,4,6]
/ /
[1] [3] [5] [7,8] (Split:[5,6,7,8])
Insert 9,10
===============
[4]
/
[2] [6,8]
/ | / |
[1] [3][5][7] [9,10] (Split:[5,6,7,8],[2,4,6,8])
Total splits: 5
However, can we derive the closed formula (if not closed formula, then a summation series?) for this for given $m$ and $n$? It seems that splits are occurring on every two insertions, but how can we capture in formula, number of splits that occur for each such iterations?
graph-theory algorithms trees data-structure
asked Jan 29 at 21:39
aniranir
418211
$endgroup$
add a comment |
$begingroup$
(I dont know if this question is valid candidate for math.stackexchange, but puttin it anyway as I believe this might require maths expertise)
I can calculate this by trying out manually inserting $n$ keys in $m$ order B Tree as follows:
- Assume median to be selected for split be left biased. That is $m/2$. For example, if $m=4$, then a node
[1,2,3,4]need to be split with 2 as a median and resulting in nodes[1]and[3,4]. So, we selected 2 as a median, whereas 3 could also be the candidate for the median and 2 is on left of 3, so "left biased". (I just made up the term "left biased median" for convenience, it might sound bad) Left biased median will leave more keys in right child than left child.
- Insert elements in increasing order, which will further result in insertion in right children nodes, which were already more filled in comparison to left children due to left biased median.
For example, if $m=4$ and $n=10$, and we insert keys:1,2,3,4,5,6,7,8,9,10, then there will be 5 splits as follows:
Insert 1,2,3
=================
[1,2,3]
Insert 4
============
[2]
/
[1] [3,4] (Split:[1,2,3,4])
Insert 5,6
===============
[2,4]
/ |
[1] [3] [5,6] (Split:[3,4,5,6])
Insert 7,8
===============
[2,4,6]
/ /
[1] [3] [5] [7,8] (Split:[5,6,7,8])
Insert 9,10
===============
[4]
/
[2] [6,8]
/ | / |
[1] [3][5][7] [9,10] (Split:[5,6,7,8],[2,4,6,8])
Total splits: 5
However, can we derive the closed formula (if not closed formula, then a summation series?) for this for given $m$ and $n$? It seems that splits are occurring on every two insertions, but how can we capture in formula, number of splits that occur for each such iterations?
graph-theory algorithms trees data-structure
asked Jan 29 at 21:39
aniranir
418211
$endgroup$
(I dont know if this question is valid candidate for math.stackexchange, but puttin it anyway as I believe this might require maths expertise)
I can calculate this by trying out manually inserting $n$ keys in $m$ order B Tree as follows:
- Assume median to be selected for split be left biased. That is $m/2$. For example, if $m=4$, then a node
[1,2,3,4]need to be split with 2 as a median and resulting in nodes[1]and[3,4]. So, we selected 2 as a median, whereas 3 could also be the candidate for the median and 2 is on left of 3, so "left biased". (I just made up the term "left biased median" for convenience, it might sound bad) Left biased median will leave more keys in right child than left child.
- Insert elements in increasing order, which will further result in insertion in right children nodes, which were already more filled in comparison to left children due to left biased median.
For example, if $m=4$ and $n=10$, and we insert keys:1,2,3,4,5,6,7,8,9,10, then there will be 5 splits as follows:
Insert 1,2,3
=================
[1,2,3]
Insert 4
============
[2]
/
[1] [3,4] (Split:[1,2,3,4])
Insert 5,6
===============
[2,4]
/ |
[1] [3] [5,6] (Split:[3,4,5,6])
Insert 7,8
===============
[2,4,6]
/ /
[1] [3] [5] [7,8] (Split:[5,6,7,8])
Insert 9,10
===============
[4]
/
[2] [6,8]
/ | / |
[1] [3][5][7] [9,10] (Split:[5,6,7,8],[2,4,6,8])
Total splits: 5
However, can we derive the closed formula (if not closed formula, then a summation series?) for this for given $m$ and $n$? It seems that splits are occurring on every two insertions, but how can we capture in formula, number of splits that occur for each such iterations?
graph-theory algorithms trees data-structure
graph-theory algorithms trees data-structure
asked Jan 29 at 21:39
aniranir
418211
asked Jan 29 at 21:39
aniranir
418211
asked Jan 29 at 21:39
aniranir
418211
asked Jan 29 at 21:39
aniranir
418211
asked Jan 29 at 21:39
aniranir
418211
418211
add a comment |
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3092757%2fcalculating-maximum-number-of-splits-that-can-occur-during-insertion-of-n-keys%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3092757%2fcalculating-maximum-number-of-splits-that-can-occur-during-insertion-of-n-keys%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
