https://wiki.algo.informatik.tu-darmstadt.de/api.php?action=feedcontributions&feedformat=atom&user=LkwAlgowiki - User contributions [en]2026-04-22T12:14:38ZUser contributionsMediaWiki 1.38.4https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Main_Page&diff=2704Main Page2014-12-26T17:35:16Z<p>Lkw: </p>
<hr />
<div>== News ==<br />
* The http://wiki.algo.informatik.tu-darmstadt.de domain will forward to this page from 13th October.<br />
* The old wiki will be reachable at http://huffmann.algo.informatik.tu-darmstadt.de/wiki/<br />
* <math>LaTeX</math> [http://www.mediawiki.org/wiki/Manual:Math available now!]<br />
* ToDo List added<br />
* Every content has to be in English!<br />
* [http://www.mediawiki.org/wiki/Extension:SyntaxHighlight_GeSHi Syntaxhighlight]<br />
<br />
== Rules ==<br />
* Add finalized reconstructions of the old Wiki to Category:Checkup.<br />
* Don't any non-Weihe content until the reconstructions isn't finished.<br />
* Keep your active reconstructing Pages in "Division of labor" section up to date!<br />
<br />
'''Look here for short/uncomplete Pages''' [[Special:ShortPages]]<br />
<br />
== Page Status ==<br />
Final: [[:Category:Checkup]]<br />
<br />
== To Do ==<br />
=== Notations ===<br />
* [[Big O notation]]<br />
* [[L' Hospital]]<br />
* [[Master theorem]]<br />
<br />
=== Problems ===<br />
* [[Matchings in graphs#Cardinality-maximal matching|Maximum matching problem]]<br />
* [[Max-Flow Problems]]<br />
* [[Min-Cost Flow Problems]]<br />
* [[Shortest Paths Problems]]<br />
** [[All pairs shortest paths]]<br />
*** [[Floyd-Warshall]]<br />
*** [[Bellman-Ford]] (DONE)<br />
*** [[Shortest paths by repeated squaring]] (variant of Bellman-Ford) <br />
** [[Single source shortest paths]]<br />
*** [[Dijkstra]]<br />
** [[Single source single target shortest paths]]<br />
*** [[A*]] (Empty in old wiki)<br />
* [[Maximum spanning forest]]<br />
* [[Problems on Sequences]]<br />
** [[Basic Problems on Sequences]]<br />
*** [[Find an element in a sequence]] (DONE)<br />
*** [[Insert an element in a sequence]] (Empty in old wiki?!)<br />
*** [[Median]] (DONE)<br />
*** [[Merging two sorted sequences]] (DONE)<br />
** [[Pattern Matching]]<br />
*** [[One-dimensional string matching]] (DONE)<br />
*** [[String matching]] (DONE)<br />
** [[Sorting]]<br />
*** [[Sorting based on pairwise comparison]] (DONE)<br />
*** [[Sorting Sequences of Strings]] (DONE)<br />
<br />
=== Coding Basics ===<br />
* [[Inheritance]]<br />
* [[Generics]]<br />
* [[Collections]]<br />
** [[Iterator]]<br />
** [[Comparator]]<br />
<br />
=== String Matching Algorithms ===<br />
* [[Simple string matching algorithm]] (DONE)<br />
* [[String matching based on finite automaton]] (DONE)<br />
<br />
=== Sorting Algorithms ===<br />
* [[Bubble]]<br />
* [[Insertion sort]]<br />
* [[Quicksort]]<br />
* [[Bubblesort]]<br />
* [[Mergesort]]<br />
* [[Bucketsort]]<br />
* [[Selection sort]]<br />
* [[Bogosort]]<br />
<br />
=== Search Algorithms ===<br />
* [[Binary search]]<br />
<br />
=== Auxillary Algorithms ===<br />
* [[Pivot partitioning by scanning]]<br />
<br />
=== Manipulation ===<br />
* [[Array list: find]]<br />
* [[Array list: find at position]]<br />
* [[Array list: insert at head]]<br />
* [[Array list: insert at position]]<br />
* [[Array list: number]]<br />
* [[Array list: remove]]<br />
* [[Doubly-linked list: insert at position]]<br />
* [[Doubly-linked list: insert at tail]]<br />
* [[Doubly-linked list: remove]]<br />
* [[Find element in sequence iteratively]]<br />
* [[Find element in sequence recursively]]<br />
* [[Hashtable: find]]<br />
* [[Hashtable: insert]]<br />
<br />
=== Tree Algorithms ===<br />
* [[Depth-first search]]<br />
* [[Breadth-first search]]<br />
* [[B-tree: find]]<br />
* [[B-tree: minimum]]<br />
* [[B-tree: maximum]]<br />
* [[B-tree: insert]]<br />
* [[B-tree: insert and rearrange]]<br />
* [[B-tree: merge two siblings]]<br />
* [[B-tree: remove]]<br />
* [[B-tree: shift key to sibling]]<br />
* [[B-tree: rotate]]<br />
* [[B-tree: merge]]<br />
* [[B-tree: split]]<br />
* [[Binary search tree: find]]<br />
* [[Binary search tree: minimum]]<br />
* [[Binary search tree: maximum]]<br />
* [[Binary search tree: insert]]<br />
* [[Binary search tree: remove]]<br />
* [[Binary search tree: remove node]]<br />
* [[Binary search tree: traverse]]<br />
<br />
=== Graph Theory ===<br />
* [[Directed graph]]<br />
* [[Bipartite graph|Bipartite graph]] (DONE)<br />
* [[k-partite graph]]<br />
* [[Negative paths]]<br />
<br />
=== Graph Algorithms ===<br />
* [[Dijkstra]]<br />
* [[Kruskal]]<br />
* [[Prim]]<br />
* [[Bellman-Ford]] (DONE)<br />
* [[Floyd-Warshall]]<br />
* [[Union Find]]<br />
* [[A*]]<br />
* [[Alternating paths algorithm]]<br />
* [[Johnson]]<br />
* [[Union-find with disjoint trees: find]]<br />
* [[Union-find with lists: unite]]<br />
* [[Max-flow min-cut]]<br />
<br />
=== Flow Algorithms ===<br />
* [[Ford-Fulkerson]]<br />
* [[Edmonds-Karp]]<br />
<br />
=== Abstract Data Structures ===<br />
*[[Network Structures]]<br />
**[[Graph]]<br />
**[[Tree]]<br />
*[[Sequence]]<br />
**[[Sorted sequence]]<br />
**[[Bounded priority queue]]<br />
**[[Linear sequence]]<br />
**[[Priority queue]]<br />
**[[Sorted sequence]]<br />
=== Implementations of Abstract Data Structures ===<br />
* [[Linked list]]<br />
* [[Array list]]<br />
* [[Binary search tree]]<br />
* [[Doubly-linked list]]<br />
* [[Heap as array]] (DONE (Heap as Array))<br />
* [[Hashtable]]<br />
* [[Multi-way search tree]]<br />
* [[Red-black tree]]<br />
* [[B-tree]]<br />
<br />
=== ??? ===<br />
* [[Min-Max Heaps]]<br />
* [[First In - First Out]]<br />
* [[First In - Last Out]]<br />
* [[Directed Tree]]<br />
* [[Decision Tree]]<br />
<br />
=== Other ===<br />
* [[Model computer]]<br />
<br />
=== Other Algorithms (LOCKED) ===<br />
* [[B*]]<br />
* [[Cyclic redundancy check]]<br />
* [[Euclid]]<br />
* [[Gauss]]<br />
* [[Discrete fourier transform]]<br />
* [[Fast fourier transform]]<br />
* [[Bresenham]]<br />
* [[Round robin]]<br />
* [[Seperate and conquer]]<br />
* [[Message-Digest algorithm]]<br />
* [[Secure hash algorithm]]<br />
* [[Sequent calculus]]<br />
* [[Resolution calculus]]<br />
* [[Cocke-Younger-Kasami algorithm]]<br />
* [[Distance vector routing]]<br />
* [[Link state routing]]<br />
* [[Z Buffer algorithm]]<br />
* [[Marching squares]]<br />
* [[Marching cubes]]<br />
* [[Bottom-Up heapsort]]<br />
* [[Radixsort]]<br />
* [[Median cut]]<br />
* [[Pancake sorting]]<br />
* [[Karnaugh-Veitch diagramm]]<br />
* [[Delanuay triangulation]]<br />
* [[Backtracking]]<br />
* [[Alpha–beta pruning]]<br />
* [[Beam search]]<br />
* [[Best-first search]]<br />
* [[Bidirectional search]]<br />
* [[Borůvka's algorithm]]<br />
* [[Branch and bound]]<br />
* [[D*]]<br />
* [[Depth-limited search]]<br />
* [[Edmonds' algorithm]]<br />
* [[Fringe search]]<br />
* [[Hill climbing]]<br />
* [[IDA*]]<br />
* [[Iterative deepening depth-first search]]<br />
* [[Jump point search]]<br />
* [[Lexicographic breadth-first search]]<br />
* [[SMA*]]<br />
* [[Uniform-cost search]]<br />
<br />
=== Other Data Structures (LOCKED) ===<br />
* [[Adelson-Velskii and Landis' tree]]<br />
* [[Patricia-Trie]]<br />
* [[Suffix Tree]]<br />
* [[Huffmann Tree]]<br />
* [[Binary Expression Tree]]<br />
* [[Hash Set]]<br />
* [[Incidence Matrix]]<br />
* [[Voronoi Diagramm]]<br />
* [[Quad Tree]]<br />
* [[Oct Tree]]<br />
* [[kd Tree]]<br />
* [[Binary space partitioning]]</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_shift_key_to_sibling&diff=468B-tree: shift key to sibling2014-09-30T19:54:39Z<p>Lkw: /* Induction step */</p>
<hr />
<div>[[Category:B-Tree]]<br />
[[Category:Algorithm]]<br />
== General Information ==<br />
'''Algorithmic problem:''' [[See B-tree]]<br />
<br />
'''Type of algorithm:''' loop<br />
<br />
'''Auxiliary data:''' <br />
<br />
== Abstract View ==<br />
'''Invariant:''' After <math>i \ge 0</math> iterations:<br />
# If <math> shiftRight</math><br />
## For <math>j \in \{ p.children[k].n-i+1, \dots ,p.children[k].n \{</math>, if <math>j>0</math>, the original values of <math>p.children[k].key[j]</math> are now the values of <math>p.children[k].key[j+1]</math>.<br />
## For <math>j \in \{ p.children[k].n-i+1, \dots ,p.children[k].n \}</math>, the original values of <math>p.children[k].children[j]</math> are now the values of <math>p.children[k].children[j+1]</math>.<br />
# Otherwise:<br />
## For <math>j \in \{2, \dots ,i+1 \}</math>, id <math>j \le n</math>, the original values of <math>p.children[k].key[j]</math> are now the values of <math>p.children[k].key[j-1]</math>.<br />
## For <math>j \in \{ 1, \dots ,i \}</math>, the values of <math>p.children[k].children[j]</math> are now the values of <math>p.children[k].children[j-1]</math>.<br />
## A few moves have already been done (in the preprocessing, in fact):<br />
### The former value of <math>p.keys[k]</math> is now the node <math>p.children[k-1]</math>.<br />
### The former value of <math>p.children[k].keys[1]</math> is now at <math>p.keys[k]</math>.<br />
### The children pointers of <math>p.children[k-1]</math> and <math>p.children[k]</math are rearranged accordingly.<br />
<br />
'''Vairant:''' <math>i</math> increases by <math>1</math><br />
<br />
'''Break condition:''' <math>(shiftRight</math> &and;<math> i=p.children[k].n+1)</math>&or;<math>(</math>&not;<math>shiftRight</math>&and;<math>i=p.children[k].n)</math> <br />
<br />
Before and after each iteration, <math>p</math> points to a node <math>N</math> such that the following holds: <br />
# In the case <math>p.n < 2M</math>, all implementation invariants of B-trees are maintained if the following <math>K'</math> can be inserted at some position in <math>N</math> such that after insertion.<br />
# In the case <math>p.n = 2M</math>, imagine that we could extend <math>p</math>.keys by one more slot (and, consequently, extend .successors by one more slot). Then <math>K'</math> can be inserted in <math>N</math> at a position such that - except for the statement about the size of <math>N</math> - all implementation invariants of B-trees are again maintained after insertion.<br />
<br />
'''Variant:''' The height level of the node to which <math>p</math> points is decreased by <math>1</math>.<br />
<br />
'''Break condition:''' <math>p.N < 2M</math> or (that is, inclusive-or) <math>p</math> points to the root.<br />
<br />
== Induction step ==<br />
'''Abstract view:''' <br />
# Move the next key and children pointer.<br />
# If <math>shiftRight</math> and the break condition applies, the shift is to be done.<br />
<br />
'''Implementation:''' <br />
# If <math>shiftRight</math>:<br />
## If <math>i \le n</math>, set <math>p.children[k]keys[p.children[k].n-i+2]:= p.children[k],keys[p.children[k]._n-i+1]</math><br />
## Set <math>p.children[k].children[p.children[k]._n-i+2]:= p.children[k].children[p.children[k]_n-i+1]</math><br />
## If <math> i=n+1</math>:<br />
### Set <math>p.children[k].keys[1]:= p.keys[k]</math><br />
### Set <math>p.keys[k]:=p.children[k-1].keys[p.children[k-1]_n] </math><br />
### Increment <math>p.children[k]_n by one </math><br />
### Decrement <math>p.children[j-1]_n by one</math><br />
# Otherwise:<br />
## If <math>i<p.children[k]_n</math> set <math>p.children[k].keys[i]:= p.children[k].keys[i+1]</math><br />
## Set <math>p.children[k].children[i-1]:= p.children[k].children[i]</math><br />
## If <math>i=p.children[k]_n, </math>decrement <math>p.children[k]_n</math> by one<br />
<br />
'''Correctness:'''<br />
# For the rearrangement of the children pointers, compare the induction basis.<br />
# Note that the increments and decrements of <math>p.children[k-1]_n</math> and <math>p.children[k]_n </math> are distributed over induction basis and induction step, but are correct in summary.<br />
<br />
== Complexity ==<br />
'''Statement:''' Linear in <math>M</math> in the best and worst case (and hence constant for fixed <math>M</math>).<br />
'''Proof:''' Obvious.</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_shift_key_to_sibling&diff=467B-tree: shift key to sibling2014-09-30T19:54:08Z<p>Lkw: /* Induction step */</p>
<hr />
<div>[[Category:B-Tree]]<br />
[[Category:Algorithm]]<br />
== General Information ==<br />
'''Algorithmic problem:''' [[See B-tree]]<br />
<br />
'''Type of algorithm:''' loop<br />
<br />
'''Auxiliary data:''' <br />
<br />
== Abstract View ==<br />
'''Invariant:''' After <math>i \ge 0</math> iterations:<br />
# If <math> shiftRight</math><br />
## For <math>j \in \{ p.children[k].n-i+1, \dots ,p.children[k].n \{</math>, if <math>j>0</math>, the original values of <math>p.children[k].key[j]</math> are now the values of <math>p.children[k].key[j+1]</math>.<br />
## For <math>j \in \{ p.children[k].n-i+1, \dots ,p.children[k].n \}</math>, the original values of <math>p.children[k].children[j]</math> are now the values of <math>p.children[k].children[j+1]</math>.<br />
# Otherwise:<br />
## For <math>j \in \{2, \dots ,i+1 \}</math>, id <math>j \le n</math>, the original values of <math>p.children[k].key[j]</math> are now the values of <math>p.children[k].key[j-1]</math>.<br />
## For <math>j \in \{ 1, \dots ,i \}</math>, the values of <math>p.children[k].children[j]</math> are now the values of <math>p.children[k].children[j-1]</math>.<br />
## A few moves have already been done (in the preprocessing, in fact):<br />
### The former value of <math>p.keys[k]</math> is now the node <math>p.children[k-1]</math>.<br />
### The former value of <math>p.children[k].keys[1]</math> is now at <math>p.keys[k]</math>.<br />
### The children pointers of <math>p.children[k-1]</math> and <math>p.children[k]</math are rearranged accordingly.<br />
<br />
'''Vairant:''' <math>i</math> increases by <math>1</math><br />
<br />
'''Break condition:''' <math>(shiftRight</math> &and;<math> i=p.children[k].n+1)</math>&or;<math>(</math>&not;<math>shiftRight</math>&and;<math>i=p.children[k].n)</math> <br />
<br />
Before and after each iteration, <math>p</math> points to a node <math>N</math> such that the following holds: <br />
# In the case <math>p.n < 2M</math>, all implementation invariants of B-trees are maintained if the following <math>K'</math> can be inserted at some position in <math>N</math> such that after insertion.<br />
# In the case <math>p.n = 2M</math>, imagine that we could extend <math>p</math>.keys by one more slot (and, consequently, extend .successors by one more slot). Then <math>K'</math> can be inserted in <math>N</math> at a position such that - except for the statement about the size of <math>N</math> - all implementation invariants of B-trees are again maintained after insertion.<br />
<br />
'''Variant:''' The height level of the node to which <math>p</math> points is decreased by <math>1</math>.<br />
<br />
'''Break condition:''' <math>p.N < 2M</math> or (that is, inclusive-or) <math>p</math> points to the root.<br />
<br />
== Induction step ==<br />
'''Abstract view:''' <br />
# Move the next key and children pointer.<br />
# If <math>shiftRight</math> and the break condition applies, the shift is to be done.<br />
<br />
'''Implementation:''' <br />
# If <math>shiftRight</math>:<br />
## If <math>i \le n</math>, set <math>p.children[k]keys[p.children[k].n-i+2]:= p.children[k],keys[p.children[k]._n-i+1]</math><br />
## Set <math>p.children[k].children[p.children[k]._n-i+2]:= p.children[k].children[p.children[k]_n-i+1]</math><br />
## If <math> i=n+1</math>:<br />
### Set <math>p.children[k].keys[1]:= p.keys[k]</math><br />
### Set <math>p.keys[k]:=p.children[k-1].keys[p.children[k-1]_n]<br />
### Increment <math>p.children[k]_n by one<br />
### Decrement <math>p.children[j-1]_n by one</math><br />
# Otherwise:<br />
## If <math>i<p.children[k]_n</math> set <math>p.children[k].keys[i]:= p.children[k].keys[i+1]</math><br />
## Set <math>p.children[k].children[i-1]:= p.children[k].children[i]</math><br />
## If <math>i=p.children[k]_n, </math>decrement <math>p.children[k]_n</math> by one<br />
<br />
'''Correctness:'''<br />
# For the rearrangement of the children pointers, compare the induction basis.<br />
# Note that the increments and decrements of <math>p.children[k-1]_n</math> and <math>p.children[k]_n </math> are distributed over induction basis and induction step, but are correct in summary.<br />
<br />
== Complexity ==<br />
'''Statement:''' Linear in <math>M</math> in the best and worst case (and hence constant for fixed <math>M</math>).<br />
'''Proof:''' Obvious.</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_shift_key_to_sibling&diff=466B-tree: shift key to sibling2014-09-30T19:49:58Z<p>Lkw: /* Complexity */</p>
<hr />
<div>[[Category:B-Tree]]<br />
[[Category:Algorithm]]<br />
== General Information ==<br />
'''Algorithmic problem:''' [[See B-tree]]<br />
<br />
'''Type of algorithm:''' loop<br />
<br />
'''Auxiliary data:''' <br />
<br />
== Abstract View ==<br />
'''Invariant:''' After <math>i \ge 0</math> iterations:<br />
# If <math> shiftRight</math><br />
## For <math>j \in \{ p.children[k].n-i+1, \dots ,p.children[k].n \{</math>, if <math>j>0</math>, the original values of <math>p.children[k].key[j]</math> are now the values of <math>p.children[k].key[j+1]</math>.<br />
## For <math>j \in \{ p.children[k].n-i+1, \dots ,p.children[k].n \}</math>, the original values of <math>p.children[k].children[j]</math> are now the values of <math>p.children[k].children[j+1]</math>.<br />
# Otherwise:<br />
## For <math>j \in \{2, \dots ,i+1 \}</math>, id <math>j \le n</math>, the original values of <math>p.children[k].key[j]</math> are now the values of <math>p.children[k].key[j-1]</math>.<br />
## For <math>j \in \{ 1, \dots ,i \}</math>, the values of <math>p.children[k].children[j]</math> are now the values of <math>p.children[k].children[j-1]</math>.<br />
## A few moves have already been done (in the preprocessing, in fact):<br />
### The former value of <math>p.keys[k]</math> is now the node <math>p.children[k-1]</math>.<br />
### The former value of <math>p.children[k].keys[1]</math> is now at <math>p.keys[k]</math>.<br />
### The children pointers of <math>p.children[k-1]</math> and <math>p.children[k]</math are rearranged accordingly.<br />
<br />
'''Vairant:''' <math>i</math> increases by <math>1</math><br />
<br />
'''Break condition:''' <math>(shiftRight</math> &and;<math> i=p.children[k].n+1)</math>&or;<math>(</math>&not;<math>shiftRight</math>&and;<math>i=p.children[k].n)</math> <br />
<br />
Before and after each iteration, <math>p</math> points to a node <math>N</math> such that the following holds: <br />
# In the case <math>p.n < 2M</math>, all implementation invariants of B-trees are maintained if the following <math>K'</math> can be inserted at some position in <math>N</math> such that after insertion.<br />
# In the case <math>p.n = 2M</math>, imagine that we could extend <math>p</math>.keys by one more slot (and, consequently, extend .successors by one more slot). Then <math>K'</math> can be inserted in <math>N</math> at a position such that - except for the statement about the size of <math>N</math> - all implementation invariants of B-trees are again maintained after insertion.<br />
<br />
'''Variant:''' The height level of the node to which <math>p</math> points is decreased by <math>1</math>.<br />
<br />
'''Break condition:''' <math>p.N < 2M</math> or (that is, inclusive-or) <math>p</math> points to the root.<br />
<br />
== Induction step ==<br />
'''Abstract view:''' <br />
# Move the next key and children pointer.<br />
# If <math>shiftRight</math> and the break condition applies, the shift is to be done.<br />
<br />
'''Implementation:''' <br />
# If <math>shiftRight</math>:<br />
## If <math>i \le n</math>, set <math>p.children[k]keys[p.children[k].n-i+2]:= p.children[k],keys[p.children[k]._n_-i_+1]</math><br />
## Set <math>p.children[k].children[p.children[k]._n-i+2]:= p.children[k].children[p.children[k]._n-i+1]</math><br />
## If <math> i=n+1</math>:<br />
### Set <math>p.children[k].keys[1]:= p.keys[k]<br />
### Set <math>p.keys[k]:=p.children[k-1].keys[p.children[k-1]_n]<br />
### Increment <math>p.children[k]_n by one<br />
### Decrement <math>p.children[j-1]_n by one</math><br />
# Otherwise:<br />
## If <math>i<p.children[k]_n</math> set <math>p.children[k].keys[i]:= p.children[k].keys[i+1]</math><br />
## Set <math>p.children[k].children[i-1]:= p.children[k].children[i]</math><br />
## If <math>i=p.children[k]_n, </math>decrement <math>p.children[k]_n</math> by one<br />
<br />
'''Correctness:'''<br />
# For the rearrangement of the children pointers, compare the induction basis.<br />
# Note that the increments and decrements of <math>p.children[k-1]_n</math> and <math>p.children[k]_n </math> are distributed over induction basis and induction step, but are correct in summary.<br />
<br />
<br />
== Complexity ==<br />
'''Statement:''' Linear in <math>M</math> in the best and worst case (and hence constant for fixed <math>M</math>).<br />
'''Proof:''' Obvious.</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_shift_key_to_sibling&diff=465B-tree: shift key to sibling2014-09-30T19:48:53Z<p>Lkw: </p>
<hr />
<div>[[Category:B-Tree]]<br />
[[Category:Algorithm]]<br />
== General Information ==<br />
'''Algorithmic problem:''' [[See B-tree]]<br />
<br />
'''Type of algorithm:''' loop<br />
<br />
'''Auxiliary data:''' <br />
<br />
== Abstract View ==<br />
'''Invariant:''' After <math>i \ge 0</math> iterations:<br />
# If <math> shiftRight</math><br />
## For <math>j \in \{ p.children[k].n-i+1, \dots ,p.children[k].n \{</math>, if <math>j>0</math>, the original values of <math>p.children[k].key[j]</math> are now the values of <math>p.children[k].key[j+1]</math>.<br />
## For <math>j \in \{ p.children[k].n-i+1, \dots ,p.children[k].n \}</math>, the original values of <math>p.children[k].children[j]</math> are now the values of <math>p.children[k].children[j+1]</math>.<br />
# Otherwise:<br />
## For <math>j \in \{2, \dots ,i+1 \}</math>, id <math>j \le n</math>, the original values of <math>p.children[k].key[j]</math> are now the values of <math>p.children[k].key[j-1]</math>.<br />
## For <math>j \in \{ 1, \dots ,i \}</math>, the values of <math>p.children[k].children[j]</math> are now the values of <math>p.children[k].children[j-1]</math>.<br />
## A few moves have already been done (in the preprocessing, in fact):<br />
### The former value of <math>p.keys[k]</math> is now the node <math>p.children[k-1]</math>.<br />
### The former value of <math>p.children[k].keys[1]</math> is now at <math>p.keys[k]</math>.<br />
### The children pointers of <math>p.children[k-1]</math> and <math>p.children[k]</math are rearranged accordingly.<br />
<br />
'''Vairant:''' <math>i</math> increases by <math>1</math><br />
<br />
'''Break condition:''' <math>(shiftRight</math> &and;<math> i=p.children[k].n+1)</math>&or;<math>(</math>&not;<math>shiftRight</math>&and;<math>i=p.children[k].n)</math> <br />
<br />
Before and after each iteration, <math>p</math> points to a node <math>N</math> such that the following holds: <br />
# In the case <math>p.n < 2M</math>, all implementation invariants of B-trees are maintained if the following <math>K'</math> can be inserted at some position in <math>N</math> such that after insertion.<br />
# In the case <math>p.n = 2M</math>, imagine that we could extend <math>p</math>.keys by one more slot (and, consequently, extend .successors by one more slot). Then <math>K'</math> can be inserted in <math>N</math> at a position such that - except for the statement about the size of <math>N</math> - all implementation invariants of B-trees are again maintained after insertion.<br />
<br />
'''Variant:''' The height level of the node to which <math>p</math> points is decreased by <math>1</math>.<br />
<br />
'''Break condition:''' <math>p.N < 2M</math> or (that is, inclusive-or) <math>p</math> points to the root.<br />
<br />
== Induction step ==<br />
'''Abstract view:''' <br />
# Move the next key and children pointer.<br />
# If <math>shiftRight</math> and the break condition applies, the shift is to be done.<br />
<br />
'''Implementation:''' <br />
# If <math>shiftRight</math>:<br />
## If <math>i \le n</math>, set <math>p.children[k]keys[p.children[k].n-i+2]:= p.children[k],keys[p.children[k]._n_-i_+1]</math><br />
## Set <math>p.children[k].children[p.children[k]._n-i+2]:= p.children[k].children[p.children[k]._n-i+1]</math><br />
## If <math> i=n+1</math>:<br />
### Set <math>p.children[k].keys[1]:= p.keys[k]<br />
### Set <math>p.keys[k]:=p.children[k-1].keys[p.children[k-1]_n]<br />
### Increment <math>p.children[k]_n by one<br />
### Decrement <math>p.children[j-1]_n by one</math><br />
# Otherwise:<br />
## If <math>i<p.children[k]_n</math> set <math>p.children[k].keys[i]:= p.children[k].keys[i+1]</math><br />
## Set <math>p.children[k].children[i-1]:= p.children[k].children[i]</math><br />
## If <math>i=p.children[k]_n, </math>decrement <math>p.children[k]_n</math> by one<br />
<br />
'''Correctness:'''<br />
# For the rearrangement of the children pointers, compare the induction basis.<br />
# Note that the increments and decrements of <math>p.children[k-1]_n</math> and <math>p.children[k]_n </math> are distributed over induction basis and induction step, but are correct in summary.<br />
<br />
<br />
== Complexity ==</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_shift_key_to_sibling&diff=464B-tree: shift key to sibling2014-09-30T19:47:20Z<p>Lkw: /* Induction Basis */</p>
<hr />
<div>[[Category:B-Tree]]<br />
[[Category:Algorithm]]<br />
== General Information ==<br />
'''Algorithmic problem:''' [[See B-tree]]<br />
<br />
'''Type of algorithm:''' loop<br />
<br />
'''Auxiliary data:''' <br />
<br />
== Abstract View ==<br />
'''Invariant:''' After <math>i \ge 0</math> iterations:<br />
# If <math> shiftRight</math><br />
## For <math>j \in \{ p.children[k].n-i+1, \dots ,p.children[k].n \{</math>, if <math>j>0</math>, the original values of <math>p.children[k].key[j]</math> are now the values of <math>p.children[k].key[j+1]</math>.<br />
## For <math>j \in \{ p.children[k].n-i+1, \dots ,p.children[k].n \}</math>, the original values of <math>p.children[k].children[j]</math> are now the values of <math>p.children[k].children[j+1]</math>.<br />
# Otherwise:<br />
## For <math>j \in \{2, \dots ,i+1 \}</math>, id <math>j \le n</math>, the original values of <math>p.children[k].key[j]</math> are now the values of <math>p.children[k].key[j-1]</math>.<br />
## For <math>j \in \{ 1, \dots ,i \}</math>, the values of <math>p.children[k].children[j]</math> are now the values of <math>p.children[k].children[j-1]</math>.<br />
## A few moves have already been done (in the preprocessing, in fact):<br />
### The former value of <math>p.keys[k]</math> is now the node <math>p.children[k-1]</math>.<br />
### The former value of <math>p.children[k].keys[1]</math> is now at <math>p.keys[k]</math>.<br />
### The children pointers of <math>p.children[k-1]</math> and <math>p.children[k]</math are rearranged accordingly.<br />
<br />
'''Vairant:''' <math>i</math> increases by <math>1</math><br />
<br />
'''Break condition:''' <math>(shiftRight</math> &and;<math> i=p.children[k].n+1)</math>&or;<math>(</math>&not;<math>shiftRight</math>&and;<math>i=p.children[k].n)</math> <br />
<br />
Before and after each iteration, <math>p</math> points to a node <math>N</math> such that the following holds: <br />
# In the case <math>p.n < 2M</math>, all implementation invariants of B-trees are maintained if the following <math>K'</math> can be inserted at some position in <math>N</math> such that after insertion.<br />
# In the case <math>p.n = 2M</math>, imagine that we could extend <math>p</math>.keys by one more slot (and, consequently, extend .successors by one more slot). Then <math>K'</math> can be inserted in <math>N</math> at a position such that - except for the statement about the size of <math>N</math> - all implementation invariants of B-trees are again maintained after insertion.<br />
<br />
'''Variant:''' The height level of the node to which <math>p</math> points is decreased by <math>1</math>.<br />
<br />
'''Break condition:''' <math>p.N < 2M</math> or (that is, inclusive-or) <math>p</math> points to the root.<br />
<br />
== Induction step ==<br />
'''Abstract view:''' <br />
# Move the next key and children pointer.<br />
# If <math>shiftRight</math> and the break condition applies, the shift is to be done.<br />
<br />
'''Implementation:''' <br />
# If <math>shiftRight</math>:<br />
## If <math>i \le n</math>, set <math>p.children[k]keys[p.children[k].n-i+2]:= p.children[k],keys[p.children[k]._n_-i_+1]</math><br />
## Set <math>p.children[k].children[p.children[k]._n-i+2]:= p.children[k].children[p.children[k]._n-i+1]</math><br />
## If <math> i=n+1</math>:<br />
### Set <math>p.children[k].keys[1]:= p.keys[k]<br />
### Set <math>p.keys[k]:=p.children[k-1].keys[p.children[k-1]_n]<br />
### Increment <math>p.children[k]_n by one<br />
### Decrement <math>p.children[j-1]_n by one</math><br />
# Otherwise:<br />
## If <math>i<p.children[k]_n</math> set <math>p.children[k].keys[i]:= p.children[k].keys[i+1]</math><br />
## Set <math>p.children[k].children[i-1]:= p.children[k].children[i]</math><br />
## If <math>i=p.children[k]_n, </math>decrement <math>p.children[k]_n</math> by one<br />
<br />
'''Correctness:'''<br />
# For the rearrangement of the children pointers, compare the induction basis.<br />
# Note that the increments and decrements of <math>p.children[k-1]_n</math> and <math>p.children[k]_n </math> are distributed over induction basis and induction step, but are correct in summary.<br />
<br />
== Induction Step ==<br />
'''Abstract view:'''<br />
# If the node is not full, the key can be inserted, and we are done.<br />
## If the new key is larger than all keys stored in the node, it can be appended.<br />
## Otherwise, is must override one specific slot. For that, first the contents of this slot and of each slot to its right must be moved one position further right (the corresponding values and successor pointers have to be moved as well). Then the new (key,value)-pair may be safely inserted.<br />
# On the other hand, if the node is indeed full, the key cannot be inserted. In this case:<br />
## The current node <math>N</math> will be split into two nodes, <math>N_1</math> and <math>N_2</math>.<br />
## <math>N_1</math> will contain all keys strictly less than the median of { <math>p.keys[1], ... , p.keys[p.n], K'</math> }<br />
## Analogously, <math>N_2</math> will contain all keys strictly greater than the median of { <math>p.keys[1], ... , p.keys[p.n], K'</math> }.<br />
## Next we try to<br />
## If <math>K'</math> is that median itself, nothing is to be done on the current node.<br />
## Otherwise, the median of <math>\{p.keys[1], \dots , p.keys[p.n], K'\}</math> is in one of the slots of the node. This slot is overridden (by moving the contents of each slot to the right one position further left). The previous contents of this slot is the new <math>K'</math> . If the current node is the root, which we next try to insert in the predecessor of<br />
<br />
'''Implementation:'''<br />
# If <math>p.n = 2M</math><br />
## If <math>p.keys[M] < K' < p.keys[M + 1]</math>, break the iteration and continue the loop.<br />
## Otherwise: <math> x:= M</math> if <math> K' < p.keys[M]</math>, and <math> x:= M+1</math> otherwise.<br />
## Set <math> K'' := p.keys[x]</math>.<br />
## For <math> j \in \{x+1, \dots, p.n \}</math> (in this order), set <math> p.keys [j-1]:= p.keys[j] </math> and <math>p. successor[j-1]:= p.successors[j]</math>.<br />
# If <math> p.keys[p.n] < K'</math>, insert the new (key, value)-pair at position <math>p.keys[p.n+1</math><br />
# Otherwise:<br />
## Let <math>i \in \{ 1, \dots , p.n \} </math> be minimal subject to <math>K' < p.keys[i]</math><br />
## For <math> j \in \{ p.n, \dots , i \} </math> (in this order), set <math> p.keys[j+1]:= p.keys[j]. </math><br />
# If <math> p.n < 2M</math>, set <math> p.n:= p.n+1</math> and terminate the algorithm.<br />
# Otherwise, set <math>K':= K''</math>.<br />
<br />
'''Correctness:''' Easy to see.<br />
<br />
== Complexity ==</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_shift_key_to_sibling&diff=463B-tree: shift key to sibling2014-09-30T19:27:01Z<p>Lkw: Created page with "Category:B-Tree Category:Algorithm == General Information == '''Algorithmic problem:''' See B-tree '''Type of algorithm:''' loop '''Auxiliary data:''' == Abstr..."</p>
<hr />
<div>[[Category:B-Tree]]<br />
[[Category:Algorithm]]<br />
== General Information ==<br />
'''Algorithmic problem:''' [[See B-tree]]<br />
<br />
'''Type of algorithm:''' loop<br />
<br />
'''Auxiliary data:''' <br />
<br />
== Abstract View ==<br />
'''Invariant:''' After <math>i \ge 0</math> iterations:<br />
# If <math> shiftRight</math><br />
## For <math>j \in \{ p.children[k].n-i+1, \dots ,p.children[k].n \{</math>, if <math>j>0</math>, the original values of <math>p.children[k].key[j]</math> are now the values of <math>p.children[k].key[j+1]</math>.<br />
## For <math>j \in \{ p.children[k].n-i+1, \dots ,p.children[k].n \}</math>, the original values of <math>p.children[k].children[j]</math> are now the values of <math>p.children[k].children[j+1]</math>.<br />
# Otherwise:<br />
## For <math>j \in \{2, \dots ,i+1 \}</math>, id <math>j \le n</math>, the original values of <math>p.children[k].key[j]</math> are now the values of <math>p.children[k].key[j-1]</math>.<br />
## For <math>j \in \{ 1, \dots ,i \}</math>, the values of <math>p.children[k].children[j]</math> are now the values of <math>p.children[k].children[j-1]</math>.<br />
## A few moves have already been done (in the preprocessing, in fact):<br />
### The former value of <math>p.keys[k]</math> is now the node <math>p.children[k-1]</math>.<br />
### The former value of <math>p.children[k].keys[1]</math> is now at <math>p.keys[k]</math>.<br />
### The children pointers of <math>p.children[k-1]</math> and <math>p.children[k]</math are rearranged accordingly.<br />
<br />
'''Vairant:''' <math>i</math> increases by <math>1</math><br />
<br />
'''Break condition:''' <math>(shiftRight</math> &and;<math> i=p.children[k].n+1)</math>&or;<math>(</math>&not;<math>shiftRight</math>&and;<math>i=p.children[k].n)</math> <br />
<br />
Before and after each iteration, <math>p</math> points to a node <math>N</math> such that the following holds: <br />
# In the case <math>p.n < 2M</math>, all implementation invariants of B-trees are maintained if the following <math>K'</math> can be inserted at some position in <math>N</math> such that after insertion.<br />
# In the case <math>p.n = 2M</math>, imagine that we could extend <math>p</math>.keys by one more slot (and, consequently, extend .successors by one more slot). Then <math>K'</math> can be inserted in <math>N</math> at a position such that - except for the statement about the size of <math>N</math> - all implementation invariants of B-trees are again maintained after insertion.<br />
<br />
'''Variant:''' The height level of the node to which <math>p</math> points is decreased by <math>1</math>.<br />
<br />
'''Break condition:''' <math>p.N < 2M</math> or (that is, inclusive-or) <math>p</math> points to the root.<br />
<br />
== Induction Basis ==<br />
'''Abstract view:''' <br />
# <math>p</math> is set to the input pointer.<br />
# <math>p_1</math> and <math>p_2</math> are void initially.<br />
<br />
'''Implementation:''' Obvious.<br />
<br />
'''Proof:''' The requirement on the input pointer immediately implies the invariants.<br />
<br />
== Induction Step ==<br />
'''Abstract view:'''<br />
# If the node is not full, the key can be inserted, and we are done.<br />
## If the new key is larger than all keys stored in the node, it can be appended.<br />
## Otherwise, is must override one specific slot. For that, first the contents of this slot and of each slot to its right must be moved one position further right (the corresponding values and successor pointers have to be moved as well). Then the new (key,value)-pair may be safely inserted.<br />
# On the other hand, if the node is indeed full, the key cannot be inserted. In this case:<br />
## The current node <math>N</math> will be split into two nodes, <math>N_1</math> and <math>N_2</math>.<br />
## <math>N_1</math> will contain all keys strictly less than the median of { <math>p.keys[1], ... , p.keys[p.n], K'</math> }<br />
## Analogously, <math>N_2</math> will contain all keys strictly greater than the median of { <math>p.keys[1], ... , p.keys[p.n], K'</math> }.<br />
## Next we try to<br />
## If <math>K'</math> is that median itself, nothing is to be done on the current node.<br />
## Otherwise, the median of <math>\{p.keys[1], \dots , p.keys[p.n], K'\}</math> is in one of the slots of the node. This slot is overridden (by moving the contents of each slot to the right one position further left). The previous contents of this slot is the new <math>K'</math> . If the current node is the root, which we next try to insert in the predecessor of<br />
<br />
'''Implementation:'''<br />
# If <math>p.n = 2M</math><br />
## If <math>p.keys[M] < K' < p.keys[M + 1]</math>, break the iteration and continue the loop.<br />
## Otherwise: <math> x:= M</math> if <math> K' < p.keys[M]</math>, and <math> x:= M+1</math> otherwise.<br />
## Set <math> K'' := p.keys[x]</math>.<br />
## For <math> j \in \{x+1, \dots, p.n \}</math> (in this order), set <math> p.keys [j-1]:= p.keys[j] </math> and <math>p. successor[j-1]:= p.successors[j]</math>.<br />
# If <math> p.keys[p.n] < K'</math>, insert the new (key, value)-pair at position <math>p.keys[p.n+1</math><br />
# Otherwise:<br />
## Let <math>i \in \{ 1, \dots , p.n \} </math> be minimal subject to <math>K' < p.keys[i]</math><br />
## For <math> j \in \{ p.n, \dots , i \} </math> (in this order), set <math> p.keys[j+1]:= p.keys[j]. </math><br />
# If <math> p.n < 2M</math>, set <math> p.n:= p.n+1</math> and terminate the algorithm.<br />
# Otherwise, set <math>K':= K''</math>.<br />
<br />
'''Correctness:''' Easy to see.<br />
<br />
== Complexity ==</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_merge_two_siblings&diff=452B-tree: merge two siblings2014-09-30T17:45:07Z<p>Lkw: /* Complexity */</p>
<hr />
<div>[[Category:B-Tree]]<br />
[[Category:Algorithm]]<br />
== General Information ==<br />
'''Algorithmic problem:''' See B-Tree<br />
<br />
'''Prerequisites:''' <br />
# A node <math>p</math> with a key at position <math>k</math> that is not void<br />
# The number of keys in <math>p.children[k-1]=p.children[k]=M-1</math><br />
<br />
'''Type of algorithm:''' loop<br />
<br />
'''Auxiliary data:''' <br />
# Three pointers <math>p, p_1, p_2 </math> of type "pointer to B-tree node".<br />
<br />
== Abstract View ==<br />
'''Invariant:''' After <math> i \ge 0</math> iterations:<br />
# <math> p_1</math> points to the left children of the key of <math>p</math> at position <math>k</math> and <math>p_2</math> points to the right children of the key of <math>p</math> at position <math>k</math>.<br />
# <math>p_1.n = M+i</math>.<br />
# <math>i</math> shows on the index of the copied key in <math>p_2</math>.<br />
<br />
'''Variant:''' <math>i</math> increases by <math>1</math>.<br />
<br />
'''Break condition:''' <math>i=M-1</math><br />
<br />
== Induction Basis ==<br />
'''Abstract view:''' <br />
# Assign <math>p_1</math> the left children of <math>p</math> at position <math>k</math> and <math>p_2</math> the right children of <math>p</math> at position <math>k</math>.<br />
# Move the key from <math>p</math> at position <math>k</math> to <math>p_1</math> at position <math>M</math>.<br />
# Copy the left children of <math>p_2</math> to the new key in <math>p1</math> at position <math>M</math><br />
# Change the number of keys in <math>p_1</math> and <math>p</math>.<br />
<br />
'''Implementation:''' <br />
# Set <math>p_1 := p.children[k-1]</math> and <math>p_2 := p.children[k]</math> and <math>p.children[k] := void</math>.<br />
# Set <math>p_1.keys[M] := p.keys[k]</math> and for <math>j \in k+1, \dots , p.n</math> (in this order), set <math>p.keys[j-1] := p.keys[j]</math> <br />
# Set <math>p_1.children[M] := p_2.children[0]</math><br />
# Set <math>p_1.n := p_1.n+1</math> and set <math>p.n := p.n-1</math><br />
<br />
'''Proof:''' In the induction basic <math>p_1</math> and <math>p_2</math> are assigned to the left and the right children of the key of <math>p</math> at position <math>k</math> (Invariant 1). The key of <math>p</math> at position <math>k</math> is shifted to <math>p_1</math> at position <math>M</math>. So the elements <math>1 \dots , M</math> are filled (B-Tree #5). The number of elements in <math>p_1</math> is increased by one and <math>p</math> is decreased by one (B-Tree #3). So are in <math>p_1 M</math> keys (Invariant 2). We removed a key of <math>p</math>, but because of the invariant of remove (<math>minM</math> keys in <math></math>), now we have <math>minM - 1</math> keys in <math>p</math> (B-Tree #4). We added the key from <math>p</math> to the left children (all keys in this children are smaller) on the right side, so the sorting order is correct again (B-Tree #6). The copied children comes from the right children, so all keys in this children are bigger again (B-Tree #7). The copied children come from the same level (<math>p_1</math> and <math>p_2</math> are both children of <math>p</math>), so all leaves are on the same level again (B-Tree #8). In the induction basic is no key copied from <math>p_2</math> (Invariant 3).<br />
<br />
== Induction Step ==<br />
'''Abstract view:'''<br />
# If not all keys (and children) of <math>p_2</math> are copied, copy the key and children from position <math>i</math> of <math>p_2</math> to position <math>M+i</math> of <math>p_1</math>.<br />
# Otherwise, terminate the algorithm.<br />
<br />
'''Implementation:'''<br />
# if <math>i \le M-1</math> (that is, not all keys of <math>p_2</math> are copied):<br />
## <math>p_1.keys[M+i] := p_2.keys[i].</math><br />
## <math>p_1.children[M+i] := p_2.children[i].</math><br />
## <math>p_1.n := p_1.n+1</math><br />
# Otherwise, terminate the algorithm.<br />
<br />
'''Correctness:''' In the induction step we copy a key and a children from <math>p_2</math> to <math>p_1</math>. The copy is in the same order as the elements and on the same level. Implementation invariants #1, #2, #4, #6, #7 and #8 are trivially fulfilled. In step 1.3 we increase <math>p_1.n</math> by one for each copied element (B-Tree #3).<br />
<br />
== Complexity ==<br />
<br />
'''Statement:''' Linear in <math>M-1</math> steps in the best and worst case<br />
<br />
'''Proof:''' Obvious.</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_merge_two_siblings&diff=451B-tree: merge two siblings2014-09-30T17:44:20Z<p>Lkw: /* Induction Step */</p>
<hr />
<div>[[Category:B-Tree]]<br />
[[Category:Algorithm]]<br />
== General Information ==<br />
'''Algorithmic problem:''' See B-Tree<br />
<br />
'''Prerequisites:''' <br />
# A node <math>p</math> with a key at position <math>k</math> that is not void<br />
# The number of keys in <math>p.children[k-1]=p.children[k]=M-1</math><br />
<br />
'''Type of algorithm:''' loop<br />
<br />
'''Auxiliary data:''' <br />
# Three pointers <math>p, p_1, p_2 </math> of type "pointer to B-tree node".<br />
<br />
== Abstract View ==<br />
'''Invariant:''' After <math> i \ge 0</math> iterations:<br />
# <math> p_1</math> points to the left children of the key of <math>p</math> at position <math>k</math> and <math>p_2</math> points to the right children of the key of <math>p</math> at position <math>k</math>.<br />
# <math>p_1.n = M+i</math>.<br />
# <math>i</math> shows on the index of the copied key in <math>p_2</math>.<br />
<br />
'''Variant:''' <math>i</math> increases by <math>1</math>.<br />
<br />
'''Break condition:''' <math>i=M-1</math><br />
<br />
== Induction Basis ==<br />
'''Abstract view:''' <br />
# Assign <math>p_1</math> the left children of <math>p</math> at position <math>k</math> and <math>p_2</math> the right children of <math>p</math> at position <math>k</math>.<br />
# Move the key from <math>p</math> at position <math>k</math> to <math>p_1</math> at position <math>M</math>.<br />
# Copy the left children of <math>p_2</math> to the new key in <math>p1</math> at position <math>M</math><br />
# Change the number of keys in <math>p_1</math> and <math>p</math>.<br />
<br />
'''Implementation:''' <br />
# Set <math>p_1 := p.children[k-1]</math> and <math>p_2 := p.children[k]</math> and <math>p.children[k] := void</math>.<br />
# Set <math>p_1.keys[M] := p.keys[k]</math> and for <math>j \in k+1, \dots , p.n</math> (in this order), set <math>p.keys[j-1] := p.keys[j]</math> <br />
# Set <math>p_1.children[M] := p_2.children[0]</math><br />
# Set <math>p_1.n := p_1.n+1</math> and set <math>p.n := p.n-1</math><br />
<br />
'''Proof:''' In the induction basic <math>p_1</math> and <math>p_2</math> are assigned to the left and the right children of the key of <math>p</math> at position <math>k</math> (Invariant 1). The key of <math>p</math> at position <math>k</math> is shifted to <math>p_1</math> at position <math>M</math>. So the elements <math>1 \dots , M</math> are filled (B-Tree #5). The number of elements in <math>p_1</math> is increased by one and <math>p</math> is decreased by one (B-Tree #3). So are in <math>p_1 M</math> keys (Invariant 2). We removed a key of <math>p</math>, but because of the invariant of remove (<math>minM</math> keys in <math></math>), now we have <math>minM - 1</math> keys in <math>p</math> (B-Tree #4). We added the key from <math>p</math> to the left children (all keys in this children are smaller) on the right side, so the sorting order is correct again (B-Tree #6). The copied children comes from the right children, so all keys in this children are bigger again (B-Tree #7). The copied children come from the same level (<math>p_1</math> and <math>p_2</math> are both children of <math>p</math>), so all leaves are on the same level again (B-Tree #8). In the induction basic is no key copied from <math>p_2</math> (Invariant 3).<br />
<br />
== Induction Step ==<br />
'''Abstract view:'''<br />
# If not all keys (and children) of <math>p_2</math> are copied, copy the key and children from position <math>i</math> of <math>p_2</math> to position <math>M+i</math> of <math>p_1</math>.<br />
# Otherwise, terminate the algorithm.<br />
<br />
'''Implementation:'''<br />
# if <math>i \le M-1</math> (that is, not all keys of <math>p_2</math> are copied):<br />
## <math>p_1.keys[M+i] := p_2.keys[i].</math><br />
## <math>p_1.children[M+i] := p_2.children[i].</math><br />
## <math>p_1.n := p_1.n+1</math><br />
# Otherwise, terminate the algorithm.<br />
<br />
'''Correctness:''' In the induction step we copy a key and a children from <math>p_2</math> to <math>p_1</math>. The copy is in the same order as the elements and on the same level. Implementation invariants #1, #2, #4, #6, #7 and #8 are trivially fulfilled. In step 1.3 we increase <math>p_1.n</math> by one for each copied element (B-Tree #3).<br />
<br />
== Complexity ==</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_merge_two_siblings&diff=445B-tree: merge two siblings2014-09-30T17:38:42Z<p>Lkw: /* Induction Basis */</p>
<hr />
<div>[[Category:B-Tree]]<br />
[[Category:Algorithm]]<br />
== General Information ==<br />
'''Algorithmic problem:''' See B-Tree<br />
<br />
'''Prerequisites:''' <br />
# A node <math>p</math> with a key at position <math>k</math> that is not void<br />
# The number of keys in <math>p.children[k-1]=p.children[k]=M-1</math><br />
<br />
'''Type of algorithm:''' loop<br />
<br />
'''Auxiliary data:''' <br />
# Three pointers <math>p, p_1, p_2 </math> of type "pointer to B-tree node".<br />
<br />
== Abstract View ==<br />
'''Invariant:''' After <math> i \ge 0</math> iterations:<br />
# <math> p_1</math> points to the left children of the key of <math>p</math> at position <math>k</math> and <math>p_2</math> points to the right children of the key of <math>p</math> at position <math>k</math>.<br />
# <math>p_1.n = M+i</math>.<br />
# <math>i</math> shows on the index of the copied key in <math>p_2</math>.<br />
<br />
'''Variant:''' <math>i</math> increases by <math>1</math>.<br />
<br />
'''Break condition:''' <math>i=M-1</math><br />
<br />
== Induction Basis ==<br />
'''Abstract view:''' <br />
# Assign <math>p_1</math> the left children of <math>p</math> at position <math>k</math> and <math>p_2</math> the right children of <math>p</math> at position <math>k</math>.<br />
# Move the key from <math>p</math> at position <math>k</math> to <math>p_1</math> at position <math>M</math>.<br />
# Copy the left children of <math>p_2</math> to the new key in <math>p1</math> at position <math>M</math><br />
# Change the number of keys in <math>p_1</math> and <math>p</math>.<br />
<br />
'''Implementation:''' <br />
# Set <math>p_1 := p.children[k-1]</math> and <math>p_2 := p.children[k]</math> and <math>p.children[k] := void</math>.<br />
# Set <math>p_1.keys[M] := p.keys[k]</math> and for <math>j \in k+1, \dots , p.n</math> (in this order), set <math>p.keys[j-1] := p.keys[j]</math> <br />
# Set <math>p_1.children[M] := p_2.children[0]</math><br />
# Set <math>p_1.n := p_1.n+1</math> and set <math>p.n := p.n-1</math><br />
<br />
'''Proof:''' In the induction basic <math>p_1</math> and <math>p_2</math> are assigned to the left and the right children of the key of <math>p</math> at position <math>k</math> (Invariant 1). The key of <math>p</math> at position <math>k</math> is shifted to <math>p_1</math> at position <math>M</math>. So the elements <math>1 \dots , M</math> are filled (B-Tree #5). The number of elements in <math>p_1</math> is increased by one and <math>p</math> is decreased by one (B-Tree #3). So are in <math>p_1 M</math> keys (Invariant 2). We removed a key of <math>p</math>, but because of the invariant of remove (<math>minM</math> keys in <math></math>), now we have <math>minM - 1</math> keys in <math>p</math> (B-Tree #4). We added the key from <math>p</math> to the left children (all keys in this children are smaller) on the right side, so the sorting order is correct again (B-Tree #6). The copied children comes from the right children, so all keys in this children are bigger again (B-Tree #7). The copied children come from the same level (<math>p_1</math> and <math>p_2</math> are both children of <math>p</math>), so all leaves are on the same level again (B-Tree #8). In the induction basic is no key copied from <math>p_2</math> (Invariant 3).<br />
<br />
== Induction Step ==<br />
'''Abstract view:'''<br />
# If the node is not full, the key can be inserted, and we are done.<br />
## If the new key is larger than all keys stored in the node, it can be appended.<br />
## Otherwise, is must override one specific slot. For that, first the contents of this slot and of each slot to its right must be moved one position further right (the corresponding values and successor pointers have to be moved as well). Then the new (key,value)-pair may be safely inserted.<br />
# On the other hand, if the node is indeed full, the key cannot be inserted. In this case:<br />
## The current node <math>N</math> will be split into two nodes, <math>N_1</math> and <math>N_2</math>.<br />
## <math>N_1</math> will contain all keys strictly less than the median of { <math>p.keys[1], ... , p.keys[p.n], K'</math> }<br />
## Analogously, <math>N_2</math> will contain all keys strictly greater than the median of { <math>p.keys[1], ... , p.keys[p.n], K'</math> }.<br />
## Next we try to<br />
## If <math>K'</math> is that median itself, nothing is to be done on the current node.<br />
## Otherwise, the median of <math>\{p.keys[1], \dots , p.keys[p.n], K'\}</math> is in one of the slots of the node. This slot is overridden (by moving the contents of each slot to the right one position further left). The previous contents of this slot is the new <math>K'</math> . If the current node is the root, which we next try to insert in the predecessor of<br />
<br />
'''Implementation:'''<br />
# If <math>p.n = 2M</math><br />
## If <math>p.keys[M] < K' < p.keys[M + 1]</math>, break the iteration and continue the loop.<br />
## Otherwise: <math> x:= M</math> if <math> K' < p.keys[M]</math>, and <math> x:= M+1</math> otherwise.<br />
## Set <math> K'' := p.keys[x]</math>.<br />
## For <math> j \in \{x+1, \dots, p.n \}</math> (in this order), set <math> p.keys [j-1]:= p.keys[j] </math> and <math>p. successor[j-1]:= p.successors[j]</math>.<br />
# If <math> p.keys[p.n] < K'</math>, insert the new (key, value)-pair at position <math>p.keys[p.n+1</math><br />
# Otherwise:<br />
## Let <math>i \in \{ 1, \dots , p.n \} </math> be minimal subject to <math>K' < p.keys[i]</math><br />
## For <math> j \in \{ p.n, \dots , i \} </math> (in this order), set <math> p.keys[j+1]:= p.keys[j]. </math><br />
# If <math> p.n < 2M</math>, set <math> p.n:= p.n+1</math> and terminate the algorithm.<br />
# Otherwise, set <math>K':= K''</math>.<br />
<br />
'''Correctness:''' Easy to see.<br />
<br />
== Complexity ==</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_merge_two_siblings&diff=441B-tree: merge two siblings2014-09-30T17:25:07Z<p>Lkw: /* Abstract View */</p>
<hr />
<div>[[Category:B-Tree]]<br />
[[Category:Algorithm]]<br />
== General Information ==<br />
'''Algorithmic problem:''' See B-Tree<br />
<br />
'''Prerequisites:''' <br />
# A node <math>p</math> with a key at position <math>k</math> that is not void<br />
# The number of keys in <math>p.children[k-1]=p.children[k]=M-1</math><br />
<br />
'''Type of algorithm:''' loop<br />
<br />
'''Auxiliary data:''' <br />
# Three pointers <math>p, p_1, p_2 </math> of type "pointer to B-tree node".<br />
<br />
== Abstract View ==<br />
'''Invariant:''' After <math> i \ge 0</math> iterations:<br />
# <math> p_1</math> points to the left children of the key of <math>p</math> at position <math>k</math> and <math>p_2</math> points to the right children of the key of <math>p</math> at position <math>k</math>.<br />
# <math>p_1.n = M+i</math>.<br />
# <math>i</math> shows on the index of the copied key in <math>p_2</math>.<br />
<br />
'''Variant:''' <math>i</math> increases by <math>1</math>.<br />
<br />
'''Break condition:''' <math>i=M-1</math><br />
<br />
== Induction Basis ==<br />
'''Abstract view:''' <br />
# <math>p</math> is set to the input pointer.<br />
# <math>p_1</math> and <math>p_2</math> are void initially.<br />
<br />
'''Implementation:''' Obvious.<br />
<br />
'''Proof:''' The requirement on the input pointer immediately implies the invariants.<br />
<br />
== Induction Step ==<br />
'''Abstract view:'''<br />
# If the node is not full, the key can be inserted, and we are done.<br />
## If the new key is larger than all keys stored in the node, it can be appended.<br />
## Otherwise, is must override one specific slot. For that, first the contents of this slot and of each slot to its right must be moved one position further right (the corresponding values and successor pointers have to be moved as well). Then the new (key,value)-pair may be safely inserted.<br />
# On the other hand, if the node is indeed full, the key cannot be inserted. In this case:<br />
## The current node <math>N</math> will be split into two nodes, <math>N_1</math> and <math>N_2</math>.<br />
## <math>N_1</math> will contain all keys strictly less than the median of { <math>p.keys[1], ... , p.keys[p.n], K'</math> }<br />
## Analogously, <math>N_2</math> will contain all keys strictly greater than the median of { <math>p.keys[1], ... , p.keys[p.n], K'</math> }.<br />
## Next we try to<br />
## If <math>K'</math> is that median itself, nothing is to be done on the current node.<br />
## Otherwise, the median of <math>\{p.keys[1], \dots , p.keys[p.n], K'\}</math> is in one of the slots of the node. This slot is overridden (by moving the contents of each slot to the right one position further left). The previous contents of this slot is the new <math>K'</math> . If the current node is the root, which we next try to insert in the predecessor of<br />
<br />
'''Implementation:'''<br />
# If <math>p.n = 2M</math><br />
## If <math>p.keys[M] < K' < p.keys[M + 1]</math>, break the iteration and continue the loop.<br />
## Otherwise: <math> x:= M</math> if <math> K' < p.keys[M]</math>, and <math> x:= M+1</math> otherwise.<br />
## Set <math> K'' := p.keys[x]</math>.<br />
## For <math> j \in \{x+1, \dots, p.n \}</math> (in this order), set <math> p.keys [j-1]:= p.keys[j] </math> and <math>p. successor[j-1]:= p.successors[j]</math>.<br />
# If <math> p.keys[p.n] < K'</math>, insert the new (key, value)-pair at position <math>p.keys[p.n+1</math><br />
# Otherwise:<br />
## Let <math>i \in \{ 1, \dots , p.n \} </math> be minimal subject to <math>K' < p.keys[i]</math><br />
## For <math> j \in \{ p.n, \dots , i \} </math> (in this order), set <math> p.keys[j+1]:= p.keys[j]. </math><br />
# If <math> p.n < 2M</math>, set <math> p.n:= p.n+1</math> and terminate the algorithm.<br />
# Otherwise, set <math>K':= K''</math>.<br />
<br />
'''Correctness:''' Easy to see.<br />
<br />
== Complexity ==</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_merge_two_siblings&diff=440B-tree: merge two siblings2014-09-30T17:24:42Z<p>Lkw: /* General Information */</p>
<hr />
<div>[[Category:B-Tree]]<br />
[[Category:Algorithm]]<br />
== General Information ==<br />
'''Algorithmic problem:''' See B-Tree<br />
<br />
'''Prerequisites:''' <br />
# A node <math>p</math> with a key at position <math>k</math> that is not void<br />
# The number of keys in <math>p.children[k-1]=p.children[k]=M-1</math><br />
<br />
'''Type of algorithm:''' loop<br />
<br />
'''Auxiliary data:''' <br />
# Three pointers <math>p, p_1, p_2 </math> of type "pointer to B-tree node".<br />
<br />
== Abstract View ==<br />
'''Invariant:''' After <math> i \ge 0</math> iterations:<br />
# <math> p_1</math> points to the left children of the key of <math>p</math> at position <math>k</math> and <math>p_2</math> points to the right children of the key of <math>p</math> at position <math>k</math>.<br />
# <math>p_1.n = M+i</math>.<br />
# <math>i</math> shows on the index of the copied key in <math>p_2</math>.<br />
<br />
'''Variant:''' <math>i</math> increases by <math>1</math>.<br />
<br />
'''Break condition:''' <math>i=M-1</math><br />
<br />
<br />
Before and after each iteration, <math>p</math> points to a node <math>N</math> such that the following holds: <br />
# In the case <math>p.n < 2M</math>, all implementation invariants of B-trees are maintained if the following <math>K'</math> can be inserted at some position in <math>N</math> such that after insertion.<br />
# In the case <math>p.n = 2M</math>, imagine that we could extend <math>p</math>.keys by one more slot (and, consequently, extend .successors by one more slot). Then <math>K'</math> can be inserted in <math>N</math> at a position such that - except for the statement about the size of <math>N</math> - all implementation invariants of B-trees are again maintained after insertion.<br />
<br />
'''Variant:''' The height level of the node to which <math>p</math> points is decreased by <math>1</math>.<br />
<br />
'''Break condition:''' <math>p.N < 2M</math> or (that is, inclusive-or) <math>p</math> points to the root.<br />
<br />
== Induction Basis ==<br />
'''Abstract view:''' <br />
# <math>p</math> is set to the input pointer.<br />
# <math>p_1</math> and <math>p_2</math> are void initially.<br />
<br />
'''Implementation:''' Obvious.<br />
<br />
'''Proof:''' The requirement on the input pointer immediately implies the invariants.<br />
<br />
== Induction Step ==<br />
'''Abstract view:'''<br />
# If the node is not full, the key can be inserted, and we are done.<br />
## If the new key is larger than all keys stored in the node, it can be appended.<br />
## Otherwise, is must override one specific slot. For that, first the contents of this slot and of each slot to its right must be moved one position further right (the corresponding values and successor pointers have to be moved as well). Then the new (key,value)-pair may be safely inserted.<br />
# On the other hand, if the node is indeed full, the key cannot be inserted. In this case:<br />
## The current node <math>N</math> will be split into two nodes, <math>N_1</math> and <math>N_2</math>.<br />
## <math>N_1</math> will contain all keys strictly less than the median of { <math>p.keys[1], ... , p.keys[p.n], K'</math> }<br />
## Analogously, <math>N_2</math> will contain all keys strictly greater than the median of { <math>p.keys[1], ... , p.keys[p.n], K'</math> }.<br />
## Next we try to<br />
## If <math>K'</math> is that median itself, nothing is to be done on the current node.<br />
## Otherwise, the median of <math>\{p.keys[1], \dots , p.keys[p.n], K'\}</math> is in one of the slots of the node. This slot is overridden (by moving the contents of each slot to the right one position further left). The previous contents of this slot is the new <math>K'</math> . If the current node is the root, which we next try to insert in the predecessor of<br />
<br />
'''Implementation:'''<br />
# If <math>p.n = 2M</math><br />
## If <math>p.keys[M] < K' < p.keys[M + 1]</math>, break the iteration and continue the loop.<br />
## Otherwise: <math> x:= M</math> if <math> K' < p.keys[M]</math>, and <math> x:= M+1</math> otherwise.<br />
## Set <math> K'' := p.keys[x]</math>.<br />
## For <math> j \in \{x+1, \dots, p.n \}</math> (in this order), set <math> p.keys [j-1]:= p.keys[j] </math> and <math>p. successor[j-1]:= p.successors[j]</math>.<br />
# If <math> p.keys[p.n] < K'</math>, insert the new (key, value)-pair at position <math>p.keys[p.n+1</math><br />
# Otherwise:<br />
## Let <math>i \in \{ 1, \dots , p.n \} </math> be minimal subject to <math>K' < p.keys[i]</math><br />
## For <math> j \in \{ p.n, \dots , i \} </math> (in this order), set <math> p.keys[j+1]:= p.keys[j]. </math><br />
# If <math> p.n < 2M</math>, set <math> p.n:= p.n+1</math> and terminate the algorithm.<br />
# Otherwise, set <math>K':= K''</math>.<br />
<br />
'''Correctness:''' Easy to see.<br />
<br />
== Complexity ==</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_merge_two_siblings&diff=439B-tree: merge two siblings2014-09-30T17:24:11Z<p>Lkw: Created page with "Category:B-Tree Category:Algorithm == General Information == '''Algorithmic problem:''' See B-Tree '''Prerequisites:''' # A node <math>p</math> with a key at positio..."</p>
<hr />
<div>[[Category:B-Tree]]<br />
[[Category:Algorithm]]<br />
== General Information ==<br />
'''Algorithmic problem:''' See B-Tree<br />
<br />
'''Prerequisites:''' <br />
# A node <math>p</math> with a key at position <math>k</math> that is not void<br />
# The number of keys in <math>p.children[k-1]=p.children[k]=M-1</math><br />
<br />
'''Type of algorithm:''' loop<br />
'''Auxiliary data:''' <br />
# Three pointers <math>p, p_1, p_2 </math> of type "pointer to B-tree node".<br />
<br />
<br />
== Abstract View ==<br />
'''Invariant:''' After <math> i \ge 0</math> iterations:<br />
# <math> p_1</math> points to the left children of the key of <math>p</math> at position <math>k</math> and <math>p_2</math> points to the right children of the key of <math>p</math> at position <math>k</math>.<br />
# <math>p_1.n = M+i</math>.<br />
# <math>i</math> shows on the index of the copied key in <math>p_2</math>.<br />
<br />
'''Variant:''' <math>i</math> increases by <math>1</math>.<br />
<br />
'''Break condition:''' <math>i=M-1</math><br />
<br />
<br />
Before and after each iteration, <math>p</math> points to a node <math>N</math> such that the following holds: <br />
# In the case <math>p.n < 2M</math>, all implementation invariants of B-trees are maintained if the following <math>K'</math> can be inserted at some position in <math>N</math> such that after insertion.<br />
# In the case <math>p.n = 2M</math>, imagine that we could extend <math>p</math>.keys by one more slot (and, consequently, extend .successors by one more slot). Then <math>K'</math> can be inserted in <math>N</math> at a position such that - except for the statement about the size of <math>N</math> - all implementation invariants of B-trees are again maintained after insertion.<br />
<br />
'''Variant:''' The height level of the node to which <math>p</math> points is decreased by <math>1</math>.<br />
<br />
'''Break condition:''' <math>p.N < 2M</math> or (that is, inclusive-or) <math>p</math> points to the root.<br />
<br />
== Induction Basis ==<br />
'''Abstract view:''' <br />
# <math>p</math> is set to the input pointer.<br />
# <math>p_1</math> and <math>p_2</math> are void initially.<br />
<br />
'''Implementation:''' Obvious.<br />
<br />
'''Proof:''' The requirement on the input pointer immediately implies the invariants.<br />
<br />
== Induction Step ==<br />
'''Abstract view:'''<br />
# If the node is not full, the key can be inserted, and we are done.<br />
## If the new key is larger than all keys stored in the node, it can be appended.<br />
## Otherwise, is must override one specific slot. For that, first the contents of this slot and of each slot to its right must be moved one position further right (the corresponding values and successor pointers have to be moved as well). Then the new (key,value)-pair may be safely inserted.<br />
# On the other hand, if the node is indeed full, the key cannot be inserted. In this case:<br />
## The current node <math>N</math> will be split into two nodes, <math>N_1</math> and <math>N_2</math>.<br />
## <math>N_1</math> will contain all keys strictly less than the median of { <math>p.keys[1], ... , p.keys[p.n], K'</math> }<br />
## Analogously, <math>N_2</math> will contain all keys strictly greater than the median of { <math>p.keys[1], ... , p.keys[p.n], K'</math> }.<br />
## Next we try to<br />
## If <math>K'</math> is that median itself, nothing is to be done on the current node.<br />
## Otherwise, the median of <math>\{p.keys[1], \dots , p.keys[p.n], K'\}</math> is in one of the slots of the node. This slot is overridden (by moving the contents of each slot to the right one position further left). The previous contents of this slot is the new <math>K'</math> . If the current node is the root, which we next try to insert in the predecessor of<br />
<br />
'''Implementation:'''<br />
# If <math>p.n = 2M</math><br />
## If <math>p.keys[M] < K' < p.keys[M + 1]</math>, break the iteration and continue the loop.<br />
## Otherwise: <math> x:= M</math> if <math> K' < p.keys[M]</math>, and <math> x:= M+1</math> otherwise.<br />
## Set <math> K'' := p.keys[x]</math>.<br />
## For <math> j \in \{x+1, \dots, p.n \}</math> (in this order), set <math> p.keys [j-1]:= p.keys[j] </math> and <math>p. successor[j-1]:= p.successors[j]</math>.<br />
# If <math> p.keys[p.n] < K'</math>, insert the new (key, value)-pair at position <math>p.keys[p.n+1</math><br />
# Otherwise:<br />
## Let <math>i \in \{ 1, \dots , p.n \} </math> be minimal subject to <math>K' < p.keys[i]</math><br />
## For <math> j \in \{ p.n, \dots , i \} </math> (in this order), set <math> p.keys[j+1]:= p.keys[j]. </math><br />
# If <math> p.n < 2M</math>, set <math> p.n:= p.n+1</math> and terminate the algorithm.<br />
# Otherwise, set <math>K':= K''</math>.<br />
<br />
'''Correctness:''' Easy to see.<br />
<br />
== Complexity ==</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_insert_and_rearrange&diff=435B-tree: insert and rearrange2014-09-30T17:18:06Z<p>Lkw: /* General Information */</p>
<hr />
<div>[[Category:B-Tree]]<br />
[[Category:Algorithm]]<br />
== General Information ==<br />
'''Algorithmic problem:''' [[Text here]]<br />
<br />
'''Type of algorithm:''' Text<br />
<br />
'''Auxiliary data:''' <br />
# Three pointers <math>p, p_1, p_2 </math> of type "pointer to B-tree node".<br />
# A current key <math> K' \in K</math><br />
<br />
== Abstract View ==<br />
'''Invariant:''' Before and after each iteration, <math>p</math> points to a node <math>N</math> such that the following holds: <br />
# In the case <math>p.n < 2M</math>, all implementation invariants of B-trees are maintained if the following <math>K'</math> can be inserted at some position in <math>N</math> such that after insertion.<br />
# In the case <math>p.n = 2M</math>, imagine that we could extend <math>p</math>.keys by one more slot (and, consequently, extend .successors by one more slot). Then <math>K'</math> can be inserted in <math>N</math> at a position such that - except for the statement about the size of <math>N</math> - all implementation invariants of B-trees are again maintained after insertion.<br />
<br />
'''Variant:''' The height level of the node to which <math>p</math> points is decreased by <math>1</math>.<br />
<br />
'''Break condition:''' <math>p.N < 2M</math> or (that is, inclusive-or) <math>p</math> points to the root.<br />
<br />
== Induction Basis ==<br />
'''Abstract view:''' <br />
# <math>p</math> is set to the input pointer.<br />
# <math>p_1</math> and <math>p_2</math> are void initially.<br />
<br />
'''Implementation:''' Obvious.<br />
<br />
'''Proof:''' The requirement on the input pointer immediately implies the invariants.<br />
<br />
== Induction Step ==<br />
'''Abstract view:'''<br />
# If the node is not full, the key can be inserted, and we are done.<br />
## If the new key is larger than all keys stored in the node, it can be appended.<br />
## Otherwise, is must override one specific slot. For that, first the contents of this slot and of each slot to its right must be moved one position further right (the corresponding values and successor pointers have to be moved as well). Then the new (key,value)-pair may be safely inserted.<br />
# On the other hand, if the node is indeed full, the key cannot be inserted. In this case:<br />
## The current node <math>N</math> will be split into two nodes, <math>N_1</math> and <math>N_2</math>.<br />
## <math>N_1</math> will contain all keys strictly less than the median of { <math>p.keys[1], ... , p.keys[p.n], K'</math> }<br />
## Analogously, <math>N_2</math> will contain all keys strictly greater than the median of { <math>p.keys[1], ... , p.keys[p.n], K'</math> }.<br />
## Next we try to<br />
## If <math>K'</math> is that median itself, nothing is to be done on the current node.<br />
## Otherwise, the median of <math>\{p.keys[1], \dots , p.keys[p.n], K'\}</math> is in one of the slots of the node. This slot is overridden (by moving the contents of each slot to the right one position further left). The previous contents of this slot is the new <math>K'</math> . If the current node is the root, which we next try to insert in the predecessor of<br />
<br />
'''Implementation:'''<br />
# If <math>p.n = 2M</math><br />
## If <math>p.keys[M] < K' < p.keys[M + 1]</math>, break the iteration and continue the loop.<br />
## Otherwise: <math> x:= M</math> if <math> K' < p.keys[M]</math>, and <math> x:= M+1</math> otherwise.<br />
## Set <math> K'' := p.keys[x]</math>.<br />
## For <math> j \in \{x+1, \dots, p.n \}</math> (in this order), set <math> p.keys [j-1]:= p.keys[j] </math> and <math>p. successor[j-1]:= p.successors[j]</math>.<br />
# If <math> p.keys[p.n] < K'</math>, insert the new (key, value)-pair at position <math>p.keys[p.n+1</math><br />
# Otherwise:<br />
## Let <math>i \in \{ 1, \dots , p.n \} </math> be minimal subject to <math>K' < p.keys[i]</math><br />
## For <math> j \in \{ p.n, \dots , i \} </math> (in this order), set <math> p.keys[j+1]:= p.keys[j]. </math><br />
# If <math> p.n < 2M</math>, set <math> p.n:= p.n+1</math> and terminate the algorithm.<br />
# Otherwise, set <math>K':= K''</math>.<br />
<br />
'''Correctness:''' Easy to see.<br />
<br />
== Complexity ==</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_insert_and_rearrange&diff=432B-tree: insert and rearrange2014-09-30T17:07:53Z<p>Lkw: </p>
<hr />
<div>[[Category:B-Tree]]<br />
[[Category:Algorithm]]<br />
== General Information ==<br />
'''Algorithmic problem:''' [[Text here]]<br />
<br />
'''Type of algorithm:''' Text<br />
<br />
'''Auxiliary data:''' <br />
# Three pointers <math>p, p_1, p_2 </math> or type "pointer to B-tree node".<br />
# A current key <math> K' \in K</math><br />
<br />
== Abstract View ==<br />
'''Invariant:''' Before and after each iteration, <math>p</math> points to a node <math>N</math> such that the following holds: <br />
# In the case <math>p.n < 2M</math>, all implementation invariants of B-trees are maintained if the following <math>K'</math> can be inserted at some position in <math>N</math> such that after insertion.<br />
# In the case <math>p.n = 2M</math>, imagine that we could extend <math>p</math>.keys by one more slot (and, consequently, extend .successors by one more slot). Then <math>K'</math> can be inserted in <math>N</math> at a position such that - except for the statement about the size of <math>N</math> - all implementation invariants of B-trees are again maintained after insertion.<br />
<br />
'''Variant:''' The height level of the node to which <math>p</math> points is decreased by <math>1</math>.<br />
<br />
'''Break condition:''' <math>p.N < 2M</math> or (that is, inclusive-or) <math>p</math> points to the root.<br />
<br />
== Induction Basis ==<br />
'''Abstract view:''' <br />
# <math>p</math> is set to the input pointer.<br />
# <math>p_1</math> and <math>p_2</math> are void initially.<br />
<br />
'''Implementation:''' Obvious.<br />
<br />
'''Proof:''' The requirement on the input pointer immediately implies the invariants.<br />
<br />
== Induction Step ==<br />
'''Abstract view:'''<br />
# If the node is not full, the key can be inserted, and we are done.<br />
## If the new key is larger than all keys stored in the node, it can be appended.<br />
## Otherwise, is must override one specific slot. For that, first the contents of this slot and of each slot to its right must be moved one position further right (the corresponding values and successor pointers have to be moved as well). Then the new (key,value)-pair may be safely inserted.<br />
# On the other hand, if the node is indeed full, the key cannot be inserted. In this case:<br />
## The current node <math>N</math> will be split into two nodes, <math>N_1</math> and <math>N_2</math>.<br />
## <math>N_1</math> will contain all keys strictly less than the median of { <math>p.keys[1], ... , p.keys[p.n], K'</math> }<br />
## Analogously, <math>N_2</math> will contain all keys strictly greater than the median of { <math>p.keys[1], ... , p.keys[p.n], K'</math> }.<br />
## Next we try to<br />
## If <math>K'</math> is that median itself, nothing is to be done on the current node.<br />
## Otherwise, the median of <math>\{p.keys[1], \dots , p.keys[p.n], K'\}</math> is in one of the slots of the node. This slot is overridden (by moving the contents of each slot to the right one position further left). The previous contents of this slot is the new <math>K'</math> . If the current node is the root, which we next try to insert in the predecessor of<br />
<br />
'''Implementation:'''<br />
# If <math>p.n = 2M</math><br />
## If <math>p.keys[M] < K' < p.keys[M + 1]</math>, break the iteration and continue the loop.<br />
## Otherwise: <math> x:= M</math> if <math> K' < p.keys[M]</math>, and <math> x:= M+1</math> otherwise.<br />
## Set <math> K'' := p.keys[x]</math>.<br />
## For <math> j \in \{x+1, \dots, p.n \}</math> (in this order), set <math> p.keys [j-1]:= p.keys[j] </math> and <math>p. successor[j-1]:= p.successors[j]</math>.<br />
# If <math> p.keys[p.n] < K'</math>, insert the new (key, value)-pair at position <math>p.keys[p.n+1</math><br />
# Otherwise:<br />
## Let <math>i \in \{ 1, \dots , p.n \} </math> be minimal subject to <math>K' < p.keys[i]</math><br />
## For <math> j \in \{ p.n, \dots , i \} </math> (in this order), set <math> p.keys[j+1]:= p.keys[j]. </math><br />
# If <math> p.n < 2M</math>, set <math> p.n:= p.n+1</math> and terminate the algorithm.<br />
# Otherwise, set <math>K':= K''</math>.<br />
<br />
'''Correctness:''' Easy to see.<br />
<br />
== Complexity ==</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_insert_and_rearrange&diff=431B-tree: insert and rearrange2014-09-30T17:07:04Z<p>Lkw: /* Induction Step */</p>
<hr />
<div>[[Category:B-Tree]]<br />
[[Category:Algorithm]]<br />
== General Information ==<br />
'''Algorithmic problem:''' [[Text here]]<br />
<br />
'''Type of algorithm:''' Text<br />
<br />
'''Auxiliary data:''' <br />
# Three pointers <math>p, p_1, p_2 </math> or type "pointer to B-tree node".<br />
# A current key <math> K' \in K</math><br />
<br />
== Abstract View ==<br />
'''Invariant:''' Before and after each iteration, <math>p</math> points to a node <math>N</math> such that the following holds: <br />
# In the case <math>p.n < 2M</math>, all implementation invariants of B-trees are maintained if the following <math>K'</math> can be inserted at some position in <math>N</math> such that after insertion.<br />
# In the case <math>p.n = 2M</math>, imagine that we could extend <math>p</math>.keys by one more slot (and, consequently, extend .successors by one more slot). Then <math>K'</math> can be inserted in <math>N</math> at a position such that - except for the statement about the size of <math>N</math> - all implementation invariants of B-trees are again maintained after insertion.<br />
<br />
'''Variant:''' The height level of the node to which <math>p</math> points is decreased by <math>1</math>.<br />
<br />
'''Break condition:''' <math>p.N < 2M</math> or (that is, inclusive-or) <math>p</math> points to the root.<br />
<br />
== Induction Basis ==<br />
'''Abstract view:''' <br />
# <math>p</math> is set to the input pointer.<br />
# <math>p_1</math> and <math>p_2</math> are void initially.<br />
<br />
'''Implementation:''' Obvious.<br />
<br />
'''Proof:''' The requirement on the input pointer immediately implies the invariants.<br />
<br />
== Induction Step ==<br />
'''Abstract view:'''<br />
# If the node is not full, the key can be inserted, and we are done.<br />
## If the new key is larger than all keys stored in the node, it can be appended.<br />
## Otherwise, is must override one specific slot. For that, first the contents of this slot and of each slot to its right must be moved one position further right (the corresponding values and successor pointers have to be moved as well). Then the new (key,value)-pair may be safely inserted.<br />
# On the other hand, if the node is indeed full, the key cannot be inserted. In this case:<br />
## The current node <math>N</math> will be split into two nodes, <math>N_1</math> and <math>N_2</math>.<br />
## <math>N_1</math> will contain all keys strictly less than the median of { <math>p.keys[1], ... , p.keys[p.n], K'</math> }<br />
## Analogously, <math>N_2</math> will contain all keys strictly greater than the median of { <math>p.keys[1], ... , p.keys[p.n], K'</math> }.<br />
## Next we try to<br />
## If <math>K'</math> is that median itself, nothing is to be done on the current node.<br />
## Otherwise, the median of <math>\{p.keys[1], \dots , p.keys[p.n], K'\}</math> is in one of the slots of the node. This slot is overridden (by moving the contents of each slot to the right one position further left). The previous contents of this slot is the new <math>K'</math> . If the current node is the root, which we next try to insert in the predecessor of<br />
<br />
'''Implementation:'''<br />
# If <math>p.n = 2M</math><br />
## If <math>p.keys[M] < K' < p.keys[M + 1]</math>, break the iteration and continue the loop.<br />
## Otherwise: <math> x:= M</math> if <math> K' < p.keys[M]</math>, and <math> x:= M+1</math> otherwise.<br />
## Set <math> K'' := p.keys[x]</math>.<br />
## For <math> j \in \{x+1, \dots, p.n \}</math> (in this order), set <math> p.keys [j-1]:= p.keys[j] </math> and <math>p. successor[j-1]:= p.successors[j]</math>.<br />
# If <math> p.keys[p.n] < K'</math>, insert the new (key, value)-pair at position <math>p.keys[p.n+1</math><br />
# Otherwise:<br />
## Let <math>i \in \{ 1, \dots , p.n \} </math> be minimal subject to <math>K' < p.keys[i]</math><br />
## For <math> j \in \{ p.n, \dots , i \} </math> (in this order), set <math> p.keys[j+1]:= p.keys[j]. </math><br />
# If <math> p.n < 2M</math>, set <math> p.n:= p.n+1</math> and terminate the algorithm.<br />
# Otherwise, set <math>K':= K''</math>.<br />
<br />
== Complexity ==<br />
<br />
'''Statement:''' The asymptotic complexity is in <math>\Theta(\log n)</math> in the worst case.<br />
<br />
'''Proof:''' Follows immediately from the fact that the height of B-tree with '''''n''''' nodes is in <math>\Theta(\log n)</math> (cf. the remark clause of the [[B-Trees]] page).</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_insert_and_rearrange&diff=430B-tree: insert and rearrange2014-09-30T17:05:24Z<p>Lkw: /* Induction Step */</p>
<hr />
<div>[[Category:B-Tree]]<br />
[[Category:Algorithm]]<br />
== General Information ==<br />
'''Algorithmic problem:''' [[Text here]]<br />
<br />
'''Type of algorithm:''' Text<br />
<br />
'''Auxiliary data:''' <br />
# Three pointers <math>p, p_1, p_2 </math> or type "pointer to B-tree node".<br />
# A current key <math> K' \in K</math><br />
<br />
== Abstract View ==<br />
'''Invariant:''' Before and after each iteration, <math>p</math> points to a node <math>N</math> such that the following holds: <br />
# In the case <math>p.n < 2M</math>, all implementation invariants of B-trees are maintained if the following <math>K'</math> can be inserted at some position in <math>N</math> such that after insertion.<br />
# In the case <math>p.n = 2M</math>, imagine that we could extend <math>p</math>.keys by one more slot (and, consequently, extend .successors by one more slot). Then <math>K'</math> can be inserted in <math>N</math> at a position such that - except for the statement about the size of <math>N</math> - all implementation invariants of B-trees are again maintained after insertion.<br />
<br />
'''Variant:''' The height level of the node to which <math>p</math> points is decreased by <math>1</math>.<br />
<br />
'''Break condition:''' <math>p.N < 2M</math> or (that is, inclusive-or) <math>p</math> points to the root.<br />
<br />
== Induction Basis ==<br />
'''Abstract view:''' <br />
# <math>p</math> is set to the input pointer.<br />
# <math>p_1</math> and <math>p_2</math> are void initially.<br />
<br />
'''Implementation:''' Obvious.<br />
<br />
'''Proof:''' The requirement on the input pointer immediately implies the invariants.<br />
<br />
== Induction Step ==<br />
'''Abstract view:'''<br />
# If the node is not full, the key can be inserted, and we are done.<br />
## If the new key is larger than all keys stored in the node, it can be appended.<br />
## Otherwise, is must override one specific slot. For that, first the contents of this slot and of each slot to its right must be moved one position further right (the corresponding values and successor pointers have to be moved as well). Then the new (key,value)-pair may be safely inserted.<br />
# On the other hand, if the node is indeed full, the key cannot be inserted. In this case:<br />
## The current node <math>N</math> will be split into two nodes, <math>N_1</math> and <math>N_2</math>.<br />
## <math>N_1</math> will contain all keys strictly less than the median of { <math>p</math>.keys<math>[1], ... , p.</math>keys<math>[p.n], K'</math> }<br />
## Analogously, <math>N_2</math> will contain all keys strictly greater than the median of { <math>p</math>.keys<math>[1], ... , p</math>.keys <math>[p.n], K'</math> }.<br />
## Next we try to<br />
## If <math>K'</math> is that median itself, nothing is to be done on the current node.<br />
## Otherwise, the median of <math>\{p</math>.keys<math>[1], \dots , p</math>.keys <math>[p.n], K'\}</math> is in one of the slots of the node. This slot is overridden (by moving the contents of each slot to the right one position further left). The previous contents of this slot is the new <math>K'</math> . If the current node is the root, which we next try to insert in the predecessor of<br />
<br />
'''Implementation:'''<br />
# If <math>p.n = 2M</math><br />
## If <math>p.keys[M] < K' < p.keys[M + 1]</math>, break the iteration and continue the loop.<br />
## Otherwise: <math> x:= M</math> if <math> K' < p.keys[M]</math>, and <math> x:= M+1</math> otherwise.<br />
## Set <math> K'' := p.keys[x]</math>.<br />
## For <math> j \in \{x+1, \dots, p.n \}</math> (in this order), set <math> p.keys [j-1]:= p.keys[j] </math> and <math>p. successor[j-1]:= p.successors[j]</math>.<br />
# If <math> p.keys[p.n] < K'</math>, insert the new (key, value)-pair at position <math>p.keys[p.n+1</math><br />
# Otherwise:<br />
## Let <math>i \in \{ 1, \dots , p.n \} </math> be minimal subject to <math>K' < p.keys[i]</math><br />
## For <math> j \in \{ p.n, \dots , i \} </math> (in this order), set <math> p.keys[j+1]:= p.keys[j]. </math><br />
# If <math> p.n < 2M</math>, set <math> p.n:= p.n+1</math> and terminate the algorithm.<br />
# Otherwise, set <math>K':= K''</math>.<br />
<br />
== Complexity ==<br />
<br />
'''Statement:''' The asymptotic complexity is in <math>\Theta(\log n)</math> in the worst case.<br />
<br />
'''Proof:''' Follows immediately from the fact that the height of B-tree with '''''n''''' nodes is in <math>\Theta(\log n)</math> (cf. the remark clause of the [[B-Trees]] page).</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_insert_and_rearrange&diff=429B-tree: insert and rearrange2014-09-30T17:04:28Z<p>Lkw: /* Induction Step */</p>
<hr />
<div>[[Category:B-Tree]]<br />
[[Category:Algorithm]]<br />
== General Information ==<br />
'''Algorithmic problem:''' [[Text here]]<br />
<br />
'''Type of algorithm:''' Text<br />
<br />
'''Auxiliary data:''' <br />
# Three pointers <math>p, p_1, p_2 </math> or type "pointer to B-tree node".<br />
# A current key <math> K' \in K</math><br />
<br />
== Abstract View ==<br />
'''Invariant:''' Before and after each iteration, <math>p</math> points to a node <math>N</math> such that the following holds: <br />
# In the case <math>p.n < 2M</math>, all implementation invariants of B-trees are maintained if the following <math>K'</math> can be inserted at some position in <math>N</math> such that after insertion.<br />
# In the case <math>p.n = 2M</math>, imagine that we could extend <math>p</math>.keys by one more slot (and, consequently, extend .successors by one more slot). Then <math>K'</math> can be inserted in <math>N</math> at a position such that - except for the statement about the size of <math>N</math> - all implementation invariants of B-trees are again maintained after insertion.<br />
<br />
'''Variant:''' The height level of the node to which <math>p</math> points is decreased by <math>1</math>.<br />
<br />
'''Break condition:''' <math>p.N < 2M</math> or (that is, inclusive-or) <math>p</math> points to the root.<br />
<br />
== Induction Basis ==<br />
'''Abstract view:''' <br />
# <math>p</math> is set to the input pointer.<br />
# <math>p_1</math> and <math>p_2</math> are void initially.<br />
<br />
'''Implementation:''' Obvious.<br />
<br />
'''Proof:''' The requirement on the input pointer immediately implies the invariants.<br />
<br />
== Induction Step ==<br />
'''Abstract view:'''<br />
# If the node is not full, the key can be inserted, and we are done.<br />
## If the new key is larger than all keys stored in the node, it can be appended.<br />
## Otherwise, is must override one specific slot. For that, first the contents of this slot and of each slot to its right must be moved one position further right (the corresponding values and successor pointers have to be moved as well). Then the new (key,value)-pair may be safely inserted.<br />
# On the other hand, if the node is indeed full, the key cannot be inserted. In this case:<br />
## The current node <math>N</math> will be split into two nodes, <math>N_1</math> and <math>N_2</math>.<br />
## <math>N_1</math> will contain all keys strictly less than the median of { <math>p</math>.keys<math>[1], ... , p.</math>keys<math>[p.n], K'</math> }<br />
## Analogously, <math>N_2</math> will contain all keys strictly greater than the median of { <math>p</math>.keys<math>[1], ... , p</math>.keys <math>[p.n], K'</math> }.<br />
## Next we try to<br />
## If <math>K'</math> is that median itself, nothing is to be done on the current node.<br />
## Otherwise, the median of <math>\{p</math>.keys<math>[1], \dots , p</math>.keys <math>[p.n], K'\}</math> is in one of the slots of the node. This slot is overridden (by moving the contents of each slot to the right one position further left). The previous contents of this slot is the new <math>K'</math> . If the current node is the root, which we next try to insert in the predecessor of<br />
<br />
'''Implementation:'''<br />
# If <math>p.n = 2M</math><br />
## If <math>p.keys[M] < K' < p.keys[M + 1]</math>, break the iteration and continue the loop.<br />
## Otherwise: <math> x:= M</math> if <math> K' < p.keys[M]</math>, and <math> x:= M+1</math> otherwise.<br />
## Set <math> K'' := p.keys[x]</math>.<br />
## For <math> j \in \{x+1, \dots, p.n \}</math> (in this order), set <math> p.keys [j-1]:= p.keys[j] </math> and <math>p</math> successor<math>[j-1]:= p.</math>successors<math>[j]</math>.<br />
# If <math> p.keys[p.n] < K'</math>, insert the new (key, value)-pair at position <math>p.keys[p.n+1</math><br />
# Otherwise:<br />
## Let <math>i \in \{ 1, \dots , p.n \} </math> be minimal subject to <math>K' < p.keys[i]</math><br />
## For <math> j \in \{ p.n, \dots , i \} </math> (in this order), set <math> p.keys[j+1]:= p.keys[j]. </math><br />
# If <math> p.n < 2M</math>, set <math> p.n:= p.n+1</math> and terminate the algorithm.<br />
# Otherwise, set <math>K':= K''</math>.<br />
<br />
== Complexity ==<br />
<br />
'''Statement:''' The asymptotic complexity is in <math>\Theta(\log n)</math> in the worst case.<br />
<br />
'''Proof:''' Follows immediately from the fact that the height of B-tree with '''''n''''' nodes is in <math>\Theta(\log n)</math> (cf. the remark clause of the [[B-Trees]] page).</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_insert_and_rearrange&diff=428B-tree: insert and rearrange2014-09-30T17:03:04Z<p>Lkw: /* Induction Step */</p>
<hr />
<div>[[Category:B-Tree]]<br />
[[Category:Algorithm]]<br />
== General Information ==<br />
'''Algorithmic problem:''' [[Text here]]<br />
<br />
'''Type of algorithm:''' Text<br />
<br />
'''Auxiliary data:''' <br />
# Three pointers <math>p, p_1, p_2 </math> or type "pointer to B-tree node".<br />
# A current key <math> K' \in K</math><br />
<br />
== Abstract View ==<br />
'''Invariant:''' Before and after each iteration, <math>p</math> points to a node <math>N</math> such that the following holds: <br />
# In the case <math>p.n < 2M</math>, all implementation invariants of B-trees are maintained if the following <math>K'</math> can be inserted at some position in <math>N</math> such that after insertion.<br />
# In the case <math>p.n = 2M</math>, imagine that we could extend <math>p</math>.keys by one more slot (and, consequently, extend .successors by one more slot). Then <math>K'</math> can be inserted in <math>N</math> at a position such that - except for the statement about the size of <math>N</math> - all implementation invariants of B-trees are again maintained after insertion.<br />
<br />
'''Variant:''' The height level of the node to which <math>p</math> points is decreased by <math>1</math>.<br />
<br />
'''Break condition:''' <math>p.N < 2M</math> or (that is, inclusive-or) <math>p</math> points to the root.<br />
<br />
== Induction Basis ==<br />
'''Abstract view:''' <br />
# <math>p</math> is set to the input pointer.<br />
# <math>p_1</math> and <math>p_2</math> are void initially.<br />
<br />
'''Implementation:''' Obvious.<br />
<br />
'''Proof:''' The requirement on the input pointer immediately implies the invariants.<br />
<br />
== Induction Step ==<br />
'''Abstract view:'''<br />
# If the node is not full, the key can be inserted, and we are done.<br />
## If the new key is larger than all keys stored in the node, it can be appended.<br />
## Otherwise, is must override one specific slot. For that, first the contents of this slot and of each slot to its right must be moved one position further right (the corresponding values and successor pointers have to be moved as well). Then the new (key,value)-pair may be safely inserted.<br />
# On the other hand, if the node is indeed full, the key cannot be inserted. In this case:<br />
## The current node <math>N</math> will be split into two nodes, <math>N_1</math> and <math>N_2</math>.<br />
## <math>N_1</math> will contain all keys strictly less than the median of { <math>p</math>.keys<math>[1], ... , p.</math>keys<math>[p.n], K'</math> }<br />
## Analogously, <math>N_2</math> will contain all keys strictly greater than the median of { <math>p</math>.keys<math>[1], ... , p</math>.keys <math>[p.n], K'</math> }.<br />
## Next we try to<br />
## If <math>K'</math> is that median itself, nothing is to be done on the current node.<br />
## Otherwise, the median of <math>\{p</math>.keys<math>[1], \dots , p</math>.keys <math>[p.n], K'\}</math> is in one of the slots of the node. This slot is overridden (by moving the contents of each slot to the right one position further left). The previous contents of this slot is the new <math>K'</math> . If the current node is the root, which we next try to insert in the predecessor of<br />
<br />
'''Implementation:'''<br />
# If <math>p.n = 2M</math><br />
## If <math>p.keys[M] < K' < p.keys[M + 1]</math>, break the iteration and continue the loop.<br />
## Otherwise: <math> x:= M</math> if <math> K' < p.keys[M]</math>, and <math> x:= M+1</math> otherwise.<br />
## Set <math> K'' := p.keys[x]</math>.<br />
## For <math> j \in \{x+1, \dots, p.n \}</math> (in this order), set <math> p.keys [j-1]:= p.keys[j] </math> and <math>p</math> successor<math>[j-1]:= p.</math>successors<math>[j]</math>.<br />
# If <math> p.keys[p.n] < K'</math>, insert the new (key, value)-pair at position <math>p.keys[p.n+1</math><br />
# Otherwise:<br />
## Let <math>i \in \{ 1, \dots , p.n \} </math> be minimal subject to <math>K' < p.keys[i]</math><br />
## For <math> j \in \{ p.n, \dots , i \} (in this order), set <math> p.keys[j+1]:= p.keys[j]. </math><br />
# If <math> p.n < 2M</math>, set <math> p.n:= p.n+1</math> and terminate the algorithm.<br />
# Otherwise, set <math>K':= K''</math>.<br />
<br />
# If '''''K''''' is one of the values <math>p.keys[1],\dots,p.keys[p.n]</math>, terminate the algorithm and return '''''true'''''.<br />
# If <math>p.children[0] = void</math> (that is, the current node is a leaf), terminate the algorithm and return '''''false'''''.<br />
# If <math>K < p.keys[1]</math> set <math>p := p.children[p.n]</math>.<br />
# Otherwise, if <math>K > p.keys[p.n]</math set <math>p := p.children[p.n]</math>.<br />
# Otherwise, there is exactly one <math>i \in \{1,\dots,p.n-1\}</math> such that <math>p.keys[i] < K < p.keys[i+1]</math>.<br />
# Set <math>p := p.children[i]</math>.<br />
<br />
'''Correctness:''' Obvious.<br />
<br />
== Complexity ==<br />
<br />
'''Statement:''' The asymptotic complexity is in <math>\Theta(\log n)</math> in the worst case.<br />
<br />
'''Proof:''' Follows immediately from the fact that the height of B-tree with '''''n''''' nodes is in <math>\Theta(\log n)</math> (cf. the remark clause of the [[B-Trees]] page).</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_insert_and_rearrange&diff=424B-tree: insert and rearrange2014-09-30T16:31:42Z<p>Lkw: /* Induction Step */</p>
<hr />
<div>[[Category:B-Tree]]<br />
[[Category:Algorithm]]<br />
== General Information ==<br />
'''Algorithmic problem:''' [[Text here]]<br />
<br />
'''Type of algorithm:''' Text<br />
<br />
'''Auxiliary data:''' <br />
# Three pointers <math>p, p_1, p_2 </math> or type "pointer to B-tree node".<br />
# A current key <math> K' \in K</math><br />
<br />
== Abstract View ==<br />
'''Invariant:''' Before and after each iteration, <math>p</math> points to a node <math>N</math> such that the following holds: <br />
# In the case <math>p.n < 2M</math>, all implementation invariants of B-trees are maintained if the following <math>K'</math> can be inserted at some position in <math>N</math> such that after insertion.<br />
# In the case <math>p.n = 2M</math>, imagine that we could extend <math>p</math>.keys by one more slot (and, consequently, extend .successors by one more slot). Then <math>K'</math> can be inserted in <math>N</math> at a position such that - except for the statement about the size of <math>N</math> - all implementation invariants of B-trees are again maintained after insertion.<br />
<br />
'''Variant:''' The height level of the node to which <math>p</math> points is decreased by <math>1</math>.<br />
<br />
'''Break condition:''' <math>p.N < 2M</math> or (that is, inclusive-or) <math>p</math> points to the root.<br />
<br />
== Induction Basis ==<br />
'''Abstract view:''' <br />
# <math>p</math> is set to the input pointer.<br />
# <math>p_1</math> and <math>p_2</math> are void initially.<br />
<br />
'''Implementation:''' Obvious.<br />
<br />
'''Proof:''' The requirement on the input pointer immediately implies the invariants.<br />
<br />
== Induction Step ==<br />
'''Abstract view:'''<br />
# If the node is not full, the key can be inserted, and we are done.<br />
## If the new key is larger than all keys stored in the node, it can be appended.<br />
## Otherwise, is must override one specific slot. For that, first the contents of this slot and of each slot to its right must be moved one position further right (the corresponding values and successor pointers have to be moved as well). Then the new (key,value)-pair may be safely inserted.<br />
# On the other hand, if the node is indeed full, the key cannot be inserted. In this case:<br />
## The current node <math>N</math> will be split into two nodes, <math>N_1</math> and <math>N_2</math>.<br />
## <math>N_1</math> will contain all keys strictly less than the median of <math>{p</math>.keys<math>[1], ... , p.</math>keys<math>[p.n], K'} <br />
<br />
'''Implementation:'''<br />
# If '''''K''''' is one of the values <math>p.keys[1],\dots,p.keys[p.n]</math>, terminate the algorithm and return '''''true'''''.<br />
# If <math>p.children[0] = void</math> (that is, the current node is a leaf), terminate the algorithm and return '''''false'''''.<br />
# If <math>K < p.keys[1]</math> set <math>p := p.children[p.n]</math>.<br />
# Otherwise, if <math>K > p.keys[p.n]</math set <math>p := p.children[p.n]</math>.<br />
# Otherwise, there is exactly one <math>i \in \{1,\dots,p.n-1\}</math> such that <math>p.keys[i] < K < p.keys[i+1]</math>.<br />
# Set <math>p := p.children[i]</math>.<br />
<br />
'''Correctness:''' Obvious.<br />
<br />
== Complexity ==<br />
<br />
'''Statement:''' The asymptotic complexity is in <math>\Theta(\log n)</math> in the worst case.<br />
<br />
'''Proof:''' Follows immediately from the fact that the height of B-tree with '''''n''''' nodes is in <math>\Theta(\log n)</math> (cf. the remark clause of the [[B-Trees]] page).</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_insert_and_rearrange&diff=423B-tree: insert and rearrange2014-09-30T16:25:22Z<p>Lkw: /* Induction Basis */</p>
<hr />
<div>[[Category:B-Tree]]<br />
[[Category:Algorithm]]<br />
== General Information ==<br />
'''Algorithmic problem:''' [[Text here]]<br />
<br />
'''Type of algorithm:''' Text<br />
<br />
'''Auxiliary data:''' <br />
# Three pointers <math>p, p_1, p_2 </math> or type "pointer to B-tree node".<br />
# A current key <math> K' \in K</math><br />
<br />
== Abstract View ==<br />
'''Invariant:''' Before and after each iteration, <math>p</math> points to a node <math>N</math> such that the following holds: <br />
# In the case <math>p.n < 2M</math>, all implementation invariants of B-trees are maintained if the following <math>K'</math> can be inserted at some position in <math>N</math> such that after insertion.<br />
# In the case <math>p.n = 2M</math>, imagine that we could extend <math>p</math>.keys by one more slot (and, consequently, extend .successors by one more slot). Then <math>K'</math> can be inserted in <math>N</math> at a position such that - except for the statement about the size of <math>N</math> - all implementation invariants of B-trees are again maintained after insertion.<br />
<br />
'''Variant:''' The height level of the node to which <math>p</math> points is decreased by <math>1</math>.<br />
<br />
'''Break condition:''' <math>p.N < 2M</math> or (that is, inclusive-or) <math>p</math> points to the root.<br />
<br />
== Induction Basis ==<br />
'''Abstract view:''' <br />
# <math>p</math> is set to the input pointer.<br />
# <math>p_1</math> and <math>p_2</math> are void initially.<br />
<br />
'''Implementation:''' Obvious.<br />
<br />
'''Proof:''' The requirement on the input pointer immediately implies the invariants.<br />
<br />
== Induction Step ==<br />
'''Abstract view:'''<br />
# Let '''''N''''' denote the node to which '''''p''''' currently points.<br />
# If the searched key is in '''''N''''', terminate the algorithm and return '''''true'''''.<br />
# Otherwise, if '''''N''''' is a leaf, terminate the algorithm and return '''''false'''''.<br />
# Otherwise, let '''''p''''' point the child of '''''N''''' such that the searched key is in the [[Directed Tree#Ranges of Search Tree Nodes|range]] of that child<br />
<br />
'''Implementation:'''<br />
# If '''''K''''' is one of the values <math>p.keys[1],\dots,p.keys[p.n]</math>, terminate the algorithm and return '''''true'''''.<br />
# If <math>p.children[0] = void</math> (that is, the current node is a leaf), terminate the algorithm and return '''''false'''''.<br />
# If <math>K < p.keys[1]</math> set <math>p := p.children[p.n]</math>.<br />
# Otherwise, if <math>K > p.keys[p.n]</math set <math>p := p.children[p.n]</math>.<br />
# Otherwise, there is exactly one <math>i \in \{1,\dots,p.n-1\}</math> such that <math>p.keys[i] < K < p.keys[i+1]</math>.<br />
# Set <math>p := p.children[i]</math>.<br />
<br />
'''Correctness:''' Obvious.<br />
<br />
== Complexity ==<br />
<br />
'''Statement:''' The asymptotic complexity is in <math>\Theta(\log n)</math> in the worst case.<br />
<br />
'''Proof:''' Follows immediately from the fact that the height of B-tree with '''''n''''' nodes is in <math>\Theta(\log n)</math> (cf. the remark clause of the [[B-Trees]] page).</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_insert_and_rearrange&diff=422B-tree: insert and rearrange2014-09-30T16:23:27Z<p>Lkw: </p>
<hr />
<div>[[Category:B-Tree]]<br />
[[Category:Algorithm]]<br />
== General Information ==<br />
'''Algorithmic problem:''' [[Text here]]<br />
<br />
'''Type of algorithm:''' Text<br />
<br />
'''Auxiliary data:''' <br />
# Three pointers <math>p, p_1, p_2 </math> or type "pointer to B-tree node".<br />
# A current key <math> K' \in K</math><br />
<br />
== Abstract View ==<br />
'''Invariant:''' Before and after each iteration, <math>p</math> points to a node <math>N</math> such that the following holds: <br />
# In the case <math>p.n < 2M</math>, all implementation invariants of B-trees are maintained if the following <math>K'</math> can be inserted at some position in <math>N</math> such that after insertion.<br />
# In the case <math>p.n = 2M</math>, imagine that we could extend <math>p</math>.keys by one more slot (and, consequently, extend .successors by one more slot). Then <math>K'</math> can be inserted in <math>N</math> at a position such that - except for the statement about the size of <math>N</math> - all implementation invariants of B-trees are again maintained after insertion.<br />
<br />
'''Variant:''' The height level of the node to which <math>p</math> points is decreased by <math>1</math>.<br />
<br />
'''Break condition:''' <math>p.N < 2M</math> or (that is, inclusive-or) <math>p</math> points to the root.<br />
<br />
== Induction Basis ==<br />
'''Abstract view:''' '''''p''''' is initialized so as to point to the root of the B-tree.<br />
<br />
'''Implementation:''' Obvious.<br />
<br />
'''Proof:''' Obvious.<br />
<br />
== Induction Step ==<br />
'''Abstract view:'''<br />
# Let '''''N''''' denote the node to which '''''p''''' currently points.<br />
# If the searched key is in '''''N''''', terminate the algorithm and return '''''true'''''.<br />
# Otherwise, if '''''N''''' is a leaf, terminate the algorithm and return '''''false'''''.<br />
# Otherwise, let '''''p''''' point the child of '''''N''''' such that the searched key is in the [[Directed Tree#Ranges of Search Tree Nodes|range]] of that child<br />
<br />
'''Implementation:'''<br />
# If '''''K''''' is one of the values <math>p.keys[1],\dots,p.keys[p.n]</math>, terminate the algorithm and return '''''true'''''.<br />
# If <math>p.children[0] = void</math> (that is, the current node is a leaf), terminate the algorithm and return '''''false'''''.<br />
# If <math>K < p.keys[1]</math> set <math>p := p.children[p.n]</math>.<br />
# Otherwise, if <math>K > p.keys[p.n]</math set <math>p := p.children[p.n]</math>.<br />
# Otherwise, there is exactly one <math>i \in \{1,\dots,p.n-1\}</math> such that <math>p.keys[i] < K < p.keys[i+1]</math>.<br />
# Set <math>p := p.children[i]</math>.<br />
<br />
'''Correctness:''' Obvious.<br />
<br />
== Complexity ==<br />
<br />
'''Statement:''' The asymptotic complexity is in <math>\Theta(\log n)</math> in the worst case.<br />
<br />
'''Proof:''' Follows immediately from the fact that the height of B-tree with '''''n''''' nodes is in <math>\Theta(\log n)</math> (cf. the remark clause of the [[B-Trees]] page).</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_insert_and_rearrange&diff=421B-tree: insert and rearrange2014-09-30T16:19:17Z<p>Lkw: </p>
<hr />
<div>[[Category:B-Tree]]<br />
[[Category:Algorithm]]<br />
== General Information ==<br />
'''Algorithmic problem:''' [[Text here]]<br />
<br />
'''Type of algorithm:''' Text<br />
<br />
'''Auxiliary data:''' <br />
# Three pointers <math>p, p_1, p_2 </math> or type "pointer to B-tree node".<br />
# A current key <math> K' \in K</math><br />
<br />
== Abstract View ==<br />
'''Invariant:''' Before and after each iteration, <math>p</math> points to a node <math>N</math> such that the following holds: <br />
# In the case <math>p.n < 2M</math>, all implementation invariants of B-trees are maintained if the following <math>K'</math> can be inserted at some position in <math>N</math> such that after insertion.<br />
# the searched key is in the [[Directed Tree#Ranges of Search Tree Nodes|range]] of '''''N'''''.<br />
<br />
'''Variant:''' '''''p''''' is redirected from the current node '''''N''''' to some child of the current node.<br />
<br />
'''Break condition:'''<br />
# '''''p''''' points to a leaf of the B-tree or (that is, inclusive-or)<br />
# the searched key is in the node to which '''''p''''' points.<br />
<br />
== Induction Basis ==<br />
'''Abstract view:''' '''''p''''' is initialized so as to point to the root of the B-tree.<br />
<br />
'''Implementation:''' Obvious.<br />
<br />
'''Proof:''' Obvious.<br />
<br />
== Induction Step ==<br />
'''Abstract view:'''<br />
# Let '''''N''''' denote the node to which '''''p''''' currently points.<br />
# If the searched key is in '''''N''''', terminate the algorithm and return '''''true'''''.<br />
# Otherwise, if '''''N''''' is a leaf, terminate the algorithm and return '''''false'''''.<br />
# Otherwise, let '''''p''''' point the child of '''''N''''' such that the searched key is in the [[Directed Tree#Ranges of Search Tree Nodes|range]] of that child<br />
<br />
'''Implementation:'''<br />
# If '''''K''''' is one of the values <math>p.keys[1],\dots,p.keys[p.n]</math>, terminate the algorithm and return '''''true'''''.<br />
# If <math>p.children[0] = void</math> (that is, the current node is a leaf), terminate the algorithm and return '''''false'''''.<br />
# If <math>K < p.keys[1]</math> set <math>p := p.children[p.n]</math>.<br />
# Otherwise, if <math>K > p.keys[p.n]</math set <math>p := p.children[p.n]</math>.<br />
# Otherwise, there is exactly one <math>i \in \{1,\dots,p.n-1\}</math> such that <math>p.keys[i] < K < p.keys[i+1]</math>.<br />
# Set <math>p := p.children[i]</math>.<br />
<br />
'''Correctness:''' Obvious.<br />
<br />
== Complexity ==<br />
<br />
'''Statement:''' The asymptotic complexity is in <math>\Theta(\log n)</math> in the worst case.<br />
<br />
'''Proof:''' Follows immediately from the fact that the height of B-tree with '''''n''''' nodes is in <math>\Theta(\log n)</math> (cf. the remark clause of the [[B-Trees]] page).</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_insert_and_rearrange&diff=418B-tree: insert and rearrange2014-09-30T16:08:08Z<p>Lkw: Created page with "Category:B-Tree Category:Algorithm == General Information == '''Algorithmic problem:''' Text here '''Type of algorithm:''' Text '''Auxiliary data:''' # Three po..."</p>
<hr />
<div>[[Category:B-Tree]]<br />
[[Category:Algorithm]]<br />
== General Information ==<br />
'''Algorithmic problem:''' [[Text here]]<br />
<br />
'''Type of algorithm:''' Text<br />
<br />
'''Auxiliary data:''' <br />
# Three pointers ''p'', ''p''<sub>1</sub>, ''p''<sub>2</sub> or type "pointer to B-tree node".<br />
# A current key <math> K' \in K</math><br />
<br />
== Abstract View ==<br />
'''Invariant:''' Before and after each iteration:<br />
# '''''p''''' points to some node '''''N''''' of the B-tree and<br />
# the searched key is in the [[Directed Tree#Ranges of Search Tree Nodes|range]] of '''''N'''''.<br />
<br />
'''Variant:''' '''''p''''' is redirected from the current node '''''N''''' to some child of the current node.<br />
<br />
'''Break condition:'''<br />
# '''''p''''' points to a leaf of the B-tree or (that is, inclusive-or)<br />
# the searched key is in the node to which '''''p''''' points.<br />
<br />
== Induction Basis ==<br />
'''Abstract view:''' '''''p''''' is initialized so as to point to the root of the B-tree.<br />
<br />
'''Implementation:''' Obvious.<br />
<br />
'''Proof:''' Obvious.<br />
<br />
== Induction Step ==<br />
'''Abstract view:'''<br />
# Let '''''N''''' denote the node to which '''''p''''' currently points.<br />
# If the searched key is in '''''N''''', terminate the algorithm and return '''''true'''''.<br />
# Otherwise, if '''''N''''' is a leaf, terminate the algorithm and return '''''false'''''.<br />
# Otherwise, let '''''p''''' point the child of '''''N''''' such that the searched key is in the [[Directed Tree#Ranges of Search Tree Nodes|range]] of that child<br />
<br />
'''Implementation:'''<br />
# If '''''K''''' is one of the values <math>p.keys[1],\dots,p.keys[p.n]</math>, terminate the algorithm and return '''''true'''''.<br />
# If <math>p.children[0] = void</math> (that is, the current node is a leaf), terminate the algorithm and return '''''false'''''.<br />
# If <math>K < p.keys[1]</math> set <math>p := p.children[p.n]</math>.<br />
# Otherwise, if <math>K > p.keys[p.n]</math set <math>p := p.children[p.n]</math>.<br />
# Otherwise, there is exactly one <math>i \in \{1,\dots,p.n-1\}</math> such that <math>p.keys[i] < K < p.keys[i+1]</math>.<br />
# Set <math>p := p.children[i]</math>.<br />
<br />
'''Correctness:''' Obvious.<br />
<br />
== Complexity ==<br />
<br />
'''Statement:''' The asymptotic complexity is in <math>\Theta(\log n)</math> in the worst case.<br />
<br />
'''Proof:''' Follows immediately from the fact that the height of B-tree with '''''n''''' nodes is in <math>\Theta(\log n)</math> (cf. the remark clause of the [[B-Trees]] page).</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_split&diff=304B-tree: split2014-09-25T20:25:15Z<p>Lkw: /* Pseudocode */</p>
<hr />
<div>== Pseudocode == <br />
<br />
<code><br />
B-TREE-SPLIT-CHILD(''x'', ''i'')<br />
1 ''z'' = ALLOCATE-NODE()<br />
2 ''y'' = ''x''.''c''<sub>i</sub><br />
3 ''z''.''leaf'' = ''y.leaf''<br />
4 ''z.n'' = ''t'' - 1<br />
5 '''for''' ''j'' = 1 '''to''' ''t'' - 1<br />
6 ''z.key''<sub>j</sub> = ''y.key''<sub>j + t</sub><br />
7 '''if''' not ''y.leaf''<br />
8 '''for''' ''j'' = 1 to t<br />
9 ''z.c''<sub>j</sub> = ''y.c''<sub>j + t</sub><br />
10 ''y.n'' = ''t'' - 1 <br />
11 '''for''' ''j'' = ''x.n'' + 1 '''downto''' ''i'' + 1<br />
12 ''x.c''<sub>j + 1</sub> = ''x.c''<sub>j</sub><br />
13 ''x.c''<sub>i + 1</sub> = ''z''<br />
14 '''for''' ''j'' = ''x.n'' '''downto''' ''i''<br />
15 ''x.key''<sub>i</sub> = ''y.key''<sub>j</sub><br />
16 ''x.key''<sub>i</sub> = ''y.key''<sub>t</sub><br />
17 ''x.n'' = ''x.n'' + 1<br />
18 DISK-WRITE(''y'')<br />
19 DISK-WRITE(''z'')<br />
20 DISK-WRITE(''x'')<br />
</code></div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_insert&diff=303B-tree: insert2014-09-25T20:23:17Z<p>Lkw: /* B-TREE-INSERT-NONFULL(x,k) */</p>
<hr />
<div>= Pseudocode = <br />
<br />
=== B-TREE-INSERT(''T'',''k'') ===<br />
<br />
<code><br />
B-TREE-INSERT(''T'',''k'')<br />
1 ''r'' = ''T.root''<br />
2 '''if''' ''r.n'' == 2''t'' - 1<br />
3 ''s'' = ALLOCATE-NODE()<br />
4 ''T.root'' = ''s''<br />
5 ''s.leaf'' = FALSE<br />
6 ''s.n'' = 0<br />
7 ''s.c<sub>1</sub>'' = ''r''<br />
8 B-TREE-SPLIT-CHILD(''s'', 1)<br />
9 B-TREE-INSERT-NONFULL(''s, k'')<br />
10 '''else''' B-TREE-INSERT-NONFULL(''r, k'') <br />
</code><br />
<br />
=== B-TREE-INSERT-NONFULL(''x'',''k'') ===<br />
<br />
<code><br />
B-TREE-INSERT-NONFULL(''x'',''k'')<br />
1 ''i'' = ''x.n''<br />
2 '''if''' ''x.leaf''<br />
3 '''while''' ''i &ge; 1 and ''k'' < ''x.key''<sub>i</sub><br />
4 ''x.key''<sub>i+1</sub>= ''x.key''<sub>i</sub><br />
5 ''i'' = ''i'' - 1<br />
6 ''x.key''<sub>i</sub>+111 = ''k''<br />
7 ''x.n'' = ''x.n'' + 1<br />
8 DISK-WRITE(''x)<br />
9 '''else while''' ''i'' &ge; 1 and ''k'' < ''x.key''<sub>i</sub><br />
10 ''i'' = ''i'' - 1<br />
11 ''i'' = ''i'' + 1<br />
12 DISK-READ(''x.c''<sub>i</sub>)<br />
13 '''if''' ''x.c<sub>i</sub>.n'' == 2''t'' - 1<br />
14 B-TREE-SPLIT-CHILD(''x, i'')<br />
15 '''if''' ''k'' > ''x.key''<sub>i</sub><br />
16 ''i'' = ''i'' + 1<br />
17 B-TREE-INSERT-NONFULL(''x.c<sub>i</sub>, k) <br />
</code></div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_insert&diff=302B-tree: insert2014-09-25T20:21:56Z<p>Lkw: /* B-TREE-INSERT(T,k) */</p>
<hr />
<div>= Pseudocode = <br />
<br />
=== B-TREE-INSERT(''T'',''k'') ===<br />
<br />
<code><br />
B-TREE-INSERT(''T'',''k'')<br />
1 ''r'' = ''T.root''<br />
2 '''if''' ''r.n'' == 2''t'' - 1<br />
3 ''s'' = ALLOCATE-NODE()<br />
4 ''T.root'' = ''s''<br />
5 ''s.leaf'' = FALSE<br />
6 ''s.n'' = 0<br />
7 ''s.c<sub>1</sub>'' = ''r''<br />
8 B-TREE-SPLIT-CHILD(''s'', 1)<br />
9 B-TREE-INSERT-NONFULL(''s, k'')<br />
10 '''else''' B-TREE-INSERT-NONFULL(''r, k'') <br />
</code><br />
<br />
=== B-TREE-INSERT-NONFULL(''x'',''k'') ===<br />
<br />
<code><br />
B-TREE-INSERT-NONFULL(''x'',''k'')<br />
1 ''i'' = ''x.n''<br />
2 '''if''' ''x.leaf''<br />
3 '''while''' ''i &ge; 1 and ''k'' < ''x.key''iiiii<br />
4 ''x.key''iii+111 = ''x.key''iiiii<br />
5 ''i'' = ''i'' - 1<br />
6 ''x.key''iii+111 = ''k''<br />
7 ''x.n'' = ''x.n'' + 1<br />
8 DISK-WRITE(''x)<br />
9 '''else while''' ''i'' &ge; 1 and ''k'' < ''x.key''iiiii<br />
10 ''i'' = ''i'' - 1<br />
11 ''i'' = ''i'' + 1<br />
12 DISK-READ(''x.c''iiii)<br />
13 '''if''' ''x.ciiii.n'' == 2''t'' - 1<br />
14 B-TREE-SPLIT-CHILD(''x, i'')<br />
15 '''if''' ''k'' > ''x.key''iiii<br />
16 ''i'' = ''i'' + 1<br />
17 B-TREE-INSERT-NONFULL(''x.ciii, k) <br />
</code></div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Master_theorem&diff=301Master theorem2014-09-25T20:21:10Z<p>Lkw: /* MASTER THEOREM */</p>
<hr />
<div>== MASTER THEOREM ==<br />
Let a &ge; 1 and b > 1 be constants, let ''f''(''n'') be a function, and let ''T''(''n'') be defined on the nonnegative integers by the recurrence<br />
<br />
''T''(''n'') = ''aT''(''n''/''b'') + ''f'' (''n''),<br />
<br />
where we interpret ''n''/''b'' to mean either &lfloor;''n''/''b''&rfloor; or &lceil;''n''/''b''&rceil;. Then ''T''(''n'') can be bounded asymptotically as follows.<br />
<br />
1. If ''f'' (''n'') = ''O''(''n<sup>log<sub>b</sub> a - &epsilon;</sup>) for some constant &epsilon; > 0, then ''T''(''n'') = &Theta;(n<sup>log<sub>b</sub> a</sup>). <br><br />
2. If ''f'' (''n'') = &Theta;(''n''<sup>log <sub>b</sub> a</sup>), then ''T''(''n'') = &Theta;(n<sup>log<sub>b</sub> a</sup> lg n). <br><br />
3. If ''f'' (''n'') = &Omega;(n<sup>log<sub>b</sub> a + &epsilon;</sup>) for some constant &epsilon; > 0, and if ''af''(''n/b'') &le; ''cf''(''n'') for some constant ''c'' < 1 and all sufficiently large ''n'', then ''T''(''n'') = &Omega;(''f'' (''n'')).</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Master_theorem&diff=300Master theorem2014-09-25T20:20:40Z<p>Lkw: /* MASTER THEOREM */</p>
<hr />
<div>== MASTER THEOREM ==<br />
Let a &ge; 1 and b > 1 be constants, let ''f''(''n'') be a function, and let ''T''(''n'') be defined on the nonnegative integers by the recurrence<br />
<br />
''T''(''n'') = ''aT''(''n''/''b'') + ''f'' (''n''),<br />
<br />
where we interpret ''n''/''b'' to mean either &lfloor;''n''/''b''&rfloor; or &lceil;''n''/''b''&rceil;. Then ''T''(''n'') can be bounded asymptotically as follows.<br />
<br />
1. If ''f'' (''n'') = ''O''(''n<sup>log<sub>b</sub> a - &epsilon;</sup>) for some constant &epsilon; > 0, then ''T''(''n'') = &Theta;(n^<sup>log<sub>b</sub> a</sup>). <br><br />
2. If ''f'' (''n'') = &Theta;(''n''<sup>log <sub>b</sub> a</sup>), then ''T''(''n'') = &Theta;(n<sup>log<sub>b</sub> a</sup> lg n). <br><br />
3. If ''f'' (''n'') = &Omega;(n<sup>log<sub>b</sub> a + &epsilon;</sup>) for some constant &epsilon; > 0, and if ''af''(''n/b'') &le; ''cf''(''n'') for some constant ''c'' < 1 and all sufficiently large ''n'', then ''T''(''n'') = &Omega;(''f'' (''n'')).</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Master_theorem&diff=299Master theorem2014-09-25T20:18:04Z<p>Lkw: /* MASTER THEOREM */</p>
<hr />
<div>== MASTER THEOREM ==<br />
Let a &ge; 1 and b > 1 be constants, let ''f''(''n'') be a function, and let ''T''(''n'') be defined on the nonnegative integers by the recurrence<br />
<br />
''T''(''n'') = ''aT''(''n''/''b'') + ''f'' (''n''),<br />
<br />
where we interpret ''n''/''b'' to mean either &lfloor;''n''/''b''&rfloor; or &lceil;''n''/''b''&rceil;. Then ''T''(''n'') can be bounded asymptotically as follows.<br />
<br />
1. If ''f'' (''n'') = ''O''(''n<sup>logba - &epsilon;</sup>) for some constant &epsilon; > 0, then ''T''(''n'') = &Theta;(n^<sup>log</sup>). <br><br />
2. If ''f'' (''n'') = &Theta;(''n''<sup>log b a</sup>), then ''T''(''n'') = &Theta;(n<sup>log b a</sup> lg n). <br><br />
3. If ''f'' (''n'') = &Omega;(n<sup>log b a + &epsilon;</sup>) for some constant &epsilon; > 0, and if ''af''(''n/b'') &le; ''cf''(''n'') for some constant ''c'' < 1 and all sufficiently large ''n'', then ''T''(''n'') = &Omega;(''f''(''n'')).</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Master_theorem&diff=298Master theorem2014-09-25T20:17:25Z<p>Lkw: /* MASTER THEOREM */</p>
<hr />
<div>== MASTER THEOREM ==<br />
Let a &ge; 1 and b > 1 be constants, let ''f''(''n'') be a function, and let ''T''(''n'') be defined on the nonnegative integers by the recurrence<br />
<br />
''T''(''n'') = ''aT''(''n''/''b'') + ''f''(''n''),<br />
<br />
where we interpret ''n''/''b'' to mean either &lfloor;''n''/''b''&rfloor; or &lceil;''n''/''b''&rceil;. Then ''T''(''n'') can be bounded asymptotically as follows.<br />
<br />
1. If ''f''(''n'') = ''O''(''n<sup>logba - &epsilon;</sup>) for some constant &epsilon; > 0, then ''T''(''n'') = &Theta;(n^<sup>log</sup>). <br><br />
2. If ''f''(''n'') = &Theta;(''n''<sup>log b a</sup>), then ''T''(''n'') = &Theta;(n<sup>log b a</sup> lg n). <br><br />
3. If ''f''(''n'') = &Omega;(n<sup>log b a + &epsilon;</sup>) for some constant &epsilon; > 0, and if ''af''(''n/b'') &le; ''cf''(''n'') for some constant ''c'' < 1 and all sufficiently large ''n'', then ''T''(''n'') = &Omega;(''f''(''n'')).</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Master_theorem&diff=297Master theorem2014-09-25T20:16:11Z<p>Lkw: /* MASTER THEOREM */</p>
<hr />
<div>== MASTER THEOREM ==<br />
Let a &ge; 1 and b > 1 be constants, let ''f''(''n'') be a function, and let ''T''(''n'') be defined on the nonnegative integers by the recurrence<br />
<br />
''T''(''n'') = ''aT''(''n''/''b'') + ''f''(''n''),<br />
<br />
where we interpret ''n''/''b'' to mean either &lfloor;''n''/''b''&rfloor; or &lceil;''n''/''b''&rceil;. Then ''T''(''n'') can be bounded asymptotically as follows.<br />
<br />
1. If ''f''(''n'') = ''O''(''n<sup>logba - &epsilon;</sup>) for some constant &epsilon; > 0, then ''T''(''n'') = &Theta;(n^<sup>log</sup>). <p><br />
2. If ''f''(''n'') = &Theta;(''n''<sup>log b a</sup>), then ''T''(''n'') = &Theta;(n<sup>log b a</sup> lg n). <p><br />
3. If ''f''(''n'') = &Omega;(n<sup>log b a + &epsilon;</sup>) for some constant &epsilon; > 0, and if ''af''(''n/b'') &le; ''cf''(''n'') for some constant ''c'' < 1 and all sufficiently large ''n'', then ''T''(''n'') = &Omega;(''f''(''n'')).</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Master_theorem&diff=296Master theorem2014-09-25T20:14:25Z<p>Lkw: /* MASTER THEOREM */</p>
<hr />
<div>== MASTER THEOREM ==<br />
Let a &ge; 1 and b > 1 be constants, let ''f''(''n'') be a function, and let ''T''(''n'') be defined on the nonnegative integers by the recurrence<br />
<br />
''T''(''n'') = ''aT''(''n''/''b'') + ''f''(''n''),<br />
<br />
where we interpret ''n''/''b'' to mean either &lfloor;''n''/''b''&rfloor; or &lceil;''n''/''b''&rceil;. Then ''T''(''n'') can be bounded asymptotically as follows.<br />
<br />
1. If ''f''(''n'') = ''O''(''n<sup>logba - &epsilon;</sup>) for some constant &epsilon; > 0, then ''T''(''n'') = &Theta;(n^<sup>log</sup>).<br />
2. If ''f''(''n'') = &Theta;(''n''<sup>log b a</sup>), then ''T''(''n'') = &Theta;(n<sup>log b a</sup> lg n).<br />
3. If ''f''(''n'') = &Omega;(n<sup>log b a + &epsilon;</sup>) for some constant &epsilon; > 0, and if ''af''(''n/b'') &le; ''cf''(''n'') for some constant ''c'' < 1 and all sufficiently large ''n'', then ''T''(''n'') = &Omega;(''f''(''n'')).</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Master_theorem&diff=294Master theorem2014-09-25T20:08:21Z<p>Lkw: /* MASTER THEOREM */</p>
<hr />
<div>== MASTER THEOREM ==<br />
Let a &ge; 1 and b > 1 be constants, let ''f''(''n'') be a function, and let ''T''(''n'') be defined on the nonnegative integers by the recurrence<br />
<br />
''T''(''n'') = ''aT''(''n''/''b'') + ''f''(''n''),<br />
<br />
where we interpret ''n''/''b'' to mean either &lfloor;''n''/''b''&rfloor; or &lceil;''n''/''b''&rceil;. Then ''T''(''n'') can be bounded asymptotically as follows.<br />
<br />
1. If ''f''(''n'') = ''O''(''n<sup>logba - &epsilon;</sup>) for some constant &epsilon; > 0, then ''T''(''n'') = &Theta;(n^<sup>log</sup>)</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Master_theorem&diff=293Master theorem2014-09-25T20:07:13Z<p>Lkw: /* MASTER THEOREM */</p>
<hr />
<div>== MASTER THEOREM ==<br />
Let a &ge; 1 and b > 1 be constants, let ''f''(''n'') be a function, and let ''T''(''n'') be defined on the nonnegative integers by the recurrence<br />
<br />
''T''(''n'') = ''aT''(''n''/''b'') + ''f''(''n''),<br />
<br />
where we interpret ''n''/''b'' to mean either &lfloor;''n''/''b''&rfloor; or &lceil;''n''/''b''&rceil;. Then ''T''(''n'') can be bounded asymptotically as follows.<br />
<br />
1. If ''f''(''n'') = ''O''(''n^(logba - &epsilon;)) for some constant &epsilon; > 0, then ''T''(''n'') = &Theta;(n^log)</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Master_theorem&diff=274Master theorem2014-09-25T18:51:40Z<p>Lkw: Created page with "== MASTER THEOREM == Let a &ge; 1 and b > 1 be constants, let ''f''(''n'') be a function, and let ''T''(''n'') be defined on the nonnegative integers by the recurrence ''T''(..."</p>
<hr />
<div>== MASTER THEOREM ==<br />
Let a &ge; 1 and b > 1 be constants, let ''f''(''n'') be a function, and let ''T''(''n'') be defined on the nonnegative integers by the recurrence<br />
<br />
''T''(''n'') = ''aT''(''n''/''b'') + ''f''(''n''),<br />
<br />
where we interpret ''n''/''b'' to mean either &lfloor;''n''/''b''&rfloor; or &lceil;''n''/''b''&rceil;. Then ''T''(''n'') can be bounded asymptotically as follows.</div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Prim&diff=270Prim2014-09-25T18:34:21Z<p>Lkw: /* MST-PRIM(G,w,r) */</p>
<hr />
<div>== Pseudocode == <br />
<br />
=== MST-PRIM(''G,w,r'') ===<br />
<br />
<code><br />
MST-PRIM(''G,w,r'')<br />
1 '''for''' each vertex ''u'' &isin; ''V''[''G''] <br />
2 '''do''' ''key''[''u''] = &infin;<br />
3 &pi;[''u''] = NIL<br />
4 ''key''[''r''] = 0<br />
5 ''Q'' = ''V''[''G'']<br />
6 '''while''' ''Q'' &ne; &Oslash;<br />
7 '''do''' ''u'' = EXTRACT-MIN(''Q'')<br />
8 '''for''' each v &isin; ''Adj[u]''<br />
9 '''do if''' v &isin; ''Q'' and ''w(u,v)'' < ''key''[''v'']<br />
10 '''then''' &pi;[''v''] = ''u''<br />
11 ''key''[''v''] = ''w(u,v)''<br />
</code></div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Prim&diff=269Prim2014-09-25T18:33:07Z<p>Lkw: Created page with "== Pseudocode == === MST-PRIM(''G,w,r'') === <code> MST-PRIM(''G,w,r'') 1 '''for''' each vertex ''u'' &isin; V[''G''] 2 '''do''' ''key[''u''] = &infin; 3..."</p>
<hr />
<div>== Pseudocode == <br />
<br />
=== MST-PRIM(''G,w,r'') ===<br />
<br />
<code><br />
MST-PRIM(''G,w,r'')<br />
1 '''for''' each vertex ''u'' &isin; V[''G''] <br />
2 '''do''' ''key[''u''] = &infin;<br />
3 &pi;[''u''] = NIL<br />
4 ''key[r] = 0<br />
5 ''Q'' = ''V[G]''<br />
6 '''while''' ''Q'' &ne; &Oslash;<br />
7 '''do''' ''u'' = EXTRACT-MIN(''Q'')<br />
8 '''for''' each v &isin; ''Adj[u]''<br />
9 '''do if''' v &isin; ''Q'' and ''w(u,v)'' < ''key[v]<br />
10 '''then''' &pi;[''v''] = ''u''<br />
11 ''key[v] = ''w(u,v)''<br />
</code></div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_insert&diff=266B-tree: insert2014-09-25T17:48:25Z<p>Lkw: </p>
<hr />
<div>= Pseudocode = <br />
<br />
=== B-TREE-INSERT(''T'',''k'') ===<br />
<br />
<code><br />
B-TREE-INSERT(''T'',''k'')<br />
1 ''r'' = ''T.root''<br />
2 '''if''' ''r.n'' == 2''t'' - 1<br />
3 ''s'' = ALLOCATE-NODE()<br />
4 ''T.root'' = ''s''<br />
5 ''s.leaf'' = FALSE<br />
6 ''s.n'' = 0<br />
7 ''s.c1111'' = ''r''<br />
8 B-TREE-SPLIT-CHILD(''s'', 1)<br />
9 B-TREE-INSERT-NONFULL(''s, k'')<br />
10 '''else''' B-TREE-INSERT-NONFULL(''r, k'') <br />
</code><br />
<br />
=== B-TREE-INSERT-NONFULL(''x'',''k'') ===<br />
<br />
<code><br />
B-TREE-INSERT-NONFULL(''x'',''k'')<br />
1 ''i'' = ''x.n''<br />
2 '''if''' ''x.leaf''<br />
3 '''while''' ''i &ge; 1 and ''k'' < ''x.key''iiiii<br />
4 ''x.key''iii+111 = ''x.key''iiiii<br />
5 ''i'' = ''i'' - 1<br />
6 ''x.key''iii+111 = ''k''<br />
7 ''x.n'' = ''x.n'' + 1<br />
8 DISK-WRITE(''x)<br />
9 '''else while''' ''i'' &ge; 1 and ''k'' < ''x.key''iiiii<br />
10 ''i'' = ''i'' - 1<br />
11 ''i'' = ''i'' + 1<br />
12 DISK-READ(''x.c''iiii)<br />
13 '''if''' ''x.ciiii.n'' == 2''t'' - 1<br />
14 B-TREE-SPLIT-CHILD(''x, i'')<br />
15 '''if''' ''k'' > ''x.key''iiii<br />
16 ''i'' = ''i'' + 1<br />
17 B-TREE-INSERT-NONFULL(''x.ciii, k) <br />
</code></div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_insert&diff=265B-tree: insert2014-09-25T17:44:56Z<p>Lkw: /* Pseudocode */</p>
<hr />
<div>== Pseudocode == <br />
<br />
= B-TREE-INSERT(''T'',''k'') =<br />
<code><br />
B-TREE-INSERT(''T'',''k'')<br />
1 ''r'' = ''T.root''<br />
2 '''if''' ''r.n'' == 2''t'' - 1<br />
3 ''s'' = ALLOCATE-NODE()<br />
4 ''T.root'' = ''s''<br />
5 ''s.leaf'' = FALSE<br />
6 ''s.n'' = 0<br />
7 ''s.c1111'' = ''r''<br />
8 B-TREE-SPLIT-CHILD(''s'', 1)<br />
9 B-TREE-INSERT-NONFULL(''s, k'')<br />
10 '''else''' B-TREE-INSERT-NONFULL(''r, k'') <br />
</code><br />
<br />
= B-TREE-INSERT-NONFULL(''x'',''k'') =<br />
<code><br />
B-TREE-INSERT-NONFULL(''x'',''k'')<br />
1 ''i'' = ''x.n''<br />
2 '''if''' ''x.leaf''<br />
3 '''while''' ''i &ge; 1 and ''k'' < ''x.key''iiiii<br />
4 ''x.key''iii+111 = ''x.key''iiiii<br />
5 ''i'' = ''i'' - 1<br />
6 ''x.key''iii+111 = ''k''<br />
7 ''x.n'' = ''x.n'' + 1<br />
8 DISK-WRITE(''x)<br />
9 '''else while''' ''i'' &ge; 1 and ''k'' < ''x.key''iiiii<br />
10 ''i'' = ''i'' - 1<br />
11 ''i'' = ''i'' + 1<br />
12 DISK-READ(''x.c''iiii)<br />
13 '''if''' ''x.ciiii.n'' == 2''t'' - 1<br />
14 B-TREE-SPLIT-CHILD(''x, i'')<br />
15 '''if''' ''k'' > ''x.key''iiii<br />
16 ''i'' = ''i'' + 1<br />
17 B-TREE-INSERT-NONFULL(''x.ciii, k) <br />
</code></div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Breadth-first_search&diff=260Breadth-first search2014-09-25T16:40:35Z<p>Lkw: /* Pseudocode */</p>
<hr />
<div>== Pseudocode == <br />
<br />
<code><br />
BFS(''G,s'')<br />
1 '''for''' each vertex ''u'' &isin; ''G.V'' - {''s''}<br />
2 ''u.color'' = WHITE<br />
3 ''u.d'' = &infin;<br />
4 ''u.''&pi; = NIL<br />
5 ''s.color'' = GRAY<br />
6 ''s.d'' = 0<br />
7 ''s.&pi;'' = NIL<br />
8 ''Q'' = &Oslash;<br />
9 ENQUE(''Q, s'')<br />
10 '''while''' ''Q'' &ne; &Oslash;<br />
11 ''u'' = DEQUEUE(''Q'')<br />
12 '''for''' each ''v'' &isin; ''G.Adj''[''u'']<br />
13 '''if''' ''v.color'' == WHITE<br />
14 ''v.color'' = GRAY<br />
15 ''v.d'' = ''u.d'' + 1<br />
16 ''v''.&pi; = ''u''<br />
17 ENQUEUE(''Q, v'')<br />
18 ''u.color'' = BLACK<br />
</code></div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Breadth-first_search&diff=259Breadth-first search2014-09-25T16:40:15Z<p>Lkw: /* Pseudocode */</p>
<hr />
<div>== Pseudocode == <br />
<br />
<code><br />
BFS(''G,s'')<br />
1 '''for''' each vertex ''u'' &isin; ''G.V'' - {''s''}<br />
2 ''u.color'' = WHITE<br />
3 ''u.d'' = &infin;<br />
4 ''u.''&pi; = NIL<br />
5 ''s.color'' = GRAY<br />
6 ''s.d'' = 0<br />
7 ''s.&pi;'' = NIL<br />
8 ''Q'' = &Oslash;<br />
9 ENQUE(''Q, s'')<br />
10 '''while''' ''Q'' &ne; &Oslash;<br />
11 ''u'' = DEQUEUE(''Q'')<br />
12 '''for''' each ''v'' &isin; ''G.Adj''[''u'']<br />
13 '''if''' ''v.color'' == WHITE<br />
14 ''v.color'' = GRAY<br />
15 ''v.d'' = ''u.d'' + 1<br />
16 ''v''.&pi; = ''u''<br />
17 ENQUEUE(''Q, v'')<br />
18 ''u.color'' = BLACK<br />
</code></div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Breadth-first_search&diff=258Breadth-first search2014-09-25T16:39:54Z<p>Lkw: /* Pseudocode */</p>
<hr />
<div>== Pseudocode == <br />
<br />
<code><br />
BFS(''G,s'')<br />
1 '''for''' each vertex ''u'' &isin; ''G.V'' - {''s''}<br />
2 ''u.color'' = WHITE<br />
3 ''u.d'' = &infin;<br />
4 ''u.''&pi; = NIL<br />
5 ''s.color'' = GRAY<br />
6 ''s.d'' = 0<br />
7 ''s.&pi;'' = NIL<br />
8 ''Q'' = &Oslash;<br />
9 ENQUE(''Q, s'')<br />
10 '''while''' ''Q'' &ne; &Oslash;<br />
11 ''u'' = DEQUEUE(''Q'')<br />
12 '''for''' each ''v'' &isin; ''G.Adj''[''u'']<br />
13 '''if''' ''v.color'' == WHITE<br />
14 ''v.color'' = GRAY<br />
15 ''v.d'' = ''u.d'' + 1<br />
16 ''v''.&pi; = ''u''<br />
17 ENQUEUE(''Q, v'')<br />
18 ''u.color'' = BLACK<br />
</code></div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Breadth-first_search&diff=254Breadth-first search2014-09-25T16:30:11Z<p>Lkw: /* Pseudocode */</p>
<hr />
<div>== Pseudocode == <br />
<br />
<code><br />
BFS(''G,s'')<br />
1 '''for''' each vertex ''u'' &isin; ''G.V'' - {''s''}<br />
2 ''u.color'' = WHITE<br />
3 ''u.d'' = &infin;<br />
4 ''u.''&pi; = NIL<br />
5 ''s.color'' = GRAY<br />
6 ''s.d'' = 0<br />
7 ''s.&pi;'' = NIL<br />
8 ''Q'' = &Oslash;<br />
9 ENQUE(''Q, s'')<br />
10 '''while''' ''Q'' &ne; &Oslash;<br />
11 ''u'' = DEQUEUE(''Q'')<br />
12 '''for''' each ''v'' &isin; ''G.Adj''[''u'']<br />
13 '''if''' ''v.color'' == WHITE<br />
14 ''v.color'' = GRAY<br />
15 ''v.d'' = ''u.d'' + 1<br />
16 ''v''.&pi; = ''u''<br />
17 ENQUEUE(''Q, v'')<br />
18 ''u.color'' = BLACK<br />
</code></div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Breadth-first_search&diff=253Breadth-first search2014-09-25T16:29:49Z<p>Lkw: /* Pseudocode */</p>
<hr />
<div>== Pseudocode == <br />
<br />
<code><br />
BFS(''G, s'')<br />
1 '''for''' each vertex ''u'' &isin; ''G.V'' - {''s''}<br />
2 ''u.color'' = WHITE<br />
3 ''u.d'' = &infin;<br />
4 ''u.''&pi; = NIL<br />
5 ''s.color'' = GRAY<br />
6 ''s.d'' = 0<br />
7 ''s.&pi;'' = NIL<br />
8 ''Q'' = &Oslash;<br />
9 ENQUE(''Q, s'')<br />
10 '''while''' ''Q'' &ne; &Oslash;<br />
11 ''u'' = DEQUEUE(''Q'')<br />
12 '''for''' each ''v'' &isin; ''G.Adj''[''u'']<br />
13 '''if''' ''v.color'' == WHITE<br />
14 ''v.color'' = GRAY<br />
15 ''v.d'' = ''u.d'' + 1<br />
16 ''v''.&pi; = ''u''<br />
17 ENQUEUE(''Q, v'')<br />
18 ''u.color'' = BLACK<br />
</code></div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Breadth-first_search&diff=252Breadth-first search2014-09-25T16:29:26Z<p>Lkw: Created page with "== Pseudocode == <code> BFS(''G, s'') 1 '''for''' each vertex ''u'' &isin; ''G.V'' - {s} 2 ''u.color'' = WHITE 3 ''u.d'' = &infin; 4 ''u.''&pi; =..."</p>
<hr />
<div>== Pseudocode == <br />
<br />
<code><br />
BFS(''G, s'')<br />
1 '''for''' each vertex ''u'' &isin; ''G.V'' - {s}<br />
2 ''u.color'' = WHITE<br />
3 ''u.d'' = &infin;<br />
4 ''u.''&pi; = NIL<br />
5 ''s.color'' = GRAY<br />
6 ''s.d'' = 0<br />
7 ''s.&pi;'' = NIL<br />
8 ''Q'' = &Oslash;<br />
9 ENQUE(''Q, s'')<br />
10 '''while''' ''Q'' &ne; &Oslash;<br />
11 ''u'' = DEQUEUE(''Q'')<br />
12 '''for''' each ''v'' &isin; ''G.Adj''[''u'']<br />
13 '''if''' ''v.color'' == WHITE<br />
14 ''v.color'' = GRAY<br />
15 ''v.d'' = ''u.d'' + 1<br />
16 ''v''.&pi; = ''u''<br />
17 ENQUEUE(''Q, v'')<br />
18 ''u.color'' = BLACK<br />
</code></div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_insert&diff=251B-tree: insert2014-09-25T16:07:41Z<p>Lkw: </p>
<hr />
<div>== Pseudocode == <br />
<br />
<code><br />
B-TREE-INSERT(''T'', ''k'')<br />
1 ''r'' = ''T.root''<br />
2 '''if''' ''r.n'' == 2''t'' - 1<br />
3 ''s'' = ALLOCATE-NODE()<br />
4 ''T.root'' = ''s''<br />
5 ''s.leaf'' = FALSE<br />
6 ''s.n'' = 0<br />
7 ''s.c1111'' = ''r''<br />
8 B-TREE-SPLIT-CHILD(''s'', 1)<br />
9 B-TREE-INSERT-NONFULL(''s, k'')<br />
10 '''else''' B-TREE-INSERT-NONFULL(''r, k'') <br />
</code><br />
<br />
<code><br />
B-TREE-INSERT-NONFULL(''x'', ''k'')<br />
1 ''i'' = ''x.n''<br />
2 '''if''' ''x.leaf''<br />
3 '''while''' ''i &ge; 1 and ''k'' < ''x.key''iiiii<br />
4 ''x.key''iii+111 = ''x.key''iiiii<br />
5 ''i'' = ''i'' - 1<br />
6 ''x.key''iii+111 = ''k''<br />
7 ''x.n'' = ''x.n'' + 1<br />
8 DISK-WRITE(''x)<br />
9 '''else while''' ''i'' &ge; 1 and ''k'' < ''x.key''iiiii<br />
10 ''i'' = ''i'' - 1<br />
11 ''i'' = ''i'' + 1<br />
12 DISK-READ(''x.c''iiii)<br />
13 '''if''' ''x.ciiii.n'' == 2''t'' - 1<br />
14 B-TREE-SPLIT-CHILD(''x, i'')<br />
15 '''if''' ''k'' > ''x.key''iiii<br />
16 ''i'' = ''i'' + 1<br />
17 B-TREE-INSERT-NONFULL(''x.ciii, k) <br />
</code></div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=B-tree:_insert&diff=249B-tree: insert2014-09-25T15:56:07Z<p>Lkw: Created page with "<code> B-TREE-INSERT(''T'', ''k'') 1 ''r'' = ''T.root'' 2 '''if''' ''r.n'' == 2''t'' - 1 3 ''s'' = ALLOCATE-NODE() 4 ''T.root'' = ''s'' 5 ''s.leaf''..."</p>
<hr />
<div><code><br />
B-TREE-INSERT(''T'', ''k'')<br />
1 ''r'' = ''T.root''<br />
2 '''if''' ''r.n'' == 2''t'' - 1<br />
3 ''s'' = ALLOCATE-NODE()<br />
4 ''T.root'' = ''s''<br />
5 ''s.leaf'' = FALSE<br />
6 ''s.n'' = 0<br />
7 ''s.c1111'' = ''r''<br />
8 B-TREE-SPLIT-CHILD(''s'', 1)<br />
9 B-TREE-INSERT-NONFULL(''s, k'')<br />
10 '''else''' B-TREE-INSERT-NONFULL(''r, k'') <br />
</code></div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Bubble_sort&diff=248Bubble sort2014-09-25T15:32:54Z<p>Lkw: /* Pseudocode */</p>
<hr />
<div>== Pseudocode == <br />
<br />
<code><br />
BUBBLESORT(''A'')<br />
1 '''for''' ''i'' = 1 '''to''' "A.length" - 1 <br />
2 '''for''' ''j'' = ''A.length'' '''downto''' ''i'' + 1<br />
3 '''if''' ''A''[''j''] < ''A''[''j'' - 1]<br />
4 exchange ''A''[''j''] with ''A''[''j'' - 1]<br />
</code></div>Lkwhttps://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Bubble_sort&diff=247Bubble sort2014-09-25T15:32:20Z<p>Lkw: /* Pseudocode */</p>
<hr />
<div>== Pseudocode == <br />
<br />
<code><br />
BUBBLESORT(''A'')<br />
1 '''for''' ''i'' = 1 '''to''' "A.length" - 1 <br />
2 '''for'' ''j'' = ''A.length'' '''downto''' ''i'' + 1<br />
3 '''if''' ''A''[''j''] < ''A''[''j'' - 1]<br />
4 exchange ''A''[''j''] with ''A''[''j'' - 1]<br />
</code></div>Lkw