<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 2-3 Trees
This notebook contains the code to visualize 2-3 trees.
Step1:  This notebook presents 2-3 trees.  We define these trees inductively as follows
Step2:  The function make_string is a helper function used to shorten the implementation of __str__.
  - obj is the object that is to be rendered as a string
  - attributes is a list of those member variables that are used to produce the string
Step3:  The method $t.\texttt{toDot}()$ takes a 2-3-4 tree $t$ and returns a graph that depicts the tree $t$.
Step4:  The method $t.\texttt{collectIDs}(d)$ takes a tree $t$ and a dictionary $d$ and updates the dictionary so that the following holds
Step5:  The function $\texttt{toDotList}(\texttt{NodeList})$ takes a list of trees and displays them one by one.
Step6:  The class Tree is not used in the implementation of 2-3 trees.  It is only used for displaying abstract subtrees in equations.
It is displayed as a triangle containing the string that is stored in the member variable mName.
Step7:  The class Method is not used in the implementation of 2-3 trees. It is only used for displaying method calls in equations. It is displayed as a rectangle containing the string that is stored in the member variable mLabel.
Step8:  The class Nil represents an empty tree.  It has no member variables of its own.
Step9:  The class Onerepresents a 1-node.  These are nodes without a key that have only a single child.
Step10:  Graphically, the node $\texttt{One}(t)$ is represented as shown below
Step11:  The class Two represents a 2-node of the form $\texttt{Two}(l, k, r)$.  It manages three member variables
Step12:  Graphically, the node $\texttt{Two}(l, k, r)$ is represented as shown below
Step13:  The class Three represents a 3-node of the form $\texttt{Three}(l, k_L, m, k_R, r)$.  It manages 5 member variables
Step14:  Graphically, the node $\texttt{Three}(l, k_L, m, k_R, r)$ is represented as shown below
Step15:  The class Four represents a 4-node.  It manages 7 member variables
Step16:  Graphically, the node $\texttt{Four}(l, k_L, m_L, k_M, m_R, k_R, r)$ is represented as shown below
Step17:  Methods of the Class Nil
Insertings a key $k$ into an empty node returns a 2-node with two empty subtrees.
Step18:  Methods of the Class Two
The method extract returns the member variables stored in a 2-node.  This is usefull to shorten the code since when we use this method, we don't have to prefix all variable names with self..
The method $t.\texttt{ins}(k)$ takes a 2-3 tree $t$ and and a key $k$ and inserts the key $k$ into $t$.
It returns a 2-3-4 tree that has at most one 4-node, which has to be a child of the root
node.  The function $\texttt{ins}$ is recursive and uses the function $\texttt{restore}$ defined below. 
The most important invariant satisfied by the method call $t.\texttt{ins}(k)$ is the fact that the tree
$t.\texttt{ins}(k)$ has the same height as the tree $t$.
The different cases that need to be handled by ins are shown graphically below
Step19:  The function call $t.\texttt{restore}()$ takes a 2-3-4 tree $t$ that has at most one 4-node. This 4-node has to be a child
of the root.  It returns a 2-3-4 tree that has at most one 4-node.  This 4-node has to be the root node.
Graphically, it is specified as shown below.
Step20:  Methods of the Class Three
The function call $t.\texttt{restore}()$ takes a 2-3-4 tree $t$ that has at most one 4-node. This 4-node has to be a child
of the root.  It returns a 2-3-4 tree that has at most one 4-node.  This 4-node has to be the root node.
The most important invariant satisfied by the method call $t.\texttt{ins}(k)$ is the fact that the tree
$t.\texttt{ins}(k)$ has the same height as the tree $t$.
The different cases that need to be handled by ins are shown graphically below
Step21:  Methods of the Class Four
Step22:  Deletion
The method $t.\texttt{delete}(k)$ is specified as follows
Step23:  Finally, we specify the method shrink.  The only class where the implementation of shrink is nontrivial is the class One.
<ASSISTANT_TASK:>
Python Code:
import graphviz as gv
Explanation: 2-3 Trees
This notebook contains the code to visualize 2-3 trees.
End of explanation
class TwoThreeTree:
    sNodeCount = 0
    
    def __init__(self):
        TwoThreeTree.sNodeCount += 1
        self.mID = TwoThreeTree.sNodeCount
        
    def getID(self):
        return self.mID
        
    def isNil(self):
        return False
    
    def isOne(self):
        return False
    
    def isTwo(self):
        return False
    
    def isThree(self):
        return False
    
    def isFour(self):
        return False
    
    def isTree(self):
        return False
    
    def isMethod(self):
        return False
    
    def insert(self, k):
        return self._ins(k)._restore()._grow()
    
    def delete(self, k):
        return self._del(k)._repair()._shrink()
    
    def _grow(self):
        return self
    
    def _shrink(self):
        return self
