In [ ]:
%%HTML
<style>
.container { width:100% } 
</style>

Binary Tries


In [ ]:
import graphviz as gv

This notebook presents binary tries. 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.


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 string
  • attributes 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'])

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 $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

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

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

Implementing the Method delete

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

Testing


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 [ ]: