\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{a4wide}

\usepackage{tikz}
\usetikzlibrary{shapes}

\begin{document}

\section*{Exercise 12.1}
\begin{tikzpicture}
  \begin{scope}
    \node (0) at (0,0) {MAX};
    \node (1) at (0,-1) {MIN};
    \node (2) at (0,-2) {MAX};
    \node (3) at (0,-3) {MIN};
    \node (4) at (0,-4) {MAX};
  \end{scope}
  \begin{scope}[
    xshift=6.5cm,
    level distance=1cm,
    level 1/.style={sibling distance = 6.5cm},
    level 2/.style={sibling distance = 3.5cm},
    level 3/.style={sibling distance = 3.2cm},
    level 4/.style={sibling distance = 1.3cm},
    level 5/.style={sibling distance = 0.5cm},
    every node/.style = {
      font={\fontsize{8pt}{12}\selectfont}
      },
    max/.style = {regular polygon, regular polygon sides=3, draw, inner
    sep=1.5pt},
    min/.style = {max, shape border rotate=180},
    terminal/.style = {circle, draw, minimum size=0.3cm}
    ]


    \node[max] (a) {}
      child { node[min] (b1) {}
        child { node[max] (c11) {}
          child { node[min] (d111) {}
            child { node[max] (e1111) {}
              child { node[terminal] (f11111) {}}
              child { node[terminal] (f11112) {}}
            }
            child { node[max] (e1112) {}
              child { node[terminal] (f11121) {}}
              child { node[terminal] (f11122) {}}
            }
          }
          child { node[min] (d112) {}
            child { node[max] (e1121) {}
              child { node[terminal] (f11211) {}}
            }
            child { node[max] (e1122) {}
              child { node[terminal] (f11221) {}}
              child { node[terminal] (f11222) {}}
            }
            child { node[max] (e1123) {}
              child { node[terminal] (f11231) {}}
              child { node[terminal] (f11232) {}}
            }
          }
        }
      }
      child { node[min] (b2) {}
        child { node[max] (c21) {}
          child { node[min] (d211) {}
            child { node[max] (e2111) {}
              child { node[terminal] (f21111) {}}
            }
            child { node[max] (e2112) {}
              child { node[terminal] (f21121) {}}
              child { node[terminal] (f21122) {}}
            }
          }
        }
        child { node[max] (c22) {}
          child { node[min] (d221) {}
            child { node[max] (e2211) {}
              child { node[terminal] (f22111) {}}
              child { node[terminal] (f22112) {}}
            }
          }
          child { node[min] (d222) {}
            child { node[max] (e2221) {}
              child { node[terminal] (f22211) {}}
              child { node[terminal] (f22212) {}}
              child { node[terminal] (f22213) {}}
              child { node[terminal] (f22214) {}}
            }
          }
        }
      };
    \node[below of=f11111, node distance=3mm] {$5$};
    \node[below of=f11112, node distance=3mm] {$4$};
    \node[below of=f11121, node distance=3mm] {$6$};
    \node[below of=f11122, node distance=3mm] {$7$};
    \node[below of=f11211, node distance=3mm] {$4$};
    \node[below of=f11221, node distance=3mm] {$5$};
    \node[below of=f11222, node distance=3mm] {$3$};
    \node[below of=f11231, node distance=3mm] {$9$};
    \node[below of=f11232, node distance=3mm] {$8$};
    \node[below of=f21111, node distance=3mm] {$9$};
    \node[below of=f21121, node distance=3mm] {$6$};
    \node[below of=f21122, node distance=3mm] {$2$};
    \node[below of=f22111, node distance=3mm] {$4$};
    \node[below of=f22112, node distance=3mm] {$8$};
    \node[below of=f22211, node distance=3mm] {$3$};
    \node[below of=f22212, node distance=3mm] {$8$};
    \node[below of=f22213, node distance=3mm] {$7$};
    \node[below of=f22214, node distance=3mm] {$5$};
  \end{scope}
\end{tikzpicture}