Explanation: This notebook presents 2-3 trees.  We define these trees inductively as follows:
  - $\texttt{Nil}$ is a 2-3 tree that represents the empty set.
  - $\texttt{Two}(l, k, r)$ is a 2-3 tree provided that
      - $l$ is a 2-3 tree,
      - $k$ is a key,
      - $r$ is a 2-3 tree,
      - all keys stored in $l$ are less than k and all keys stored in $r$ are bigger than $k$, that is we have
        $$ l < k < r. $$
      - $l$ and $r$ have the same height.
      A node of the form  $\texttt{Two}(l, k, r)$ is called a 2-node.  Except for the fact
      that there is no value, a 2-node is
      interpreted in the same way as we have interpreted the term $\texttt{Node}(k, v, l, r)$.
  - $\texttt{Three}(l, k_l, m, k_r, r)$ is a 2-3 tree provided
      - $l$, $m$, and $r$ are 2-3 trees,
      - $k_l$ and $k_r$ are keys,
      - $l < k_l < m < k_r < r$,
      - $l$, $m$, and $r$ have the same height.
      A node of the form  $\texttt{Three}(l, k_l, m, k_r, r)$ is called a 3-node. 
In order to keep 2-3 trees balanced when inserting new keys we use a fourth constructor of the form
$\texttt{Four}(l,k_1,m_l, k_2, m_r, k_3, r)$.
A term of the form $\texttt{Four}(l,k_1,m_l, k_2, m_r, k_3, r)$ is a 2-3-4 tree iff
  - $l$, $m_l$, $m_r$, and $r$ are 2-3 trees,
  - $k_l$, $k_m$, and $k_r$ are keys,
  - $l < k_l < m_l < k_m < m_r < k_r < r$,
  - $l$, $m_l$, $m_r$, and $r$ all have the same height.
Nodes of this form are called 4-nodes and the key $k_m$ is called the middle key.
Trees containing 2-nodes, 3-node, and 4-nodes are called 2-3-4 trees.
In order to keep 2-3 trees balanced when deleting keys we use a fifth constructor of the form
$\texttt{One}(t)$.
A term of the form $\texttt{One}(t)$ is a 1-2-3 tree iff $t$ is a 2-3 tree.
The class TwoThreeTree is a superclass for constructing the nodes of 2-3-4 trees.  It has one static variable sNodeCount.  This variable is used to equip all nodes with a unique identifier.  This identifier is used to draw the trees using graphviz.
Every node has a uniques id mID that is stored as a member variable.  Furthermore, this class provides defaults for the functions isNil, isTwo, isThree, and isFour.  These functions can be used to check the type of a node.
End of explanation
def _make_string(self, attributes):
        # map the function __str__ to all attributes and join them with a comma
        name = self.__class__.__name__
        return f"{name}({', '.join(map(str, [getattr(self, at) for at in attributes]))})"
    
