<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Binary Tries
Step1:  This notebook presents <em style="color
Step2:  The function make_string is a helper function that is used to simplify the implementation of __str__.
  - self 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 binary trie $t$ and returns a graph that depicts the tree $t$.
Step4:  The method $t.\texttt{collectIDs}(d)$ takes a binary trie $t$ and a dictionary $d$ and updates the dictionary so that the following holds
Step5:  The class Nil represents an empty binary trie.  It has no member variables of 
its own.
Step6:  The class Bin represents a binary trie of the form $\texttt{Bin}(v,l,r)$.
It has three member variables
Step7:  Implementing the Method  find
Given a binary trie $b$ and a natural number $n$, the expression
$$ b.\texttt{find}(n) $$ 
returns the value in $b$ that is associated with the number $n$.  If there is no value associated
with $b$, then the expression evaluates to $\Omega$.  Formally, the value of the expression
$b.\texttt{find}(n)$ is defined by induction on both $b$ and $n$
Step8:  Implementing the Method  insert
Given a binary trie $b$, a natural number $n$ and a value $v$, the expression
$$  b.\texttt{insert}(n, v) $$
is defined by induction on $b$ and $n$
Step9:  Implementing the Method  delete
First we have to implement a method simplify.  Given a binary trie $b$,
the expression $b.\texttt{simplify}()$ returns Nil iff $b$ does not contain any key.  Otherwise, $b$ is left unchanged.
The method simplify is specified by the following equations
Step10:  Your equations here!
Step11:  Testing
Step12:  Let us compute the prime numbers next.
<ASSISTANT_TASK:>
Python Code:
import graphviz as gv
Explanation: Binary Tries
End of explanation
class BinaryTrie:
    sNodeCount = 0
    
    def __init__(self):
        BinaryTrie.sNodeCount += 1
        self.mID = BinaryTrie.sNodeCount
        
    def getID(self):
        return self.mID  # used only by graphviz
Explanation: This notebook presents <em style="color:blue;">binary tries</em>.  We define the set $\texttt{BT}$ of binary tries by induction:
$\texttt{Nil} \in \texttt{BT}$.
$\texttt{Bin}(v,l,r) \in \texttt{BT}$ provided that
$v \in \texttt{Value} \cup {\Omega}$  and
$l,r \in \texttt{BT}$.
The class BinaryTrie is a superclass for constructing binary tries.  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 object of class BinaryTrie has a unique identifier mID that is stored as a member variable.
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]))})"
    
BinaryTrie._make_string = _make_string
del _make_string
Explanation: The function make_string is a helper function that is used to simplify the implementation of __str__.
  - self 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 isinstance(t, Nil):
            dot.node(str(n), label='', shape='point') 
        elif isinstance(t, Bin):
            if t.mValue != None:
                dot.node(str(n), label='{' + str(t.mDigit) + '|' + str(t.mValue) + '}')
            else:
                dot.node(str(n), label='{' + str(t.mDigit) + '|' + '}')
        else:
            assert False, f'Unknown node {t}'
    for n, t in nodeDict.items():
        if isinstance(t, Bin):
            dot.edge(str(n), str(t.mLeft .getID()))
            dot.edge(str(n), str(t.mRight.getID()))
    return dot
BinaryTrie.toDot = toDot
del toDot
Explanation: The method $t.\texttt{toDot}()$ takes a binary trie $t$ and returns a graph that depicts the tree $t$.
End of explanation
def _collectIDs(self, nodeDict):
    nodeDict[self.getID()] = self
    if isinstance(self, Bin):
        self.mLeft ._collectIDs(nodeDict)
        self.mRight._collectIDs(nodeDict)
        self.mLeft .mDigit = '0'
        self.mRight.mDigit = '1'
        
BinaryTrie._collectIDs = _collectIDs
del _collectIDs
Explanation: The method $t.\texttt{collectIDs}(d)$ takes a binary trie $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
class Nil(BinaryTrie):
    def __init__(self):
        BinaryTrie.__init__(self)
          
    def __str__(self):
        return 'Nil()'
