Completar ejemplo de conteo de referencias

[z.facultad/75.00/informe.git] / source / gc.rst

diff --git a/source/gc.rst b/source/gc.rst
index c37672f102cdf45924016cbc8e8e7db49439f21f..2da1a95ea1b41d50e6efa9e2135428b4fe4d16f5 100644 (file)
--- a/source/gc.rst
+++ b/source/gc.rst
@@ -805,10 +805,12 @@ Ejemplo
 
 A continuación se presenta un ejemplo gráfico para facilitar la comprensión
 del algoritmo. Por simplicidad se asumen celdas de tamaño fijo con dos
 
 A continuación se presenta un ejemplo gráfico para facilitar la comprensión
 del algoritmo. Por simplicidad se asumen celdas de tamaño fijo con dos

-punteros, ``left`` y ``right`` y se muestra el contador de referencias
-abajo del nombre de cada celda. Se parte con una pequeña estructura ya
-construída y se muestra como opera el algoritmo al eliminar o cambiar una
-referencia (cambios en la conectividad del grafo).
+punteros, ``left`` (``l``) y ``right`` (``r``) y se muestra el contador de
+referencias abajo del nombre de cada celda. Se parte con una pequeña
+estructura ya construída y se muestra como opera el algoritmo al eliminar
+o cambiar una referencia (cambios en la conectividad del grafo). En un
+comienzo todas las celdas son accesibles desde el *root set* por lo tanto
+son todas parte del *live set*.

 
 Se comienza por eliminar la referencia de ``r0`` a ``h1``, que determina
 que ``h1`` se convirtió en *basura* (figura :vref:`fig:gc-rc-rm-1`). Esto
 
 Se comienza por eliminar la referencia de ``r0`` a ``h1``, que determina
 que ``h1`` se convirtió en *basura* (figura :vref:`fig:gc-rc-rm-1`). Esto


@@ -823,13 +825,60 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el
 
    .. subfig::
 
 
    .. subfig::
 

-      Se ejecuta ``update(r0, null)``.
+      Estado inicial del grafo de conectividad.

 
       .. digraph:: g3_1
 
          margin = 0;
          ratio  = fill;
 
       .. digraph:: g3_1
 
          margin = 0;
          ratio  = fill;

-         size   = "3.0,3.8";
+         size   = "1.9,2.6";
+         edge [ color = gray40 ];
+         node [
+            shape     = record,
+            width     = 0,
+            height    = 0,
+            style     = filled,
+            fillcolor = gray25,
+            fontcolor = white
+         ];
+
+         subgraph cluster_all {
+
+            root [
+               label     = "root\nset|<r0> r0|<r1> r1",
+               style     = filled,
+               fillcolor = gray96,
+               fontcolor = black,
+            ];
+
+            h1 [ label = "h1\n1|<l> l|<r> r" ];
+            h2 [ label = "h2\n2|<l> l|<r> r" ];
+            h3 [ label = "h3\n2|<l> l|<r> r" ];
+            h4 [ label = "h4\n1|<l> l|<r> r" ];
+            h5 [ label = "h5\n1|<l> l|<r> r" ];
+            h6 [ label = "h6\n1|<l> l|<r> r" ];
+
+            root:r0 -> h1;
+            root:r1 -> h3;
+            h1:l -> h2;
+            h1:r -> h3;
+            h2:l -> h4;
+            h2:r -> h5;
+            h3:l -> h2;
+            h3:r -> h6;
+
+         }
+
+   .. subfig::
+
+      Al ejecutarse ``update(r0, null)``, se comienza por visitar la celda
+      ``h1``.
+
+      .. digraph:: g3_2
+
+         margin = 0;
+         ratio  = fill;
+         size   = "1.9,2.6";

          edge [ color = gray40 ];
          node [
             shape     = record,
          edge [ color = gray40 ];
          node [
             shape     = record,


@@ -849,12 +898,12 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el
                fontcolor = black,
             ];
 
                fontcolor = black,
             ];
 

-            h1 [ label = "h1\n1|<l> left|<r> right" ];
-            h2 [ label = "h2\n2|<l> left|<r> right" ];
-            h3 [ label = "h3\n2|<l> left|<r> right" ];
-            h4 [ label = "h4\n1|<l> left|<r> right" ];
-            h5 [ label = "h5\n1|<l> left|<r> right" ];
-            h6 [ label = "h6\n1|<l> left|<r> right" ];
+            h1 [ label = "h1\n1|<l> l|<r> r" ];
+            h2 [ label = "h2\n2|<l> l|<r> r" ];
+            h3 [ label = "h3\n2|<l> l|<r> r" ];
+            h4 [ label = "h4\n1|<l> l|<r> r" ];
+            h5 [ label = "h5\n1|<l> l|<r> r" ];
+            h6 [ label = "h6\n1|<l> l|<r> r" ];

 
             root:r0 -> h1 [ style = bold, color = black ];
             root:r1 -> h3;
 
             root:r0 -> h1 [ style = bold, color = black ];
             root:r1 -> h3;


@@ -869,15 +918,14 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el
 
    .. subfig::
 
 
    .. subfig::
 

-      Se decrementa el contador de ``h1`` y éste queda en 0 (indicando
-      que es basura). Esto desencadena la eliminación de las referencias
-      ``h1.left`` y ``h1.right``.
+      Se decrementa el contador de ``h1`` quedando en 0 (pasa a ser
+      *basura*). Se elimina primero ``h1.l`` y luego ``h1.r``.

 
 

-      .. digraph:: g3_2
+      .. digraph:: g3_3

 
          margin = 0;
          ratio  = fill;
 
          margin = 0;
          ratio  = fill;

-         size   = "3.0,3.8";
+         size   = "1.9,2.6";

          edge [ color = gray40 ];
          node [
             shape     = record,
          edge [ color = gray40 ];
          node [
             shape     = record,


@@ -902,12 +950,12 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el
                h1;
             };
 
                h1;
             };
 

-            h1 [ label = "h1\n0|<l> left|<r> right" ];
-            h2 [ label = "h2\n2|<l> left|<r> right" ];
-            h3 [ label = "h3\n2|<l> left|<r> right" ];
-            h4 [ label = "h4\n1|<l> left|<r> right" ];
-            h5 [ label = "h5\n1|<l> left|<r> right" ];
-            h6 [ label = "h6\n1|<l> left|<r> right" ];
+            h1 [ label = "h1\n0|<l> l|<r> r" ];
+            h2 [ label = "h2\n2|<l> l|<r> r" ];
+            h3 [ label = "h3\n2|<l> l|<r> r" ];
+            h4 [ label = "h4\n1|<l> l|<r> r" ];
+            h5 [ label = "h5\n1|<l> l|<r> r" ];
+            h6 [ label = "h6\n1|<l> l|<r> r" ];

 
             root:r0 -> h1 [ style = invis ];
             root:r1 -> h3;
 
             root:r0 -> h1 [ style = invis ];
             root:r1 -> h3;


@@ -920,21 +968,21 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el
 
          }
 
 
          }
 

+

 .. fig:: fig:gc-rc-rm-2
 
    Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 2).
 
    .. subfig::
 
 .. fig:: fig:gc-rc-rm-2
 
    Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 2).
 
    .. subfig::
 

-      Se decrementa el contador de ``h2`` pero no queda en 0, por lo
-      tanto no es necesario descender a sus hijas; se continúa con
-      ``h3``.
+      Se decrementa el contador de ``h2`` pero no queda en 0 (permanece en
+      el *live set*).

 
 

-      .. digraph:: g3_3
+      .. digraph:: g3_4

 
          margin = 0;
          ratio  = fill;
 
          margin = 0;
          ratio  = fill;

-         size   = "3.0,3.8";
+         size   = "1.9,2.6";

          edge [ color = gray40 ];
          node [
             shape     = record,
          edge [ color = gray40 ];
          node [
             shape     = record,


@@ -959,12 +1007,12 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el
                h1;
             };
 
                h1;
             };
 

-            h1 [ label = "h1\n0|<l> left|<r> right" ];
-            h2 [ label = "h2\n1|<l> left|<r> right" ];
-            h3 [ label = "h3\n2|<l> left|<r> right" ];
-            h4 [ label = "h4\n1|<l> left|<r> right" ];
-            h5 [ label = "h5\n1|<l> left|<r> right" ];
-            h6 [ label = "h6\n1|<l> left|<r> right" ];
+            h1 [ label = "h1\n0|<l> l|<r> r" ];
+            h2 [ label = "h2\n1|<l> l|<r> r" ];
+            h3 [ label = "h3\n2|<l> l|<r> r" ];
+            h4 [ label = "h4\n1|<l> l|<r> r" ];
+            h5 [ label = "h5\n1|<l> l|<r> r" ];
+            h6 [ label = "h6\n1|<l> l|<r> r" ];

 
             root:r0 -> h1 [ style = invis ];
             root:r1 -> h3;
 
             root:r0 -> h1 [ style = invis ];
             root:r1 -> h3;


