Обратите также внимание, что для простоты эти деревья хранят только значения, а поиск возвращает «истину» или «ложь». На практике иногда требуется хранить вместе ключ и ассоциируемое значение (и что-то еще) в каждом узле дерева. Для потенциальных лесорубов среди читателей в примере 18.15 показано, как выглядит такой объект дерева.
Пример 18.15. PP4E\Dstruct\Classics\btreevals.py
"двоичное дерево поиска, хранящее значения вместе с ключами"
class KeyedBinaryTree:
def __init__(self): self.tree = EmptyNode()
def __repr__(self): return repr(self.tree)
def lookup(self, key): return self.tree.lookup(key)
def insert(self, key, val): self.tree = self.tree.insert(key, val)
class EmptyNode:
def __repr__(self): return ‘*’
def lookup(self, key): # достигнут конец снизу
return None
def insert(self, key, val):
return BinaryNode(self, key, val, self) # добавить новый узел снизу
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) # искать слева
else:
return self.right.lookup(key) # искать справа
def insert(self, key, val):
if self.key == key: self.val = val elif self.key > key: self.left = self.left.insert(key, val) # вставить слева elif self.key < key:
self.right = self.right.insert(key, val) # вставить справа 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) # изменить значение ключа
print(t)
Ниже показаны результаты выполнения программного кода самотестирования — на этот раз узлы просто содержат больше информации:
C:\…\PP4E\Dstruct\Classics> python btreevals.py
( ( *, ‘aaa’=2, * ), ‘bbb’=1, ( *, ‘ccc’=3, * ) )
( ( *, ‘aaa’=5, * ), ‘bbb’=1, ( *, ‘ccc’=3, ( *, ‘ddd’=4, * ) ) )
Фактически результат напоминает ключи и значения во встроенном словаре, но собственная древовидная структура, подобная этой, может поддерживать особые случаи использования и алгоритмы, а также дальнейшее развитие программного кода. Однако, чтобы познакомиться со структурами данных, еще дальше отстоящих от встроенных типов, нам необходимо перейти к следующему разделу.
Использованная литература:
Марк Лутц — Программирование на Python, 4-е издание, II том, 2011