Explanation: The class Nil represents an empty binary trie.  It has no member variables of 
its own.
End of explanation
class Bin(BinaryTrie):
    def __init__(self, value, left, right):
        BinaryTrie.__init__(self)
        self.mValue = value
        self.mLeft  = left
        self.mRight = right
        self.mDigit = '' # only used by graphviz
    def __str__(self):
        return _make_string(self, ['mValue', 'mLeft', 'mRight'])
Explanation: The class Bin represents a binary trie of the form $\texttt{Bin}(v,l,r)$.
It has three member variables:
* mValue is the value that is stored at this node.
* mLeft  is the left subtree.
* mRight is the right subtree.
* mDigit is a string that is used by graphviz to display the node.
End of explanation
def find(self, n):
    "your code here"
Nil.find = find
del find
def find(self, n):
    "your code here"
    
Bin.find = find
del find
Explanation: Implementing the Method  find
Given a binary trie $b$ and a natural number $n$, the expression
$$ b.\texttt{find}(n) $$ 
returns the value in $b$ that is associated with the number $n$.  If there is no value associated
with $b$, then the expression evaluates to $\Omega$.  Formally, the value of the expression
$b.\texttt{find}(n)$ is defined by induction on both $b$ and $n$:
  - $\texttt{Nil}.\texttt{find}(n) = \Omega$,
since the empty trie doesn't store any values.
$\texttt{Bin}(v,l,r).\texttt{find}(0) = v$,
because $0$ is interpreted as the empty string $\varepsilon$.
  - $n \not= 0 \rightarrow \texttt{Bin}(v,l,r).\texttt{find}(2\cdot n) = l.\texttt{find}(n)$,
because if a number is represented in binary, then the last bit of every even number is zero
and zero chooses the left subtree.
  - $\texttt{Bin}(v,l,r).\texttt{find}(2 \cdot n + 1) = r.\texttt{find}(n)$,
because if a number is represented in binary, then the last bit of every odd number is 1 and 
1 is associated with the right subtree.
End of explanation
def insert(self, n, v):
    "your code here"
    
Nil.insert = insert
del insert
def insert(self, n, v):
    "your code here"
    
Bin.insert = insert
del insert
Explanation: Implementing the Method  insert
Given a binary trie $b$, a natural number $n$ and a value $v$, the expression
$$  b.\texttt{insert}(n, v) $$
is defined by induction on $b$ and $n$:
Your equations here!
E = m * c ** 2
End of explanation
def simplify(self):
    "your code here"
    
Bin.simplify = simplify
del simplify
Explanation: Implementing the Method  delete
First we have to implement a method simplify.  Given a binary trie $b$,
the expression $b.\texttt{simplify}()$ returns Nil iff $b$ does not contain any key.  Otherwise, $b$ is left unchanged.
The method simplify is specified by the following equations:
Your equations here!
End of explanation
def delete(self, n):
    "your code here"
Nil.delete = delete
del delete
def delete(self, n):
    "your code here"
    
Bin.delete = delete
del delete
Explanation: Your equations here!
End of explanation
b = Nil()
b.toDot()
b = b.insert(0, 'a')
b.toDot()
b = b.insert(1, 'b')
b.toDot()
b = b.insert(2, 'c')
b.toDot()
b = b.delete(0)
b.toDot()
b = b.delete(1)
b.toDot()
b = b.delete(2)
b.toDot()
Explanation: Testing
End of explanation
Primes = Nil()
for i in range(2, 101):
    Primes = Primes.insert(i, True)
Primes.toDot()
for i in range(2, 51):
    for j in range(i, 100 // i + 1):
        Primes = Primes.delete(i * j)
display(Primes.toDot())
for i in range(2, 101):
    if Primes.find(i):
        print(i, end=' ')
Explanation: Let us compute the prime numbers next.
End of explanation
<END_TASK>