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

• 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

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

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.

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.

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.

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

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

Výsledný stav

• 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ší

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();
};

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.

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;
}

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.

void enter0 (Item * p, int val);

Vyhledáme vhodné místo pro naši novou hodnotu

    int i = 0;
    while (i < p->cnt && p->key[i] < val) i++;

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-

    if (i < p->cnt && p->key[i] == val) {  }

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.

        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++;
        }

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).

        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 */
 
        }

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

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.

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.

            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

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]

                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];

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.

                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;

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.

                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 ++;

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.

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++;
            }
        }
    }
}

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.

    Item * root = nullptr;
    enter (root, 30);
    enter (root, 20);

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

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 */
    }
}

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.

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

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

            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;

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.

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

#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);
}

Jen pro ilustraci: zobrazování stromů.

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

    [ 'text zobrazený v uzlu', [ první podstrom ], [ druhý podstrom ] ]

['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']
   ]
]

Výpis v tomto tvaru zajistí funkce display.

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;
    }
}

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

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 ();
}

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);
}

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.

<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>