TwoThreeTree._make_string = _make_string
Explanation: The function make_string is a helper function used to shorten the implementation of __str__.
  - obj is the object that is to be rendered as a string
  - attributes is a list of those member variables that are used to produce the string
End of explanation
def toDot(self):
    dot = gv.Digraph(node_attr={'shape': 'record', 'style': 'rounded'})
    nodeDict = {}
    self._collectIDs(nodeDict)
    for n, t in nodeDict.items():
        if t.isNil():
            dot.node(str(n), label='', shape='point')
        elif t.isOne():
            dot.node(str(n), label='', shape='point')
        elif t.isTwo():
            dot.node(str(n), label=str(t.mKey))
        elif t.isThree():
            dot.node(str(n), label=str(t.mKeyL) + '|' + str(t.mKeyR))
        elif t.isFour():
            dot.node(str(n), label=str(t.mKeyL) + '|' + str(t.mKeyM) + '|' + str(t.mKeyR))
        elif t.isTree():
            dot.node(str(n), label=str(t.mName), shape='triangle')
        else:
            assert False, f'Unknown node {t}'
    for n, t in nodeDict.items():
        if t.isOne():
            dot.edge(str(n), str(t.mChild.getID()))
        if t.isTwo():
            dot.edge(str(n), str(t.mLeft .getID()))
            dot.edge(str(n), str(t.mRight.getID()))
        if t.isThree():
            dot.edge(str(n), str(t.mLeft  .getID()))
            dot.edge(str(n), str(t.mMiddle.getID()))
            dot.edge(str(n), str(t.mRight .getID()))
        if t.isFour():
            dot.edge(str(n), str(t.mLeft   .getID()))
            dot.edge(str(n), str(t.mMiddleL.getID()))
            dot.edge(str(n), str(t.mMiddleR.getID()))
            dot.edge(str(n), str(t.mRight  .getID()))
    return dot
TwoThreeTree.toDot = toDot
Explanation: The method $t.\texttt{toDot}()$ takes a 2-3-4 tree $t$ and returns a graph that depicts the tree $t$.
End of explanation
def _collectIDs(self, nodeDict):
    nodeDict[self.getID()] = self
    if self.isOne():
        self.mChild._collectIDs(nodeDict)
    elif self.isTwo():
        self.mLeft ._collectIDs(nodeDict)
        self.mRight._collectIDs(nodeDict)
    elif self.isThree():
        self.mLeft  ._collectIDs(nodeDict)
        self.mMiddle._collectIDs(nodeDict)
        self.mRight ._collectIDs(nodeDict)
    elif self.isFour():
        self.mLeft   ._collectIDs(nodeDict)
        self.mMiddleL._collectIDs(nodeDict)
        self.mMiddleR._collectIDs(nodeDict)
        self.mRight  ._collectIDs(nodeDict)
        
TwoThreeTree._collectIDs = _collectIDs
Explanation: The method $t.\texttt{collectIDs}(d)$ takes a tree $t$ and a dictionary $d$ and updates the dictionary so that the following holds:
$$ d[\texttt{id}] = n \quad \mbox{for every node $n$ in $t$.} $$
Here, $\texttt{id}$ is the unique identifier of the node $n$, i.e. $d$ associates the identifiers with the corresponding nodes.
End of explanation
def toDotList(NodeList):
    dot = gv.Digraph(node_attr={'shape': 'record', 'style': 'rounded'})
    nodeDict = {}
    for node in NodeList:
        node._collectIDs(nodeDict)
    for n, t in nodeDict.items():
        if t.isNil():
            dot.node(str(n), label='', shape='point')
        elif t.isOne():
            dot.node(str(n), label='', shape='point')
        elif t.isTwo():
            dot.node(str(n), label=str(t.mKey))
        elif t.isThree():
            dot.node(str(n), label=str(t.mKeyL) + '|' + str(t.mKeyR))
        elif t.isFour():
            dot.node(str(n), label=str(t.mKeyL) + '|' + str(t.mKeyM) + '|' + str(t.mKeyR))
        elif t.isTree():
            dot.node(str(n), label=str(t.mName), shape='triangle', style='solid')
        elif t.isMethod():
            dot.node(str(n), label=str(t.mLabel), shape='rectangle', style='dotted')
        else:
            assert False, f'toDotList: Unknown node {str(t)}'
    for n, t in nodeDict.items():
        if t.isOne():
            dot.edge(str(n), str(t.mChild.getID()))
        if t.isTwo():
            dot.edge(str(n), str(t.mLeft .getID()))
            dot.edge(str(n), str(t.mRight.getID()))
        if t.isThree():
            dot.edge(str(n), str(t.mLeft  .getID()))
            dot.edge(str(n), str(t.mMiddle.getID()))
            dot.edge(str(n), str(t.mRight .getID()))
        if t.isFour():
            dot.edge(str(n), str(t.mLeft   .getID()))
            dot.edge(str(n), str(t.mMiddleL.getID()))
            dot.edge(str(n), str(t.mMiddleR.getID()))
            dot.edge(str(n), str(t.mRight  .getID()))
    return dot