@@ -979,14 +1027,13 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el
 
    .. subfig::
 
 
    .. subfig::
 

-      El contador de ``h3`` tampoco queda en 0; no hay necesidad de
-      descender a sus hijas y finaliza el proceso.
+      El contador de ``h3`` tampoco queda en 0, sigue en el *live set*.

 
 

-      .. digraph:: g3_4
+      .. digraph:: g3_5

 
          margin = 0;
          ratio  = fill;
 
          margin = 0;
          ratio  = fill;

-         size   = "3.0,3.8";
+         size   = "1.9,2.6";

          edge [ color = gray40 ];
          node [
             shape     = record,
          edge [ color = gray40 ];
          node [
             shape     = record,


@@ -1011,12 +1058,12 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el
                h1;
             };
 
                h1;
             };
 

-            h1 [ label = "h1\n0|<l> left|<r> right" ];
-            h2 [ label = "h2\n1|<l> left|<r> right" ];
-            h3 [ label = "h3\n1|<l> left|<r> right" ];
-            h4 [ label = "h4\n1|<l> left|<r> right" ];
-            h5 [ label = "h5\n1|<l> left|<r> right" ];
-            h6 [ label = "h6\n1|<l> left|<r> right" ];
+            h1 [ label = "h1\n0|<l> l|<r> r" ];
+            h2 [ label = "h2\n1|<l> l|<r> r" ];
+            h3 [ label = "h3\n1|<l> l|<r> r" ];
+            h4 [ label = "h4\n1|<l> l|<r> r" ];
+            h5 [ label = "h5\n1|<l> l|<r> r" ];
+            h6 [ label = "h6\n1|<l> l|<r> r" ];

 
             root:r0 -> h1 [ style = invis ];
             root:r1 -> h3;
 
             root:r0 -> h1 [ style = invis ];
             root:r1 -> h3;


@@ -1031,31 +1078,31 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el
 
 
 Luego se cambia una referencia (en vez de eliminarse) realizándose la
 
 
 Luego se cambia una referencia (en vez de eliminarse) realizándose la

-operación ``update(h3.left, h5)``. Para esto primero se incrementa el
-contador de referencias de ``h5`` para evitar confundirlo accidentalmente
-con *basura* (figura :vref:`fig:gc-rc-up-1`). Luego se procede
-a decrementar el contador de ``h2`` que queda en 0 (transformándose en
-*basura*) y lo mismo pasa cuando se desciende a ``h4`` (figura
-:vref:`fig:gc-rc-up-2`). Finalmente se decrementa el contador de ``h5``
-pero como esta celda va a ser apuntada por ``h3`` (por la operación que
-está ejecutándose) sobrevive y permanece en el *live set*.  Finalmente se
-termina de actualizar la referencia ``h3.left`` para que apunte a ``h5``
-(figura :vref:`fig:gc-rc-up-3`).
+operación ``update(h3.l, h5)``. Para esto primero se incrementa el contador
+de referencias de ``h5`` para evitar confundirlo accidentalmente con
+*basura* si se elimina alguna celda que apuntaba a ésta. Luego se procede
+a decrementar el contador de ``h2`` que queda en 0, transformándose en
+*basura* (figura :vref:`fig:gc-rc-up-1`). Lo mismo pasa cuando se desciende
+a ``h4``, pero al descender a ``h5`` y decrementar el contador, éste sigue
+siendo mayor que 0 (pues ``h3`` va a apuntar a ``h5``) así que permanece en
+el *live set*. Finalmente se termina de actualizar la referencia ``h3.l``
+para que apunte a ``h5`` (figura :vref:`fig:gc-rc-up-3`).

 
 
 .. fig:: fig:gc-rc-up-1
 
 
 
 .. fig:: fig:gc-rc-up-1
 