\section*{Exercise 12.2}
\begin{tikzpicture}
  \begin{scope}
    \node (0) at (0,0) {MAX};
    \node (1) at (0,-1) {MIN};
    \node (2) at (0,-2) {MAX};
    \node (3) at (0,-3) {MIN};
  \end{scope}
  \begin{scope}[
    xshift=7.5cm,
    level distance=1cm,
    level 1/.style={sibling distance = 5cm},
    level 2/.style={sibling distance = 2cm},
    level 3/.style={sibling distance = 1.2cm},
    level 4/.style={sibling distance = 0.4cm},
    every node/.style = {
      font={\fontsize{8pt}{12}\selectfont}
      },
    max/.style = {regular polygon, regular polygon sides=3, draw, inner
    sep=1.5pt},
    min/.style = {max, shape border rotate=180},
    terminal/.style = {circle, draw, minimum size=0.3cm},
    invisible/.style={opacity=0.4}
    ]

    \node[max] (a) {}
      child { node[min] (b1) {}
        child { node[max] (c11) {}
          child { node[min] (d111) {}
            child { node[terminal] (e1111) {}}
            child { node[terminal] (e1112) {}}
          }
          child { node[min] (d112) {}
            child { node[terminal] (e1121) {}}
            child { node[terminal] (e1122) {}}
            child { node[terminal] (e1123) {}}
          }
        }
        child { node[max] (c12) {}
          child { node[min] (d121) {}
            child { node[terminal] (e1211) {}}
            child { node[terminal] (e1212) {}}
          }
        }
      }
      child { node[min] (b2) {}
        child { node[max] (c21) {}
          child { node[min] (d211) {}
            child { node[terminal] (e2111) {}}
            child { node[terminal] (e2112) {}}
          }
          child { node[min] (d212) {}
            child { node[terminal] (e2121) {}}
            child[invisible] { node[terminal] (e2122) {}}
          }
        }
        child[invisible] { node[max] (c22) {}
          child { node[min] (d221) {}
            child { node[terminal] (e2211) {}}
            child { node[terminal] (e2212) {}}
          }
        }
        child[invisible] { node[max] (c23) {}
          child { node[min] (d231) {}
            child { node[terminal] (e2311) {}}
            child { node[terminal] (e2312) {}}
          }
          child { node[min] (d232) {}
            child { node[terminal] (e2321) {}}
            child { node[terminal] (e2322) {}}
            child { node[terminal] (e2323) {}}
          }
        }
      }
      child { node[min] (b3) {}
        child { node[max] (c31) {}
          child { node[min] (d311) {}
            child { node[terminal] (e3111) {}}
            child[invisible] { node[terminal] (e3112) {}}
          }
          child { node[min] (d312) {}
            child { node[terminal] (e3121) {}}
          }
          child { node[min] (d313) {}
            child { node[terminal] (e3131) {}}
            child[invisible] { node[terminal] (e3132) {}}
          }
        }
      };
    \node[below of=e1111, node distance=3mm] {$1$};
    \node[below of=e1112, node distance=3mm] {$7$};
    \node[below of=e1121, node distance=3mm] {$8$};
    \node[below of=e1122, node distance=3mm] {$9$};
    \node[below of=e1123, node distance=3mm] {$8$};
    \node[below of=e1211, node distance=3mm] {$3$};
    \node[below of=e1212, node distance=3mm] {$8$};
    \node[below of=e2111, node distance=3mm] {$6$};
    \node[below of=e2112, node distance=3mm] {$1$};
    \node[below of=e2121, node distance=3mm] {$0$};
    \node[invisible, below of=e2122, node distance=3mm] {$2$};
    \node[invisible, below of=e2211, node distance=3mm] {$6$};
    \node[invisible, below of=e2212, node distance=3mm] {$3$};
    \node[invisible, below of=e2311, node distance=3mm] {$7$};
    \node[invisible, below of=e2312, node distance=3mm] {$7$};
    \node[invisible, below of=e2321, node distance=3mm] {$0$};
    \node[invisible, below of=e2322, node distance=3mm] {$7$};
    \node[invisible, below of=e2323, node distance=3mm] {$3$};
    \node[below of=e3111, node distance=3mm] {$2$};
    \node[invisible, below of=e3112, node distance=3mm] {$8$};
    \node[below of=e3121, node distance=3mm] {$6$};
    \node[below of=e3131, node distance=3mm] {$3$};
    \node[invisible, below of=e3132, node distance=3mm] {$5$};

    \node[above of=d111, node distance=3mm] {$1[-\infty,1]$};
    \node[above right of=d112, node distance=4mm] {$8[1,8]$};
    \node[right of=c11, node distance=7mm] {$8[8,\infty]$};
    \node[above right of=d121, node distance=4mm] {$3[-\infty,3]$};
    \node[right of=c12, node distance=6mm] {$3[3,8]$};
    \node[above of=b1, node distance=3mm] {$3[-\infty,3]$};

    \node[right of=d211, node distance=5mm] {$1[3,6]$};
    \node[right of=d212, node distance=6mm] {$0[3,\infty]$};
    \node[right of=c21, node distance=7mm] {$1[3,\infty]$};
    \node[right of=b2, node distance=7mm] {$1[3,\infty]$};

    \node[right of=d311, node distance=6mm] {$2[3,\infty]$};
    \node[right of=d312, node distance=6mm] {$6[3,6]$};
    \node[right of=d313, node distance=6mm] {$3[6,\infty]$};
    \node[right of=c31, node distance=7mm] {$6[6,\infty]$};
    \node[right of=b3, node distance=7mm] {$6[3,6]$};
    \node[above of=a, node distance=3mm] {$6[6,\infty]$};
  \end{scope}
\end{tikzpicture}

\section*{Exercise 12.3}
  \begin{tikzpicture}
    \begin{scope}
      \node (0) at (0,0) {P1};
      \node (1) at (0,-1) {P2};
      \node (2) at (0,-2) {P3};
    \end{scope}
    \begin{scope}[
      xshift=6cm,
      level distance=1cm,
      level 1/.style={sibling distance = 6cm},
      level 2/.style={sibling distance = 3cm},
      level 3/.style={sibling distance = 1.5cm},
      ]
      \node {}
        child { node {}
          child { node {}
            child { node {(3,5,1)} }
            child { node {(8,2,2)} }
          }
          child { node {}
            child { node {(2,6,4)} }
            child { node {(0,5,8)} }
          }
        }
        child { node {}
          child { node {}
            child { node {(3,3,3)} }
            child { node {(7,9,1)} }
          }
          child { node {}
            child { node {(4,7,4)} }
            child { node {(2,4,0)} }
          }
        }
      ;
    \end{scope}
  \end{tikzpicture}

\end{document}