Explanation: The function $\texttt{toDotList}(\texttt{NodeList})$ takes a list of trees and displays them one by one.
End of explanation
class Tree(TwoThreeTree):
    def __init__(self, name):
        TwoThreeTree.__init__(self)
        self.mName = name
        
    def __str__(self):
        return self.mName
    
    def isTree(self):
        return True
Explanation: The class Tree is not used in the implementation of 2-3 trees.  It is only used for displaying abstract subtrees in equations.
It is displayed as a triangle containing the string that is stored in the member variable mName.
End of explanation
class Method(TwoThreeTree):
    def __init__(self, label):
        TwoThreeTree.__init__(self)
        self.mLabel = label
        
    def __str__(self):
        return self.mLabel
    
    def isMethod(self):
        return True
Explanation: The class Method is not used in the implementation of 2-3 trees. It is only used for displaying method calls in equations. It is displayed as a rectangle containing the string that is stored in the member variable mLabel.
End of explanation
class Nil(TwoThreeTree):
    def __init__(self):
        TwoThreeTree.__init__(self)
        
    def isNil(self):
        return True
    
    def __str__(self):
        return 'Nil()'
Explanation: The class Nil represents an empty tree.  It has no member variables of its own.
End of explanation
class One(TwoThreeTree):
    def __init__(self, child):
        TwoThreeTree.__init__(self)
        self.mChild = child
        
    def isOne(self):
        return True
    def __str__(self):
        return _make_string(self, ['mChild'])
Explanation: The class Onerepresents a 1-node.  These are nodes without a key that have only a single child.
End of explanation
toDotList([One(Tree('t'))])
Explanation: Graphically, the node $\texttt{One}(t)$ is represented as shown below:
End of explanation
class Two(TwoThreeTree):
    def __init__(self, left, key, right):
        TwoThreeTree.__init__(self)
        self.mLeft  = left
        self.mKey   = key
        self.mRight = right
        
    def isTwo(self):
        return True
    def __str__(self):
        return self._make_string(['mLeft', 'mKey', 'mRight'])
Explanation: The class Two represents a 2-node of the form $\texttt{Two}(l, k, r)$.  It manages three member variables:
  - mLeft  is the left subtree $l$,
  - mKey   is the key that is stored at this node,
  - mRight is the right subtree $r$.
End of explanation
toDotList([Two(Tree('l'), 'k', Tree('r'))])
Explanation: Graphically, the node $\texttt{Two}(l, k, r)$ is represented as shown below:
End of explanation
class Three(TwoThreeTree):
    def __init__(self, left, keyL, middle, keyR, right):
        TwoThreeTree.__init__(self)
        self.mLeft   = left
        self.mKeyL   = keyL
        self.mMiddle = middle
        self.mKeyR   = keyR
        self.mRight  = right
    def __str__(self):
        return self._make_string(['mLeft', 'mKeyL', 'mMiddle', 'mKeyR', 'mRight'])        
    def isThree(self):
        return True