-   TODO Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 1).
+   Cambio en la referencia ``h2.l`` :math:`\to` ``h2`` a ``h2.l``
+   :math:`\to` ``h5`` (parte 1).

 
    .. subfig::
 
 
    .. subfig::
 

-      TODO
+      Comienza ``update(h3.l, h5)``, se incrementa el contador de ``h5``.

 
       .. digraph:: g4_1
 
          margin = 0;
          ratio  = fill;
 
       .. digraph:: g4_1
 
          margin = 0;
          ratio  = fill;

-         size   = "3.0,3.8";
+         size   = "1.9,2.6";

          edge [ color = gray40 ];
          node [
             shape     = record,
          edge [ color = gray40 ];
          node [
             shape     = record,


@@ -1080,12 +1127,12 @@ termina de actualizar la referencia ``h3.left`` para que apunte a ``h5``
                h1;
             };
 
                h1;
             };
 

-            h1 [ label = "h1\n0|<l> left|<r> right" ];
-            h2 [ label = "h2\n1|<l> left|<r> right" ];
-            h3 [ label = "h3\n1|<l> left\n*|<r> right" ];
-            h4 [ label = "h4\n1|<l> left|<r> right" ];
-            h5 [ label = "h5\n1|<l> left|<r> right" ];
-            h6 [ label = "h6\n1|<l> left|<r> right" ];
+            h1 [ label = "h1\n0|<l> l|<r> r" ];
+            h2 [ label = "h2\n1|<l> l|<r> r" ];
+            h3 [ label = "h3\n1|<l> l\n*|<r> r" ];
+            h4 [ label = "h4\n1|<l> l|<r> r" ];
+            h5 [ label = "h5\n2|<l> l|<r> r" ];
+            h6 [ label = "h6\n1|<l> l|<r> r" ];

 
             root:r0 -> h1 [ style = invis ];
             h1:l -> h2 [ style = invis ];
 
             root:r0 -> h1 [ style = invis ];
             h1:l -> h2 [ style = invis ];


@@ -1093,20 +1140,21 @@ termina de actualizar la referencia ``h3.left`` para que apunte a ``h5``
             root:r1 -> h3;
             h2:l -> h4;
             h2:r -> h5;
             root:r1 -> h3;
             h2:l -> h4;
             h2:r -> h5;

-            h3:l -> h2 [ style = bold, color = black ];
+            h3:l -> h2;
+            h3:l -> h5 [ style = dotted, color = black ];

             h3:r -> h6;
 
          }
 
    .. subfig::
 
             h3:r -> h6;
 
          }
 
    .. subfig::
 

-      TODO
+      Luego se procede a visitar las hijas de ``h3``, comenzando por ``h2``.

 
       .. digraph:: g4_2
 
          margin = 0;
          ratio  = fill;
 
       .. digraph:: g4_2
 
          margin = 0;
          ratio  = fill;

-         size   = "3.0,3.8";
+         size   = "1.9,2.6";

          edge [ color = gray40 ];
          node [
             shape     = record,
          edge [ color = gray40 ];
          node [
             shape     = record,


@@ -1131,12 +1179,12 @@ termina de actualizar la referencia ``h3.left`` para que apunte a ``h5``
                h1;
             };
 
                h1;
             };
 

-            h1 [ label = "h1\n0|<l> left|<r> right" ];
-            h2 [ label = "h2\n1|<l> left|<r> right" ];
-            h3 [ label = "h3\n1|<l> left\n*|<r> right" ];
-            h4 [ label = "h4\n1|<l> left|<r> right" ];
-            h5 [ label = "h5\n2|<l> left|<r> right" ];
-            h6 [ label = "h6\n1|<l> left|<r> right" ];
+            h1 [ label = "h1\n0|<l> l|<r> r" ];
+            h2 [ label = "h2\n1|<l> l|<r> r" ];
+            h3 [ label = "h3\n1|<l> l\n*|<r> r" ];
+            h4 [ label = "h4\n1|<l> l|<r> r" ];
+            h5 [ label = "h5\n2|<l> l|<r> r" ];
+            h6 [ label = "h6\n1|<l> l|<r> r" ];

 
             root:r0 -> h1 [ style = invis ];
             h1:l -> h2 [ style = invis ];
 
             root:r0 -> h1 [ style = invis ];
             h1:l -> h2 [ style = invis ];


