class EmptyNode:
def repr(self):
return '*'
def lookup(self, key): # fail at the bottom
return None
def insert(self, key, val):
return BinaryNode(self, key, val, self) # add node at bottom
class BinaryNode:
def init(self, left, key, val, right):
self.key, self.val = key, val
self.left, self.right = left, right
def lookup(self, key):
if self.key == key:
return self.val
elif self.key > key:
return self.left.lookup(key) # look in left
else:
return self.right.lookup(key) # look in right
def insert(self, key, val):
if self.key == key:
self.val = val
elif self.key > key:
self.left = self.left.insert(key, val) # grow in left
elif self.key < key:
self.right = self.right.insert(key, val) # grow in right
return self
def repr(self):
return ('( %s, %s=%s, %s )' %
(repr(self.left), repr(self.key), repr(self.val), repr(self.right)))
if name == 'main':
t = KeyedBinaryTree()
for (key, val) in [('bbb', 1), ('aaa', 2), ('ccc', 3)]:
t.insert(key, val)
print(t)
print(t.lookup('aaa'), t.lookup('ccc'))
t.insert('ddd', 4)
t.insert('aaa', 5) # changes key's value
print(t)
The following shows this script’s self-test code at work; nodes simply have more con-
tent this time around:
C:\...\PP4E\Dstruct\Classics> python btreevals.py
( ( *, 'aaa'=2, * ), 'bbb'=1, ( *, 'ccc'=3, * ) )
2 3
( ( *, 'aaa'=5, * ), 'bbb'=1, ( *, 'ccc'=3, ( *, 'ddd'=4, * ) ) )In fact, the effect is similar to the keys and values of a built-in dictionary, but a custom
tree structure like this might support custom use cases and algorithms, as well as code
Binary Search Trees | 1389