Explanation: The class Three represents a 3-node of the form $\texttt{Three}(l, k_L, m, k_R, r)$.  It manages 5 member variables:
  - mLeft   is the left subtree $l$,
  - mKeyL   is the left key $k_L$,
  - mMiddle is the middle subtree $m$,
  - mKeyR   is the right key $k_r$,
  - mRight  is the right subtree.
End of explanation
toDotList([Three(Tree('l'), 'kL', Tree('m'), 'kR', Tree('r'))])
Explanation: Graphically, the node $\texttt{Three}(l, k_L, m, k_R, r)$ is represented as shown below:
End of explanation
class Four(TwoThreeTree):
    def __init__(self, l, kl, ml, km, mr, kr, r):
        TwoThreeTree.__init__(self)
        self.mLeft    = l
        self.mKeyL    = kl
        self.mMiddleL = ml
        self.mKeyM    = km
        self.mMiddleR = mr
        self.mKeyR    = kr
        self.mRight   = r
        
    def __str__(self):
        return self._make_string(['mLeft', 'mKeyL', 'mMiddleL', 'mKeyM', 'mMiddleR', 'mKeyR', 'mRight'])
    
    def isFour(self):
        return True
Explanation: The class Four represents a 4-node.  It manages 7 member variables:
  - mLeft    is the left subtree $l$,
  - mKeyL    is the left key $k_L$,
  - mMiddleL is the middle left subtree $m_L$,
  - mKeyM    is the middle key,
  - mMiddleR is the middle right subtree $m_R$,
  - mKeyR    is the right key $k_r$,
  - mRight   is the right subtree.
End of explanation
toDotList([Four(Tree('l'), 'kL', Tree('mL'), 'kM', Tree('mR'), 'kR', Tree('r'))])
Explanation: Graphically, the node $\texttt{Four}(l, k_L, m_L, k_M, m_R, k_R, r)$ is represented as shown below:
End of explanation
toDotList([Nil(), Method('insert(k)'), Two(Nil(), 'k', Nil())])
Explanation: Methods of the Class Nil
Insertings a key $k$ into an empty node returns a 2-node with two empty subtrees.
End of explanation
toDotList([Two(Tree('l'), 'k', Tree('r')), Method('.ins(k)'), Two(Tree('l'), 'k', Tree('r')) ])
toDotList([Method('k1 < k2:'), Two(Nil(), 'k1', Nil()), Method('.ins(k2)'), Three(Nil(), 'k1', Nil(), 'k2', Nil()) ])
toDotList([Method('k2 < k1:'), Two(Nil(), 'k1', Nil()), Method('.ins(k2)'), Three(Nil(), 'k2', Nil(), 'k1', Nil()) ])
toDotList([Method('k1 < k2:'), Two(Tree('l'), 'k1', Tree('r')), Method('.ins(k2)'), Two(Tree('l'), 'k1', Tree('r.ins(k2)')) ])
toDotList([Method('k2 < k1:'), Two(Tree('l'), 'k1', Tree('r')), Method('.ins(k2)'), Two(Tree('l.ins(k2)'), 'k1', Tree('r')) ])
Explanation: Methods of the Class Two
The method extract returns the member variables stored in a 2-node.  This is usefull to shorten the code since when we use this method, we don't have to prefix all variable names with self..
The method $t.\texttt{ins}(k)$ takes a 2-3 tree $t$ and and a key $k$ and inserts the key $k$ into $t$.
It returns a 2-3-4 tree that has at most one 4-node, which has to be a child of the root
node.  The function $\texttt{ins}$ is recursive and uses the function $\texttt{restore}$ defined below. 
The most important invariant satisfied by the method call $t.\texttt{ins}(k)$ is the fact that the tree
$t.\texttt{ins}(k)$ has the same height as the tree $t$.
The different cases that need to be handled by ins are shown graphically below:
End of explanation
toDotList([Two(Four(Tree('l1'),'kl',Tree('ml'),'km', Tree('mr'),'kr',Tree('r1')), 'k', Tree('r')), 
           Method('.restore()'), 
           Three(Two(Tree('l1'),'kl',Tree('ml')), 'km', Two(Tree('mr'),'kr',Tree('r1')), 'k', Tree('r'))])