@@ -1150,19 +1198,16 @@ termina de actualizar la referencia ``h3.left`` para que apunte a ``h5``
 
          }
 
 
          }
 

-.. fig:: fig:gc-rc-up-2
-
-   TODO Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 2).
-

    .. subfig::
 
    .. subfig::
 

-      TODO
+      Se decrementa el contador de ``h2`` y queda en 0 (pasa a ser
+      *basura*). Se eliminan las referencias a las hijas.

 
       .. digraph:: g4_3
 
          margin = 0;
          ratio  = fill;
 
       .. digraph:: g4_3
 
          margin = 0;
          ratio  = fill;

-         size   = "3.0,3.8";
+         size   = "1.9,2.6";

          edge [ color = gray40 ];
          node [
             shape     = record,
          edge [ color = gray40 ];
          node [
             shape     = record,


@@ -1187,12 +1232,12 @@ termina de actualizar la referencia ``h3.left`` para que apunte a ``h5``
                h1; h2;
             };
 
                h1; h2;
             };
 

-            h1 [ label = "h1\n0|<l> left|<r> right" ];
-            h2 [ label = "h2\n0|<l> left|<r> right" ];
-            h3 [ label = "h3\n1|<l> left\n*|<r> right" ];
-            h4 [ label = "h4\n1|<l> left|<r> right" ];
-            h5 [ label = "h5\n2|<l> left|<r> right" ];
-            h6 [ label = "h6\n1|<l> left|<r> right" ];
+            h1 [ label = "h1\n0|<l> l|<r> r" ];
+            h2 [ label = "h2\n1|<l> l|<r> r" ];
+            h3 [ label = "h3\n1|<l> l\n*|<r> r" ];
+            h4 [ label = "h4\n1|<l> l|<r> r" ];
+            h5 [ label = "h5\n2|<l> l|<r> r" ];
+            h6 [ label = "h6\n1|<l> l|<r> r" ];

 
             root:r0 -> h1 [ style = invis ];
             h1:l -> h2 [ style = invis ];
 
             root:r0 -> h1 [ style = invis ];
             h1:l -> h2 [ style = invis ];


@@ -1206,15 +1251,22 @@ termina de actualizar la referencia ``h3.left`` para que apunte a ``h5``
 
          }
 
 
          }
 

+
+.. fig:: fig:gc-rc-up-2
+
+   Cambio en la referencia ``h2.l`` :math:`\to` ``h2`` a ``h2.l``
+   :math:`\to` ``h5`` (parte 2).
+

    .. subfig::
 
    .. subfig::
 

-      TODO
+      Se decrementa el contador de ``h4`` quedando en 0, pasa a ser
+      *basura*. Se continúa con ``h5``.

 
       .. digraph:: g4_4
 
          margin = 0;
          ratio  = fill;
 
       .. digraph:: g4_4
 
          margin = 0;
          ratio  = fill;

-         size   = "3.0,3.8";
+         size   = "1.9,2.6";

          edge [ color = gray40 ];
          node [
             shape     = record,
          edge [ color = gray40 ];
          node [
             shape     = record,


@@ -1239,12 +1291,12 @@ termina de actualizar la referencia ``h3.left`` para que apunte a ``h5``
                h1; h2; h4;
             };
 
                h1; h2; h4;
             };
 

-            h1 [ label = "h1\n0|<l> left|<r> right" ];
-            h2 [ label = "h2\n0|<l> left|<r> right" ];
-            h3 [ label = "h3\n1|<l> left\n*|<r> right" ];
-            h4 [ label = "h4\n0|<l> left|<r> right" ];
-            h5 [ label = "h5\n2|<l> left|<r> right" ];
-            h6 [ label = "h6\n1|<l> left|<r> right" ];
+            h1 [ label = "h1\n0|<l> l|<r> r" ];
+            h2 [ label = "h2\n1|<l> l|<r> r" ];
+            h3 [ label = "h3\n1|<l> l\n*|<r> r" ];
+            h4 [ label = "h4\n0|<l> l|<r> r" ];
+            h5 [ label = "h5\n2|<l> l|<r> r" ];
+            h6 [ label = "h6\n1|<l> l|<r> r" ];

 
             root:r0 -> h1 [ style = invis ];
             h1:l -> h2 [ style = invis ];
 
             root:r0 -> h1 [ style = invis ];
             h1:l -> h2 [ style = invis ];


@@ -1258,19 +1310,15 @@ termina de actualizar la referencia ``h3.left`` para que apunte a ``h5``
 
          }
 
 
          }
 

-.. fig:: fig:gc-rc-up-3
-
-   TODO Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 3).
-

    .. subfig::
 
    .. subfig::
 

-      TODO
+      Se decrementa el contador de ``h5`` pero sigue siendo mayor que 0.

 
       .. digraph:: g4_5
 
          margin = 0;
          ratio  = fill;
 
       .. digraph:: g4_5
 
          margin = 0;
          ratio  = fill;

-         size   = "3.0,3.8";
+         size   = "1.9,2.6";

          edge [ color = gray40 ];
          node [
             shape     = record,
          edge [ color = gray40 ];
          node [
             shape     = record,


@@ -1295,12 +1343,12 @@ termina de actualizar la referencia ``h3.left`` para que apunte a ``h5``
                h1; h2; h4;
             };
 
                h1; h2; h4;
             };
 

-            h1 [ label = "h1\n0|<l> left|<r> right" ];
-            h2 [ label = "h2\n0|<l> left|<r> right" ];
-            h3 [ label = "h3\n1|<l> left\n*|<r> right" ];
-            h4 [ label = "h4\n0|<l> left|<r> right" ];
-            h5 [ label = "h5\n1|<l> left|<r> right" ];
-            h6 [ label = "h6\n1|<l> left|<r> right" ];
+            h1 [ label = "h1\n0|<l> l|<r> r" ];
+            h2 [ label = "h2\n1|<l> l|<r> r" ];
+            h3 [ label = "h3\n1|<l> l\n*|<r> r" ];
+            h4 [ label = "h4\n0|<l> l|<r> r" ];
+            h5 [ label = "h5\n1|<l> l|<r> r" ];
+            h6 [ label = "h6\n1|<l> l|<r> r" ];

 
             root:r0 -> h1 [ style = invis ];
             h1:l -> h2 [ style = invis ];
 
             root:r0 -> h1 [ style = invis ];
             h1:l -> h2 [ style = invis ];


@@ -1316,13 +1364,14 @@ termina de actualizar la referencia ``h3.left`` para que apunte a ``h5``
 
    .. subfig::
 
 
    .. subfig::
 

-      TODO
+      Se termina por actualizar la referencia de ``h3.l`` para que apunte
+      a ``h5``.

 
       .. digraph:: g4_6
 
          margin = 0;
          ratio  = fill;
 
       .. digraph:: g4_6
 
          margin = 0;
          ratio  = fill;

-         size   = "3.0,3.8";
+         size   = "1.9,2.6";

          edge [ color = gray40 ];
          node [
             shape     = record,
          edge [ color = gray40 ];
          node [
             shape     = record,


@@ -1347,13 +1396,13 @@ termina de actualizar la referencia ``h3.left`` para que apunte a ``h5``
                h1; h2; h4;
             };
 
                h1; h2; h4;
             };
 

-            h1 [ label = "h1\n0|<l> left|<r> right" ];
-            h1 [ label = "h1\n0|<l> left|<r> right" ];
-            h2 [ label = "h2\n0|<l> left|<r> right" ];
-            h3 [ label = "h3\n1|<l> left|<r> right" ];
-            h4 [ label = "h4\n0|<l> left|<r> right" ];
-            h5 [ label = "h5\n1|<l> left|<r> right" ];
-            h6 [ label = "h6\n1|<l> left|<r> right" ];
+            h1 [ label = "h1\n0|<l> l|<r> r" ];
+            h1 [ label = "h1\n0|<l> l|<r> r" ];
+            h2 [ label = "h2\n0|<l> l|<r> r" ];
+            h3 [ label = "h3\n1|<l> l|<r> r" ];
+            h4 [ label = "h4\n0|<l> l|<r> r" ];
+            h5 [ label = "h5\n1|<l> l|<r> r" ];
+            h6 [ label = "h6\n1|<l> l|<r> r" ];

 
             root:r0 -> h1 [ style = invis ];
             h1:l -> h2 [ style = invis ];
 
             root:r0 -> h1 [ style = invis ];
             h1:l -> h2 [ style = invis ];