In [ ]:
%%HTML
<style>
.container { width:100% }
</style>
In [ ]:
import graphviz as gv
This notebook presents binary tries. We define the set $\texttt{BT}$ of binary tries by induction:
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.
In [ ]:
class BinaryTrie:
sNodeCount = 0
def __init__(self):
BinaryTrie.sNodeCount += 1
self.mID = BinaryTrie.sNodeCount
def getID(self):
return self.mID # used only by graphviz
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 stringattributes is a list of those member variables that are used to produce the string
In [ ]:
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
The method $t.\texttt{toDot}()$ takes a binary trie $t$ and returns a graph that depicts the tree $t$.
In [ ]:
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
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.
In [ ]:
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
The class Nil represents an empty binary trie. It has no member variables of its own.
In [ ]:
class Nil(BinaryTrie):
def __init__(self):
BinaryTrie.__init__(self)
def __str__(self):
return 'Nil()'
The class Bin represents a binary trie of the form $\texttt{Bin}(v,l,r)$.
In [ ]:
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'])
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 $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.
In [ ]:
def find(self, n):
"your code here"
Nil.find = find
del find
In [ ]:
def find(self, n):
"your code here"
Bin.find = find
del find
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
In [ ]:
def insert(self, n, v):
"your code here"
Nil.insert = insert
del insert
In [ ]:
def insert(self, n, v):
"your code here"
Bin.insert = insert
del insert
First we have to implement a method simplify which is specified by the following equations:
Your equations here!
In [ ]:
def simplify(self):
"your code here"
Bin.simplify = simplify
del simplify
Your equations here!
In [ ]:
def delete(self, n):
"your code here"
Nil.delete = delete
del delete
In [ ]:
def delete(self, n):
"your code here"
Bin.delete = delete
del delete
In [ ]:
b = Nil()
b.toDot()
In [ ]:
b = b.insert(0, 'a')
b.toDot()
In [ ]:
b = b.insert(1, 'b')
b.toDot()
In [ ]:
b = b.insert(2, 'c')
b.toDot()
In [ ]:
b = b.delete(0)
b.toDot()
In [ ]:
b = b.delete(1)
b.toDot()
In [ ]:
b = b.delete(2)
b.toDot()
Let us compute the prime numbers next.
In [ ]:
Primes = Nil()
for i in range(2, 101):
Primes = Primes.insert(i, True)
Primes.toDot()
In [ ]:
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=' ')
In [ ]: