In [ ]:
%%HTML
<style>
.container { width:100% }
</style>
In [ ]:
import graphviz as gv
Ths notebook presents 2-3 trees. We define these trees inductively as follows:
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
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.
In [ ]:
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
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 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]))})"
TwoThreeTree._make_string = _make_string
The method $t.\texttt{toDot}()$ takes a 2-3-4 tree $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 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
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.
In [ ]:
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
The function $\texttt{toDotList}(\texttt{NodeList})$ takes a list of trees and displays them one by one.
In [ ]:
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
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.
In [ ]:
class Tree(TwoThreeTree):
def __init__(self, name):
TwoThreeTree.__init__(self)
self.mName = name
def __str__(self):
return self.mName
def isTree(self):
return True
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.
In [ ]:
class Method(TwoThreeTree):
def __init__(self, label):
TwoThreeTree.__init__(self)
self.mLabel = label
def __str__(self):
return self.mLabel
def isMethod(self):
return True
The class Nil represents an empty tree. It has no member variables of its own.
In [ ]:
class Nil(TwoThreeTree):
def __init__(self):
TwoThreeTree.__init__(self)
def isNil(self):
return True
def __str__(self):
return 'Nil()'
The class Onerepresents a 1-node. These are nodes without a key that have only a single child.
In [ ]:
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'])
Graphically, the node $\texttt{One}(t)$ is represented as shown below:
In [ ]:
toDotList([One(Tree('t'))])
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$.
In [ ]:
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'])
Graphically, the node $\texttt{Two}(l, k, r)$ is represented as shown below:
In [ ]:
toDotList([Two(Tree('l'), 'k', Tree('r'))])
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.
In [ ]:
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
Graphically, the node $\texttt{Three}(l, k_L, m, k_R, r)$ is represented as shown below:
In [ ]:
toDotList([Three(Tree('l'), 'kL', Tree('m'), 'kR', Tree('r'))])
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.
In [ ]:
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
Graphically, the node $\texttt{Four}(l, k_L, m_L, k_M, m_R, k_R, r)$ is represented as shown below:
In [ ]:
toDotList([Four(Tree('l'), 'kL', Tree('mL'), 'kM', Tree('mR'), 'kR', Tree('r'))])
The empty tree does not contain any keys: $$ \texttt{Nil}.\texttt{member}(k) = \texttt{False} $$
In [ ]:
def member(self, k):
return False
Nil.member = member
Insertings a key $k$ into an empty node returns a 2-node with two empty subtrees.
In [ ]:
toDotList([Nil(), Method('insert(k)'), Two(Nil(), 'k', Nil())])
Mathematically, this can be written as follows: $$ \texttt{Nil}.\texttt{ins}(k) = \texttt{Two}(\texttt{Nil}, k, \texttt{Nil}) $$ The implementation is straightforward as shown below.
In [ ]:
def _ins(self, k):
return Two(Nil(), k, Nil())
Nil._ins = _ins
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..
In [ ]:
def _extract(self):
return self.mLeft, self.mKey, self.mRight
Two._extract = _extract
Given a 2-node $t$ and a key $k$, the method $t.\texttt{member}(k)$ checks whether the key $k$ occurs in $t$. It is specified as follows:
In [ ]:
def member(self, key):
l, k, r = self._extract()
if k == key:
return True
elif key < k:
return l.member(key)
elif key > self.mKey:
return r.member(key)
Two.member = member
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:
In [ ]:
toDotList([Two(Tree('l'), 'k', Tree('r')), Method('.ins(k)'), Two(Tree('l'), 'k', Tree('r')) ])
In [ ]:
toDotList([Method('k1 < k2:'), Two(Nil(), 'k1', Nil()), Method('.ins(k2)'), Three(Nil(), 'k1', Nil(), 'k2', Nil()) ])
In [ ]:
toDotList([Method('k2 < k1:'), Two(Nil(), 'k1', Nil()), Method('.ins(k2)'), Three(Nil(), 'k2', Nil(), 'k1', Nil()) ])
In [ ]:
toDotList([Method('k1 < k2:'), Two(Tree('l'), 'k1', Tree('r')), Method('.ins(k2)'), Two(Tree('l'), 'k1', Tree('r.ins(k2)')) ])
In [ ]:
toDotList([Method('k2 < k1:'), Two(Tree('l'), 'k1', Tree('r')), Method('.ins(k2)'), Two(Tree('l.ins(k2)'), 'k1', Tree('r')) ])
I have collected all of these equations below:
Using these equations, the implementation of ins is straightforward.
In [ ]:
def _ins(self, key):
l, k, r = self._extract()
if k == key:
return self
elif l.isNil() and r.isNil():
if key < k:
return Three(Nil(), key, Nil(), k, Nil())
else:
return Three(Nil(), k, Nil(), key, Nil())
elif not l.isNil() and not r.isNil():
if key < k:
self.mLeft = l._ins(key)._restore()
else:
self.mRight = r._ins(key)._restore()
return self
assert False, f'Unbalanced node {self}'
Two._ins = _ins
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.
In [ ]:
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'))])
In [ ]:
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')))])
I have collected both equations below:
If neither the left nor the right child node of a 2-node is a 4-node, the node is returned unchanged.
In [ ]:
def _restore(self):
l, k, r = self._extract()
if l.isFour():
l1, kl, ml, km, mr, kr, r1 = l._extract()
return Three(Two(l1, kl, ml), km, Two(mr, kr, r1), k, r)
if r.isFour():
l1, kl, ml, km, mr, kr, r1 = r._extract()
return Three(l, k, Two( l1, kl, ml), km, Two( mr, kr, r1))
return self
Two._restore = _restore
The method extract returns the member variables stored in a 3-node.
In [ ]:
def _extract(self):
return self.mLeft, self.mKeyL, self.mMiddle, self.mKeyR, self.mRight
Three._extract = _extract
Given a 3-node $t$ and a key $k$, the method $t.\texttt{member}(k)$ checks whether the key $k$ occurs in $t$. It is specified as follows:
In [ ]:
def member(self, key):
l, kL, m, kR, r = self._extract()
if key == kL or key == kR:
return True
if key < kL:
return l.member(key)
if kL < key < kR:
return m.member(key)
if kR < key:
return self.mRight.member(key)
Three.member = member
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. It is defined as follows:
\texttt{Four}(\texttt{Nil},k,\texttt{Nil},k_l,\texttt{Nil},k_r,\texttt{Nil})$ \texttt{Four}(\texttt{Nil},k_l,\texttt{Nil},k,\texttt{Nil},k_r,\texttt{Nil})$$k_r < k \rightarrow \texttt{Three}(\texttt{Nil},k_l,\texttt{Nil},k_r,\texttt{Nil}).\texttt{ins}(k) =
\texttt{Four}(\texttt{Nil},k_l,\texttt{Nil},k_r,\texttt{Nil},k,\texttt{Nil})$$k < k_l \wedge l \not= \texttt{Nil} \wedge m \not= \texttt{Nil}\wedge r \not= \texttt{Nil} \rightarrow \texttt{Three}(l,k_l,m,k_r,r).\texttt{ins}(k) = \texttt{Three}\bigl(l.\texttt{ins}(k),k_l,m,k_r,r\bigr).\texttt{restore}()$
In [ ]:
def _ins(self, key):
l, kL, m, kR, r = self._extract()
if key == kL or key == kR:
return self
if l.isNil() and m.isNil() and r.isNil():
if key < kL:
return Four(Nil(), key, Nil(), kL, Nil(), kR, Nil())
if kL < key < kR:
return Four(Nil(), kL, Nil(), key, Nil(), kR, Nil())
if kR < key:
return Four(Nil(), kL, Nil(), kR, Nil(), key, Nil())
if not l.isNil() and not m.isNil() and not r.isNil():
if key < kL:
self.mLeft = l._ins(key)._restore()
elif kL < key < kR:
self.mMiddle = m._ins(key)._restore()
elif kR < key:
self.mRight = r._ins(key)._restore()
return self
assert False, f'Unbalanced node {self}'
Three._ins = _ins
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:
In [ ]:
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')),
])
In [ ]:
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'))
])
In [ ]:
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')))
])
Below I have collected all the equations specifying the implementation of restore for 3-nodes.
If neither of the child nodes of a 3-node is a 4-node, the node is returned unchanged.
In [ ]:
def _restore(self):
l, kl, m, kr, r = self._extract()
if l.isFour():
l1, k1, ml, k2, mr, k3, r1 = l._extract()
return Four(Two(l1, k1, ml), k2, Two( mr, k3, r1), kl, m, kr, r)
if m.isFour():
l1, k1, ml, k2, mr, k3, r1 = m._extract()
return Four(l, kl, Two( l1, k1, ml), k2, Two( mr, k3, r1), kr, r)
if r.isFour():
l1, k1, ml, k2, mr, k3, r1 = r._extract()
return Four(l, kl, m, kr, Two( l1, k1, ml), k2, Two( mr, k3, r1))
return self
Three._restore = _restore
The method extract returns the member variables stored in a 4-node.
In [ ]:
def _extract(self):
return self.mLeft, self.mKeyL, self.mMiddleL, self.mKeyM, self.mMiddleR, self.mKeyR, self.mRight
Four._extract = _extract
The method restore returns a 4-node unchanged.
In [ ]:
def _restore(self):
return self
Four._restore = _restore
The function grow turns a 4-node into 3 2-nodes. Graphically, it is specified as follows:
In [ ]:
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')))
])
In [ ]:
def _grow(self):
l, kl, ml, km, mr, kr, r = self._extract()
return Two(Two(l, kl, ml), km, Two(mr, kr, r))
Four._grow = _grow
In [ ]:
m = Nil()
m.isNil()
m.toDot()
In [ ]:
m = m.insert("anton")
m.toDot()
In [ ]:
m = m.insert("hugo" )
m.toDot()
In [ ]:
m = m.insert("gustav")
m.toDot()
In [ ]:
m = m.insert("jens")
m.toDot()
In [ ]:
m = m.insert("hubert")
m.toDot()
In [ ]:
m = m.insert("andre")
m.toDot()
In [ ]:
m = m.insert("philipp")
m.toDot()
In [ ]:
m = m.insert("rene")
m.toDot()
In [ ]:
m = m.insert("walter")
m.toDot()
Let's generate 2-3 tree with random keys.
In [ ]:
import random as rnd
In [ ]:
t = Nil()
for k in range(30):
k = rnd.randrange(100)
t = t.insert(k)
t.toDot()
Lets us try to create a tree by inserting sorted numbers because that resulted in linear complexity for ordered binary trees.
In [ ]:
M = Nil()
for k in range(38):
M = M.insert(k)
M.toDot()
Finally, we compute the set of prime numbers $\leq 100$. Mathematically, this set is given as follows: $$ \bigl\{2, \cdots, 100 \bigr\} - \bigl\{ i \cdot j \bigm| i, j \in \{2, \cdots, 100 \}\bigr\}$$ First, we compute the set of products $\bigl\{ i \cdot j \bigm| i, j \in \{2, \cdots, 100 \}\bigr\}$. Then, we insert all naturals numbers less than 100 that are not products into the set of primes.
In [ ]:
Products = Nil()
for i in range(2, 101):
for j in range(2, 101):
Products = Products.insert(i * j)
Primes = Nil()
for k in range(2, 101):
if not Products.member(k):
Primes = Primes.insert(k)
Primes.toDot()
The method $t.\texttt{delete}(k)$ is specified as follows:
This method has already been implemented in he class TwoThreeTree.
Below we specify the method del. 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.
For the class Nil the method $t.\texttt{del}(x)$ is specified as follows:
In [ ]:
def _del(self, x):
"your code here"
TwoThreeTree._del = _del
For the class Two the method del is specified as follows:
$k \not= e \rightarrow \texttt{Two}(\texttt{Nil}, k, \texttt{Nil}).\texttt{del}(e) = \texttt{Two}(\texttt{Nil}, k, \texttt{Nil})$
$L \not= \texttt{Nil} \wedge R \not= \texttt{Nil} \wedge R.\texttt{delMin}() = \langle R', kM\rangle \rightarrow \texttt{Two}(L, k, R).\texttt{del}(k) = \texttt{Two}(L, kM, R').\texttt{repair}()$
In [ ]:
def _del(self, e):
"your code here"
Two._del = _del
Below we specify the method del for the class Three:
$k_L \not= e \wedge k_R \not= e \rightarrow \texttt{Three}(\texttt{Nil}, k_L, \texttt{Nil}, k_R, \texttt{Nil}).\texttt{del}(e) = \texttt{Three}(\texttt{Nil}, k_L, \texttt{Nil}, k_R, \texttt{Nil})$
$L \not= \texttt{Nil} \wedge M.\texttt{delMin}() = \langle M', k_M\rangle \rightarrow \texttt{Three}(L, k_L, M, k_R, R).\texttt{del}(k_L) = \texttt{Three}(L, k_M, M', k_R, R).\texttt{repair}()$
In [ ]:
def _del(self, e):
"your code here"
Three._del = _del
The method $t.\texttt{delMin}()$ removes the smallest key $k_M$ from the tree $t$ and returns a pair $\langle t', k_M \rangle$ where $t'$ is the tree that results from deleting $k_M$ in $t$. The nodes $t'$ and $t$ have the same height.
For the class Two the method delMin is specified via the following equations:
In [ ]:
def _delMin(self):
"your code here"
Two._delMin = _delMin
For the class Three the method delMin is specified via the following equations:
In [ ]:
def _delMin(self):
"your code here"
Three._delMin = _delMin
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.
In [ ]:
toDotList([Two(One(Tree('L1')), 'k', Two(Tree('M1'), 'k1', Tree('R1'))), Method('.repair()'), One(Three(Tree('L1'), 'k', Tree('M1'), 'k1', Tree('R1')))])
In [ ]:
toDotList([Two(Two(Tree('L1'), 'k1', Tree('M1')), 'k', One(Tree('R1'))), Method('.repair()'), One(Three(Tree('L1'), 'k1', Tree('M1'), 'k', Tree('R1')))])
In [ ]:
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')))
])
In [ ]:
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')))
])
In [ ]:
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'))
])
In [ ]:
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'))
])
In [ ]:
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')))
])
In [ ]:
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'))
])
In [ ]:
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'))
])
In [ ]:
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')))])
The equation specifying the method repairfor the class Nilis:
In [ ]:
def _repair(self):
"your code here"
Nil._repair = _repair
The equation specifying the method repair for the class One is:
In [ ]:
def _repair(self):
"your code here"
One._repair = _repair
The equations specifying the method repair for the class Two are:
$\texttt{Two}(\texttt{Two}(L_1, k_1, M_1), k, \texttt{One}(R_1)).\texttt{repair}() = \texttt{One}(\texttt{Three}(L_1, k_1, M_1, k, R_1))$
$\texttt{Two}(\texttt{One}(A), k, \texttt{Three}(B, k_1, C, k_2, D)).\texttt{repair}() = \texttt{Two}(\texttt{Two}(A, k, B), k_1, \texttt{Two}(C, k_2, D))$
In [ ]:
def _repair(self):
"your code here"
Two._repair = _repair
The equations specifying the method repair for the class Three:
$\texttt{Three}(L, k_L, \texttt{Two}(A, k, B), k_R, \texttt{One}(C)).\texttt{repair}() = \texttt{Two}(L, k_L, \texttt{Three}(A, k, B, k_R, C))$
$\texttt{Three}(\texttt{One}(A), k_L, \texttt{Three}(B, k_1, C, k_2, D), k_R, R).\texttt{repair}() = \texttt{Three}(\texttt{Two}(A, k_L, B), k_1, \texttt{Two}(C, k_2, D), k_R, R)$
In [ ]:
def _repair(self):
"your code here"
Three._repair = _repair
Finally, we specify the method shrink. The only class where the implementation of shrink is nontrivial is the class One.
In [ ]:
toDotList([One(Tree('A')), Method('.shrink()'), Tree('A')])
$\texttt{One}(A).\texttt{shrink}() = A$
In [ ]:
def _shrink(self):
return self.mChild
One._shrink = _shrink
In [ ]:
m.toDot()
In [ ]:
m = m.delete('hugo')
m.toDot()
In [ ]:
m = m.delete('walter')
m.toDot()
In [ ]:
m = m.delete('hubert')
m.toDot()
In [ ]:
m = m.delete('anton')
m.toDot()
In [ ]:
m = m.delete('jens')
m.toDot()
In [ ]:
m = m.delete('rene')
m.toDot()
In [ ]:
m = m.delete('gustav')
m.toDot()
In [ ]:
m = m.delete('andre')
m.toDot()
In [ ]:
m = m.delete('philipp')
m.toDot()
In [ ]:
Primes = Nil()
for k in range(2, 101):
Primes = Primes.insert(k)
Primes.toDot()
In [ ]:
for i in range(2, 101):
for j in range(2, 101):
Primes = Primes.delete(i * j)
Primes.toDot()
In [ ]: