====== B-stromy ======

Skripta 2.3.1

nebo http://cis.stvincent.edu/html/tutorials/swd/btree/btree.html

  * B-stromy jsou vyvažované stromy se stejnou délkou cesty od kořene ke všem listům.
  * Každý uzel obsahuje několik hodnot a několik ukazatelů na podstromy (zobecnění binárních stromů).
  * Každý uzel, který není listem, má alespoň dva podstromy (důležité pro efektivní vyhledávání)


B-stromy používají databázové aplikace pro ukládání setříděných hodnot (indexů) na disk. \\
Maximální počet prvků v uzlu se volí podle velikosti sektorů nebo alokačních bloků na disku.

http://cs.wikipedia.org/wiki/B-strom \\
http://en.wikipedia.org/wiki/B-tree

Jak zmiňuje poslední odkaz, terminologie a implementace se může v jednotlivých případech mírně lišit. \\
V následující podkapitole shrnu pravidla používaná v našem programu pro vkládání hodnot do B-stromu. 

Videa: \\
  * B-Tree https://www.youtube.com/watch?v=C_q5ccN84C8
  * Nebo jiné B-Tree http://www.youtube.com/watch?v=GKa_t7fF8o0
  * B Trees v databázových aplikacích http://www.youtube.com/watch?v=aZjYr87r1b8

===== Požadavky na B-strom  =====

  * V každém uzlu, kromě kořene, musí být alespoň **Max/2** hodnot
  * V každém uzlu smí být nejvýše **Max** hodnot
  * Pokud má uzel, který není koncovým listem,  **cnt** hodnot, musí mít **cnt+1** podstromů
  * Všechny cesty od kořene k libovolnému listu jsou stejně dlouhé

  * Prázdný strom budeme reprezentovat nulovým ukazatelem
  * Strom s méně než **Max/2** hodnotami kořenovým uzlem s těmito hodnotami
  * Stejně ukládáme i strom s nejvýše **Max** hodnotami 

  * Jednotlivé podstromy a hodnoty indexuejeme od **0**
  * Hodnoty v jednom uzlu tvoří rostoucí posloupnost

  * Zaměříme se na jeden uzel, který má **cnt** hodnot, hodnoty v tomto uzlu budeme nazývat klíče
  * Zmíněný uzel má klíče s indexy **0** ... **cnt-1** a podstromy indexy **0** ... **cnt**
  * První podstrom (s indexem **0**) obsahuje hodnoty menší než první klíč (a tedy menší než všechny klíče)
  * Poslední podstrom (s indexem **cnt**) obsahuje hodnoty větší než poslední klíč (s indexem **cnt-1**), (a tedy větší než všechny klíče)
  * Podstrom s idexem **i** obsahuje hodnoty větší než klíč s indexem **i-1** a  menší než klíč s indexem **i**, pro i = 1, ... , cnt-1 

:!: Pokud **Max/2**  je větší nebo rovno **2**, má každý uzel (kromě listů) alespoň dva podstromy





===== Příklad =====

Do prázdného stromu vložíme hodnotu **30**.

{{zalg::btree-new.png}}

==== Vložíme celkem 5 hodnot a přeplníme kořen stromu ====

Postupně přidáváme hodnoty **20, 10, 40, 50**. \\
Pro **Max=4** se hodnoty zatřiďují mezi předcházející hodnoty v kořenovém prvku. \\
Hodnota **50** přeplní kořen stromu.

{{zalg::btree-before-root-split.png}}

Jako dělící bod vybereme hodnotu **30**. \\
Původní kořenový prvek se rozdělí na dva. \\
A ještě musíme přidat nový kořenový prvek, do kterého umístíme **30**.

{{zalg::btree-after-root-split.png}}


==== Po vložení několika prvků přibývají listy stromu ====

Přidáváme 21, ..., 29 a potom 51, ... 52. \\
Pokud se jednotlivé listy přeplní, rozdělí se a do kořene přibývá další hodnota.

{{zalg::btree-full.png}}

==== Další hodnota přeplní list ====

Vložíme *53* a opět se přeplní list, jako dělící bod bude použita hodnota **51**.

{{zalg::btree-before-node-split.png}}

Hodnota **51** přeplní kořen stromu, musíme kořen rozdělit, dělícím bodem bude **27**.

{{zalg::btree-after-node-split.png}}

Výsledný stav

{{zalg::btree-complete.png}}