toDotList([Two(Tree('l'), 'k', Four(Tree('l1'),'kl',Tree('ml'),'km', Tree('mr'),'kr',Tree('r1'))), 
           Method('.restore()'), 
           Three(Tree('l'), 'k', Two(Tree('l1'),'kl',Tree('ml')), 'km', Two(Tree('mr'),'kr',Tree('r1')))])
Explanation: The function call $t.\texttt{restore}()$ takes a 2-3-4 tree $t$ that has at most one 4-node. This 4-node has to be a child
of the root.  It returns a 2-3-4 tree that has at most one 4-node.  This 4-node has to be the root node.
Graphically, it is specified as shown below.
End of explanation
toDotList([Three(Four(Tree('l1'), 'k1', Tree('ml'), 'k2', Tree('mr'), 'k3', Tree('r1')), 'kl', Tree('m'), 'kr', Tree('r')),
           Method('.restore()'),
           Four(Two(Tree('l1'), 'k1', Tree('ml')), 'k2', Two(Tree('mr'), 'k3', Tree('r1')), 'kl', Tree('m'), 'kr', Tree('r')),
          ])
toDotList([Three(Tree('l'), 'kl', Four(Tree('l1'), 'k1', Tree('ml'), 'k2', Tree('mr'), 'k3', Tree('r1')), 'kr', Tree('r')),
           Method('.restore()'),
           Four(Tree('l'), 'kl', Two(Tree('l1'), 'k1', Tree('ml')), 'k2', Two(Tree('mr'), 'k3', Tree('r1')), 'kr', Tree('r'))
          ])
toDotList([Three(Tree('l'), 'kl', Tree('m'), 'kr', Four(Tree('l1'), 'k1', Tree('ml'), 'k2', Tree('mr'), 'k3', Tree('r1'))),
           Method('.restore()'),
           Four(Tree('l'), 'kl', Tree('m'), 'kr', Two(Tree('l1'), 'k1', Tree('ml')), 'k2', Two(Tree('mr'), 'k3', Tree('r1')))
          ])
Explanation: Methods of the Class Three
The function call $t.\texttt{restore}()$ takes a 2-3-4 tree $t$ that has at most one 4-node. This 4-node has to be a child
of the root.  It returns a 2-3-4 tree that has at most one 4-node.  This 4-node has to be the root node.
The most important invariant satisfied by the method call $t.\texttt{ins}(k)$ is the fact that the tree
$t.\texttt{ins}(k)$ has the same height as the tree $t$.
The different cases that need to be handled by ins are shown graphically below:
End of explanation
toDotList([Four(Tree('l'),'kl', Tree('ml'), 'km', Tree('mr'), 'kr', Tree('r')),
           Method('.grow()'),
           Two(Two(Tree('l'),'kl', Tree('ml')), 'km', Two(Tree('mr'), 'kr', Tree('r')))
          ])
Explanation: Methods of the Class Four
End of explanation
toDotList([Two(One(Tree('L1')), 'k', Two(Tree('M1'), 'k1', Tree('R1'))), Method('.repair()'), One(Three(Tree('L1'), 'k', Tree('M1'), 'k1', Tree('R1')))])
toDotList([Two(Two(Tree('L1'), 'k1', Tree('M1')), 'k', One(Tree('R1'))), Method('.repair()'), One(Three(Tree('L1'), 'k1', Tree('M1'), 'k', Tree('R1')))])
toDotList([Two(One(Tree('A')), 'k', Three(Tree('B'), 'k1', Tree('C'), 'k2', Tree('D'))), 
           Method('.repair()'), 
           Two(Two(Tree('A'), 'k', Tree('B')), 'k1', Two(Tree('C'), 'k2', Tree('D')))
          ])