===== Datová struktura pro jeden uzel =====

  * V každém uzlu bude uloženo **cnt** hodnot, cnt < =  Max.
  * V poli **key** bude **cnt** hodnot
  * V poli **ref** bude **cnt+1** ukazatelů na podstromy

  * Prazdný strom reprezentujeme nulovým ukazatelem
  * Kořenový prkek má **cnt** od **1** do **Max**
  * Ostatní prkeky mají **cnt** od **Max/2** do **Max**
  

:?: Pro snažši vkládání nové hodnoty deklarujeme pole **key** a **ref** o jeden prvek delší

<code C++>
const int Max = 4;

struct Item
{
    int cnt; // pocet klicu 
    int key [Max+1]; // key[0], ... key[cnt-1], a jeden navic
    Item * ref [Max+2]; // ptr [0], ... ptr [cnt], a jeden navic
    Item();
};
</code>

Celý strom budeme reprezentovat ukazatelem na **Item**

Konstruktor struktury **Item** nastaví **cnt** na **0** (ale prvek s nulovým počtem hodnot se ve stromu nakonec nikdy neobjeví). \\
Hodnoty inicializuje na **-1** (to nám může usnadnit ladění programu). \\
Ukazatele na podstromy nastaví na **nullptr** (tak to zůstane u listů).

:?: V poli **key** smíme používat jen indexy **0**, ... **cnt-1**. \\
V poli **ref** jen indexy **0**, ... **cnt**. \\

<code C++>
Item::Item()
{
    cnt = 0;
    for (int i = 0; i < Max + 1; i++) key[i] = -1;
    for (int i = 0; i < Max + 2; i++) ref [i] = nullptr;
}
</code>



===== Funkce enter0 =====

Funkce **enter0** vloží do prvku zadaného ukazatelem **p** novou hodnotu **val**.

Funkce **enter0** není //určena pro vkládání do kořene stromu//, ale pro //"nižší"// patra.

<code C++>
void enter0 (Item * p, int val);
</code>

Vyhledáme vhodné místo pro naši novou hodnotu
<code C++>
    int i = 0;
    while (i < p->cnt && p->key[i] < val) i++;
</code>
Přeskočíme klíče s menší hodnotou: **p->key[i] < val** \\
Před porovnáním zkontrolujeme zda index **i** má přípustnou hodnotu: **i < p->cnt**

A) Pokud  **i** je menší než **p->cnt**, vložíme novou hodnotu na pozici s indexem **i** a původní hodnoty od indexu **i** výše posuneme o jedno políčko. \\
B) Pokud se cyklus zastaví s indexem **i** rovným **p->cnt**, patří nová hodnota na konec pole **key**, za všechny současné hodnoty. 

:?: A) **i <  p->cnt** , **key[j] < val** pro **j < i**, **val < = key[i]** \\
:?: B) **i = = p->cnt** , **key[j] < val** pro **j = 0, ..., cnt-1**

Pokud ve variantě A) nastane rovnost, klíč je již ve stromu uložen. Můžeme ohlásit chybu nebo prostě klíč ve stromu ponechat-
<code C++>
    if (i < p->cnt && p->key[i] == val) {  }
</code>


===== Jsme na dně =====

Podívám se, zda již nejsme na nejnižším patře, zda náš prvek není listem. \\
:?: Pokud pod náma je nulový ukazatel jsou i ostatní ukazatele nulové, neboť všechny cesty jsou stejně dlouhé.

Uvolníme místo pro novou hodnotu, kterou vložíme do **key[i]**. Posuneme key [i], ..., key [cnt-1] o políčko dále. \\
:?: Kopírování začneme od vyšších indexů, jinak si hodnoty s vyššími indexy přepíšeme.

Posuneme ref [i], ..., ref [cnt] o políčko dále, ukazatelů je o jeden více než klíčů. 

Do pole **key** na pozici **i** uložíme novou hodnotu. \\
Do **ref** na pozici **i** uložíme nulový ukazatel (jsme na nejnižším patře). \\
Nezapomene zvětšit počet hodnot **cnt**. \\
:?: Možná jsme překročili povolený počet prvků **Max**, ale v polích máme místo pro jeden prvek navíc.

<code C++>
        Item * t = p->ref[i];
        if (t == nullptr)
        {
            for (int k = p->cnt-1; k >= i; k--) p->key[k+1] = p->key[k];
            for (int k = p->cnt; k >= i; k--) p->ref[k+1] = p->ref[k];
            p->key[i] = val;
            p->ref[i] = nullptr;
            p->cnt++;
        }

</code>


===== Pokud nejsme na dně =====

Pokud nejsme na nejižším patře, zavoláme **enter0** pro vkládání do příslušného podstromu.

:?: Pokud nová hodnota byla menší než **key[i]**, patří nová hodnota do podstromu **ref[i]** (varianta A, rovnost jsem již vyloučili). \\
:?: Pokud nová hodnota byla větší než všechny hodnoty **key**, patří nová hodnota do posledního podstromu (varianta B).

<code C++>
        Item * t = p->ref[i];
        if (t == nullptr)
        {
            /* již bylo popsáno */
        }
        else
        {
            enter0 (t, val); // vložíme do nižšího patra 
            /* musíme zkontrolovat, zda prvek t není přeplněn */

        }
</code>

Rekurzivní volání **enter0** uloží hodnotu do podstromu. \\
( Tím by skončilo vkládání do //nevyvažovaného binárního// stromu. [[strom_add|funkce insert v binárních stromech]] ) \\
My ještě musíme zkontrolovat, zda v uzlu **t** není příliš mnoho hodnot.



===== Pod náma je příliš mnoho prvků, musíme rozlomit přeplněný prvek =====

Pokud je uvnitř uzlu **t** příliš mnoho prvků, \\
ponecháme Max/2 hodnot v původním uzlu **t**,  \\
jednu hodnotu //"vytáhneme"// o patro výše a vložíme ji do uzlu **p**, \\
ostatní hodnoty přesuneme do nového uzlu **n**, ktrý umísíme vpravo od **t**.



==== Naplánujeme si rozdělení ====
Označíme **a** a **b** počty prvků, které se mají ocitnout v uzlech **t** a **n**. \\
Proměnná **d** bude obsahovat hodnotu, která má být vložena do uzlu **p**.

<code C++>
            if (t->cnt == Max + 1)
            {
                int a = Max / 2; // a klicu zustane v t
                int b = t->cnt-a-1; // b klicu do noveho bloku
                int d = t->key[a]; // delici bod
</code>

{{zalg::btree-before.png}}







==== Vytvoříme nový uzel pro pravou část prvků ====

Vytvoříme nový uzel **n**. \\
Do něj patří **b** hodnot. 

Z uzlu **t** přesuneme hodnoty **t->key[a+1]**, ..., **t->key[cnt-1]** do nového **n->key[0]**, ..., **n->key[b-1]**.

Ukazatele na podstromy **t->ref[a+1]**, ..., **t->ref[cnt]** přesuneme do **n->ref[0]**, ..., **n->ref[b]**

<code C++>
                Item * n = new Item;
                n->cnt = b;
                for (int k = a + 1; k < t->cnt; k++)   n->key[k-a-1] = t->key[k];
                for (int k = a + 1; k < t->cnt+1; k++) n->ref[k-a-1] = t->ref[k];
</code>

{{zalg::btree-after.png}}

==== Uklidíme v původně přeplněném prvku ====

:?: V uzlu **t** zůstane **a** hodnot s indexy **0**, ..., **a-1**. \\
Hodnota s indexem **a** je dělícím bodem **d**. \\
Ostatní hodnoty patří do **n**. 

:?: V levém uzlu **t** zůstane i ukazatel **ref[a]**. (Ukazatelů je o jedna více než hodnot.) \\
Ukazatel **ref[a+1]** a následující patří do **n**.

V původním uzlu **t** nastavíme počet hodnot na **a**. \\
A pro přehlednější ladění odstraníme přebytečné hodnoty.

<code C++>
                for (int k = a + 1; k < t->cnt; k++) t->key[k] = -1;
                for (int k = a + 1; k < t->cnt + 1; k++) t->ref[k] = nullptr;
                t->cnt = a;
</code>

==== Vložíme jednu hodnotu a nový prvek do původního podstromu ====

Zbývá vložit hodnotu **d** na pozici s indexem **i** do //"nadřazeného"// prvku **p**. 

Nejdříve posuneme původní hodnoty **p->key[i]**, ..., **p->key[p->cnt-1]** o jedno políčko doprava. \\
A také posuneme ukazatatele **p->ref[i+1]**, ..., **p->ref[p->cnt]**.

Ukazatel **p->ref[i]** stále míří na **t**. \\
Do **p->key[i]** vložíme //dělící// hodnotu **d**. \\
Ukazatel **p->ref[i+1]** směřuje na nové **n**. \\

<code C++>
                for (int k = p->cnt-1; k >= i; k--) p->key[k + 1] = p->key[k];
                for (int k = p->cnt; k > i; k--) p->ref[k + 1] = p->ref[k];
                p->key[i] = d;
                p->ref[i+1] = n;
                p->cnt ++;
</code>

Zvýšíme počet prvků uvnitř **p**.

Pokud **p** přeplníme, ať si to vyřeší ten, kdo tuto funkci **enter0** zavolal.

Pokud jsme zavolali enter0 rekurzivně ve funkci enter0, tak jsme přeplnění právě řešíli.

Zbývá ještě vyřešit případné přeplnění kořene stromu.
Tam je postup odlišný musíme přidat nový kořen a pod něj umístit dva prvky, které vzniky z původního přeplněného kořenu.

===== Celá funkce enter0 =====

<code C++>
void enter0 (Item * p, int val)
{
    int i = 0;
    while (i < p->cnt && p->key[i] < val) i++;
    // i == p->cnt , vsechny byly mensi, pridat 
    // i < p->cnt, p->key[i] >= val
    if (i < p->cnt && p->key[i] == val) {  }
    else {
        Item * t = p->ref[i];
        if (t == nullptr)
        {
            for (int k = p->cnt - 1; k >= i; k--) p->key[k + 1] = p->key[k];
            for (int k = p->cnt; k >= i; k--) p->ref[k + 1] = p->ref[k];
            p->key[i] = val;
            p->ref[i] = nullptr;
            p->cnt++;
        }
        else
        {
            enter0 (t, val);
            if (t->cnt == Max + 1)
            {
                int a = Max / 2; // a klicu zustane v t
                int b = t->cnt - a -1; // b klicu do noveho bloku
                int d = t->key[a]; // delici bod

                Item * n = new Item;
                n->cnt = b;
                for (int k = a + 1; k < t->cnt; k++) n->key[k - a - 1] = t->key[k];
                for (int k = a + 1; k < t->cnt+1; k++) n->ref[k - a - 1] = t->ref[k];

                for (int k = a + 1; k < t->cnt; k++) t->key[k] = -1;
                for (int k = a + 1; k < t->cnt + 1; k++) t->ref[k] = nullptr;
                t->cnt = a;

                for (int k = p->cnt - 1; k >= i; k--) p->key[k + 1] = p->key[k];
                for (int k = p->cnt; k > i; k--) p->ref[k + 1] = p->ref[k];
                p->key[i] = d;
                p->ref[i+1] = n;
                p->cnt++;
            }
        }
    }
}
</code>



===== Funkce enter =====

Funkce **enter** se stará o vkládání do kořene B-stromu.

Pokud byl původní ukazatel **p** nulový, vytvoříme nový prvek s jednou novou hodnotou. \\
Tento prvek se stane kořenem stromu. \\
Parametr **p** je předáván odkazem (**&**), aby se změna promítla i do proměěnné použité jako skutečný parametr při volání funkce **enter**.

Například do proměnné **root** uložíme **nullptr**, představující prázdný strom. \\
A první volání funkce **enter** do proměnné **root** uloží nový prvek. 

<code C++>
    Item * root = nullptr;
    enter (root, 30);
    enter (root, 20);
</code>


==== Od prázdného stromu k jednoprvkovému ====

Jednoprvkový strom bude obsahovat jednu (novou) hodnotu a dva nulové ukazatele.

<code C++>
void enter (Item * & p, int val)
{
    if (p == nullptr)
    {
        p = new Item;
        p->cnt = 1;
        p->key[0] = val;
        p->ref[0] = nullptr;
        p->ref[1] = nullptr;
    }
    else
    {
       /* strom již existuje */
    }
}
</code>

==== Vložení hodnoty pomocí funkce enter0 ====

Pokud kořen stromu již existuje, použijeme funkci **enter0** pro vložení hodnoty. \\
A podíváme se zda kořen stromu není přeplněný. \\
Kořen stromu v tomto případě připomíná proměnnou **t** z minulé funkce **enter0**.

<code C++>
    if (p == nullptr)
    {
    }
    else
    {
        enter0 (p, val);
        Item * t = p;
        if (t->cnt == Max + 1)
        {
           /* přeplněný kořen stromu */
        }
    }
</code>

==== Rozdělění kořene stromu ====

Stejně jako ve funkci **enter0** vytvoříme nový prvek **n** a přesuneme do něj polovinu hodnot.

<code C++>
            int a = Max / 2; // a klicu zustane v t
            int b = t->cnt - a - 1; // b klicu do noveho bloku
            int d = t->key[a]; // delici bod

            Item * n = new Item;
            n->cnt = b;
            for (int k = a + 1; k < t->cnt; k++)     n->key[k-a-1] = t->key[k];
            for (int k = a + 1; k < t->cnt + 1; k++) n->ref[k-a-1] = t->ref[k];

            for (int k = a + 1; k < t->cnt; k++)     t->key[k] = -1;
            for (int k = a + 1; k < t->cnt + 1; k++) t->ref[k] = nullptr;
            t->cnt = a;
</code>


==== Přidání nového patra ====

//B-stromy rostou tak, že je u kořene uřízneme, zvedneme a vložíme nový špalek.//

//Já vám říkal, že programátoři nejsou dobří zahradníci.//

A potom je postup odlišný od funkce **enter0**. \\
Vytvoříme nový prvek, který se stane novým kořenem stromu. \\
Opět připomínám, že **p** je předávaná //odkazem//.

V novém kořeni stromu bude uložena dělící hodnota **d**. \\
A bude mít za podstromy **t** (původní kořen stromu) a nově vytvořený **n**.

:?: Ukazatel na původní kořen stromu jsme si schovali do obyčejného ukazatele **t**.

<code C++>
            p = new Item;
            p->cnt = 1;
            p->ref[0] = t;
            p->key[0] = d;
            p->ref[1] = n;
</code>





===== Celý program =====

<code C++>
#include <iostream>
using namespace std;

const int Max = 4;

struct Item
{
    int cnt; // pocet klicu
    int key [Max+1]; // key[0], ... key[cnt-1], a jeden navic
    Item * ref [Max+2]; // ptr [0], ... ptr [cnt], a jeden navic
    Item();
};

Item::Item()
{
    cnt = 0;
    for (int i = 0; i < Max + 1; i++) key[i] = -1;
    for (int i = 0; i < Max + 2; i++) ref [i] = nullptr;
}

void enter0 (Item * p, int val)
{
    int i = 0;
    while (i < p->cnt && p->key[i] < val) i++;
    // i == p->cnt , vsechny byly mensi, pridat 
    // i < p->cnt, p->key[i] >= val
    if (i < p->cnt && p->key[i] == val) {  }
    else {
        Item * t = p->ref[i];
        if (t == nullptr)
        {
            for (int k = p->cnt - 1; k >= i; k--) p->key[k + 1] = p->key[k];
            for (int k = p->cnt; k >= i; k--) p->ref[k + 1] = p->ref[k];
            p->key[i] = val;
            p->ref[i] = nullptr;
            p->cnt++;
        }
        else
        {
            enter0 (t, val);
            if (t->cnt == Max + 1)
            {
                int a = Max / 2; // a klicu zustane v t
                int b = t->cnt - a -1; // b klicu do noveho bloku
                int d = t->key[a]; // delici bod

                Item * n = new Item;
                n->cnt = b;
                for (int k = a + 1; k < t->cnt; k++) n->key[k - a - 1] = t->key[k];
                for (int k = a + 1; k < t->cnt+1; k++) n->ref[k - a - 1] = t->ref[k];

                for (int k = a + 1; k < t->cnt; k++) t->key[k] = -1;
                for (int k = a + 1; k < t->cnt + 1; k++) t->ref[k] = nullptr;
                t->cnt = a;

                for (int k = p->cnt - 1; k >= i; k--) p->key[k + 1] = p->key[k];
                for (int k = p->cnt; k > i; k--) p->ref[k + 1] = p->ref[k];
                p->key[i] = d;
                p->ref[i+1] = n;
                p->cnt++;
            }
        }
    }
}

void enter (Item * & p, int val)
{
    if (p == nullptr)
    {
        p = new Item;
        p->cnt = 1;
        p->key[0] = val;
        p->ref[0] = nullptr;
        p->ref[1] = nullptr;
    }
    else
    {
        enter0 (p, val);
        Item * t = p;
        if (t->cnt == Max + 1)
        {
            int a = Max / 2; // a klicu zustane v t
            int b = t->cnt - a - 1; // b klicu do noveho bloku
            int d = t->key[a]; // delici bod

            Item * n = new Item;
            n->cnt = b;
            for (int k = a + 1; k < t->cnt; k++) n->key[k - a - 1] = t->key[k];
            for (int k = a + 1; k < t->cnt + 1; k++) n->ref[k - a - 1] = t->ref[k];

            for (int k = a + 1; k < t->cnt; k++) t->key[k] = -1;
            for (int k = a + 1; k < t->cnt + 1; k++) t->ref[k] = nullptr;
            t->cnt = a;

            p = new Item;
            p->cnt = 1;
            p->ref[0] = t;
            p->key[0] = d;
            p->ref[1] = n;
        }
    }
}

void print (Item * p)
// alespon vytiskneme hodnoty v rostoucim poradi
{
    if (p != nullptr) 
    {
        for (int i = 0; i < p->cnt; i++)
        {
            print (p->ref[i]);
            cout << p->key[i] << endl;
        }
        print (p->ref[p->cnt]);
    }
}

int main ()
{
    Item * root = nullptr;
    enter(root, 30);
    enter(root, 20);
    enter(root, 10);
    enter(root, 40);
    enter(root, 50);

    for (int k = 21; k <= 29; k++) enter(root, k);

    for (int k = 51; k <= 800; k++) enter(root, k);

    print (root);
}
</code>

===== Grafický výstup do HTML souboru s pomocí JavaScriptu =====

Jen pro ilustraci: zobrazování stromů. 

{{zalg::btree.png}}

http://gitlab.fjfi.cvut.cz/culikzde/zalg/-/tree/master/btree-js \\
Náš program vytvoří textový soubor //output.html//. \\
V něm bude popis stromu ve tvaru 

<code JavaScript>
    [ 'text zobrazený v uzlu', [ první podstrom ], [ druhý podstrom ] ]
</code>

<code JavaScript>
['27, 54, 63, 72',
   ['21, 24',
      ['10, 20'],
      ['22, 23'],
      ['25, 26']
   ],
   ['30, 51',
      ['28, 29'],
      ['40, 50'],
      ['52, 53']
   ],
   ['57, 60',
      ['55, 56'],
      ['58, 59'],
      ['61, 62']
   ],
   ['66, 69',
      ['64, 65'],
      ['67, 68'],
      ['70, 71']
   ],
   ['75, 78',
      ['73, 74'],
      ['76, 77'],
      ['79, 80']
   ]
]
</code>

Výpis v tomto tvaru zajistí funkce **display**. 

<code C++>
void display (ofstream & f, Item * p, bool comma = false, int level = 0)
{
    if (p != nullptr)
    {
        bool list = (p->ref[0] == nullptr);
        for (int i = 1; i <= level; i++) f << "   ";
        f << "[";

        // klice v jednoduchych uvozovkach
        f << "'";
        for (int i = 0; i < p->cnt; i++)
        {
            f << p->key [i];
            if (i < p->cnt-1) f << ", ";
        }
        f << "'";

        if (!list)
        {
           f << ","; // carka pred nasledujicimi hodnotam
           f << endl;
           for (int i = 0; i < p->cnt + 1; i++)
           {
               display (f, p->ref[i], i < p->cnt, level+1);
           }
        }

        if (!list)
            for (int i = 1; i <= level; i++) f << "   ";
        f << "]";
        if (comma) f << ",";
        f << endl;
    }
}
</code>

Funkce **displayData** přidá program v JavaScriptu, využívající knihovnu **mxGraph**.

http://jgraph.github.io/mxgraph \\
http://jgraph.github.io/mxgraph/javascript/index.html \\
http://github.com/jgraph/mxgraph

<code C++>
void displayData (Item * p)
{
    ofstream f ("output.html");

    f << "<html>" << endl;
    f << "<head>" << endl;
    f << "<title>B-Tree with mxGraph</title>" << endl;
    f << "<script type=\"text/javascript\">" << endl;
    f << "    mxBasePath = 'http://jgraph.github.io/mxgraph/javascript/src';" << endl;
    f << "</script>" << endl;
    f << "<script type=\"text/javascript\" src=\"http://jgraph.github.io/mxgraph/javascript/src/js/mxClient.js\"></script>" << endl;
    f << "<script type=\"text/javascript\">" << endl;

    f << "    var data =" << endl;
    display (f, p);
    f << ";" << endl;

    f << "function display (graph, parent, above, items)" << endl;
    f << "{" << endl;
    f << "    var name;" << endl;
    f << "    if (Array.isArray (items))" << endl;
    f << "       name = items [0];" << endl;
    f << "    else" << endl;
    f << "       name = items;" << endl;
    f << endl;
    f << "    var v1 = graph.insertVertex (parent, null, name, 0, 0, 80, 30);" << endl;
    f << "    if (above != null)" << endl;
    f << "       var e1 = graph.insertEdge(parent, null, '', above, v1);" << endl;

    f << "    if (Array.isArray (items))" << endl;
    f << "    {" << endl;
    f << "      var i;" << endl;
    f << "      for (i = 1; i < items.length; i++)" << endl;
    f << "      {" << endl;
    f << "         var item = items [i];" << endl;
    f << "         display (graph, parent, v1, items [i]);" << endl;
    f << "      }" << endl;
    f << "    }" << endl;
    f << "    return v1;" << endl;
    f << "}" << endl;
    f << "function main (container)" << endl;
    f << "{" << endl;
    f << "    var graph = new mxGraph(container);" << endl;
    f << "    var parent = graph.getDefaultParent();" << endl;
    f << "    graph.getModel().beginUpdate();" << endl;
    f << "    var v1 = display (graph, parent, null, data);" << endl;
    f << "    var layout = new mxHierarchicalLayout (graph, mxConstants.DIRECTION_NORTH);" << endl;
    f << "    layout.execute (graph.getDefaultParent(), v1);" << endl;
    f << "    graph.getModel().endUpdate();" << endl;
    f << "};" << endl;
    f << "</script>" << endl;
    f << "</head>" << endl;
    f << "<body onload=\"main(document.getElementById('graphContainer'))\">" << endl;
    f << "<div id=\"graphContainer\">" << endl;
    f << "</div>" << endl;
    f << "</body>" << endl;
    f << "</html>" << endl;

    f.close ();
}
</code>

<code C++>
int main()
{
    Item * root = nullptr;
    enter(root, 30);
    enter(root, 20);
    enter(root, 10);
    enter(root, 40);
    enter(root, 50);

    for (int k = 21; k <= 29; k++) enter(root, k);

    for (int k = 51; k <= 80; k++) enter(root, k);

    displayData (root);
}
</code>

Zde je výsledný soubor //output.html//. \\
Stačí uložit do textového souboru a podívat se na něj webovým prohížečem.

<code JavaScript>
<html>
<head>
<title>B-Tree with mxGraph</title>
<script type="text/javascript">
    mxBasePath = 'http://jgraph.github.io/mxgraph/javascript/src';
</script>
<script type="text/javascript" src="http://jgraph.github.io/mxgraph/javascript/src/js/mxClient.js"></script>
<script type="text/javascript">
    var data =
['27, 54, 63, 72',
   ['21, 24',
      ['10, 20'],
      ['22, 23'],
      ['25, 26']
   ],
   ['30, 51',
      ['28, 29'],
      ['40, 50'],
      ['52, 53']
   ],
   ['57, 60',
      ['55, 56'],
      ['58, 59'],
      ['61, 62']
   ],
   ['66, 69',
      ['64, 65'],
      ['67, 68'],
      ['70, 71']
   ],
   ['75, 78',
      ['73, 74'],
      ['76, 77'],
      ['79, 80']
   ]
]
;
function display (graph, parent, above, items)
{
    var name;
    if (Array.isArray (items))
       name = items [0];
    else
       name = items;

    var v1 = graph.insertVertex (parent, null, name, 0, 0, 80, 30);
    if (above != null)
       var e1 = graph.insertEdge(parent, null, '', above, v1);
    if (Array.isArray (items))
    {
      var i;
      for (i = 1; i < items.length; i++)
      {
         var item = items [i];
         display (graph, parent, v1, items [i]);
      }
    }
    return v1;
}
function main (container)
{
    var graph = new mxGraph(container);
    var parent = graph.getDefaultParent();
    graph.getModel().beginUpdate();
    var v1 = display (graph, parent, null, data);
    var layout = new mxHierarchicalLayout (graph, mxConstants.DIRECTION_NORTH);
    layout.execute (graph.getDefaultParent(), v1);
    graph.getModel().endUpdate();
};
</script>
</head>
<body onload="main(document.getElementById('graphContainer'))">
<div id="graphContainer">
</div>
</body>
</html>
</code>