toDotList([Two(Three(Tree('A'), 'k1', Tree('B'), 'k2', Tree('C')), 'k', One(Tree('D'))), 
           Method('.repair()'), 
           Two(Two(Tree('A'), 'k1', Tree('B')), 'k2', Two(Tree('C'), 'k', Tree('D')))
          ])
toDotList([Three(One(Tree('A')), 'kL', Two(Tree('B'), 'k', Tree('C')), 'kR', Tree('R')), 
           Method('.repair()'), 
           Two(Three(Tree('A'), 'kL', Tree('B'), 'k', Tree('C')), 'kR', Tree('R'))
          ])
toDotList([Three(Two(Tree('A'), 'k', Tree('B')), 'kL', One(Tree('C')), 'kR', Tree('R')), 
           Method('.repair()'), 
           Two(Three(Tree('A'), 'k', Tree('B'), 'kL', Tree('C')), 'kR', Tree('R'))
          ])
toDotList([Three(Tree('L'), 'kL', Two(Tree('A'), 'k', Tree('B')), 'kR', One(Tree('C'))), 
           Method('.repair()'), 
           Two(Tree('L'), 'kL', Three(Tree('A'), 'k', Tree('B'), 'kR', Tree('C')))
          ])
toDotList([Three(One(Tree('A')), 'kL', Three(Tree('B'), 'k1', Tree('C'), 'k2', Tree('D')), 'kR', Tree('R')), 
           Method('.repair()'), 
           Three(Two(Tree('A'), 'kL', Tree('B')), 'k1', Two(Tree('C'), 'k2', Tree('D')), 'kR', Tree('R'))
          ])
toDotList([Three(Three(Tree('A'), 'k1', Tree('B'), 'k2', Tree('C')), 'kL', One(Tree('D')), 'kR', Tree('R')), 
           Method('.repair()'), 
           Three(Two(Tree('A'), 'k1', Tree('B')), 'k2', Two(Tree('C'), 'kL', Tree('D')), 'kR', Tree('R'))
          ])
toDotList([Three(Tree('L'), 'kL', Three(Tree('A'), 'k1', Tree('B'), 'k2', Tree('C')), 'kR', One(Tree('D'))), 
           Method('.repair()'), 
           Three(Tree('L'), 'kL', Two(Tree('A'), 'k1', Tree('B')), 'k2', Two(Tree('C'), 'kR', Tree('D')))])
Explanation: Deletion
The method $t.\texttt{delete}(k)$ is specified as follows:
 - $t.\texttt{delete}(x) = t.\texttt{del}(x).\texttt{repair}().\texttt{shrink}()$
When $t.\texttt{del}(e)$ is called, $t$ is a 1-2-3 tree containing at most one 1-node.  This 1-node must occur at the root of the tree.  The expression $t.\texttt{del}(e)$ returns the 1-2-3 tree that results from removing the element $e$ from the tree $t$.
The important invariant maintained by del is that the trees $t$ and $t.\texttt{del}(k)$ have the same height.
The method $t.\texttt{repair}()$ takes a 1-2-3 tree $t$ that contains at most a single 1-node. 
If the tree $t$ has size $1$, then this 1-node may occur at the root.  Otherwise, the 1-node has to be a child of the root.
The method returns a 1-2-3 tree of the same size as $t$ where the 1-node can only occur at the root.
End of explanation
toDotList([One(Tree('A')), Method('.shrink()'), Tree('A')])
Explanation: Finally, we specify the method shrink.  The only class where the implementation of shrink is nontrivial is the class One.
End of explanation
<END_TASK>