Двоичные деревья названы так из-за подразумеваемой древовидной структуры ссылок на поддеревья. Обычно их узлы реализуются как тройки значений: (ЛевоеПоддерево, ЗначениеУзла, ПравоеПоддерево). Помимо этого реализация деревьев ничем более не ограничивается. Здесь мы будем использовать подход на основе классов:
• BinaryTree — главный объект, который инициализирует и контролирует фактическое дерево.
• EmptyNode — пустой объект, совместно используемый всеми пустыми поддеревьями (внизу).
• BinaryNode — объекты, представляющие непустые узлы дерева, имеющие значение и два поддерева.
Пример 18.14. PP4E\Dstruct\Classics\btree.py
"двоичное дерево поиска, не имеющее значений"
class BinaryTree:
def __init__(self): self.tree = EmptyNode()
def __repr__(self): return repr(self.tree)
def lookup(self, value): return self.tree.lookup(value)
def insert(self, value): self.tree = self.tree.insert(value)
class EmptyNode:
def __repr__(self): return ‘*’
def lookup(self, value): # достигнут конец снизу
return False
def insert(self, value):
return BinaryNode(self, value, self) # добавить новый узел снизу
class BinaryNode:
def __init__(self, left, value, right): self.data, self.left, self.right = value, left, right
def lookup(self, value): if self.data == value: return True elif self.data > value: return self.left.lookup(value) # искать слева
else:
return self.right.lookup(value) # искать справа
def insert(self, value): if self.data > value: self.left = self.left.insert(value) # вставить слева elif self.data < value:
self.right = self.right.insert(value) # вставить справа return self
def __repr__(self):
return (‘( %s, %s, %s )’ %
(repr(self.left), repr(self.data), repr(self.right)))
Как обычно, экземпляр BinaryTree может содержать объекты любого типа, поддерживающего предполагаемый протокол интерфейса, — в данном случае операторы сравнения > и <. В их число входят экземпляры классов с методами __lt__ и __gt__. Поэкспериментируем с интерфейсами этого модуля. В следующем сеансе в новое дерево добавляются пять целых чисел, а затем выполняется поиск значений 0…7, как мы делали это раньше с применением словарей и множеств:
C:\…\PP4E\Dstruct\Classics> python
> >> from btree import BinaryTree
> >> x = BinaryTree()
> >> for i in [3, 1, 9, 2, 7]: x.insert(i)
…
> >> for i in range(8): print((i, x.lookup(i)), end=’ ‘)
…
(0,False) (1,True) (2,True) (3,True) (4,False) (5,False) (6,False) (7,True)
Чтобы посмотреть, как растет это дерево, добавьте вызов функции print после каждой операции вставки. Узлы деревьев выводят себя как триплеты, а пустые узлы — как *. Результат отражает вложенность деревьев:
> >> y = BinaryTree()
> >> y
*
> >> for i in [3, 1, 9, 2, 7]:
… y.insert(i); print(y)
…
( *, 3, * )
( ( *, 1, * ), 3, * )
( ( *, 1, * ), 3, ( *, 9, * ) )
( ( *, 1, ( *, 2, * ) ), 3, ( *, 9, * ) )
( ( *, 1, ( *, 2, * ) ), 3, ( ( *, 7, * ), 9, * ) )
В конце этой главы мы увидим другой способ визуализации таких деревьев в графическом интерфейсе с именем PyTree (при желании вы можете перелистать книгу прямо сейчас). Значениями узлов в этом объекте дерева могут быть любые допускающие сравнение объекты Python. Например, ниже приводятся деревья строк:
> >> z = BinaryTree()
>>> for c in ‘badce’: z.insert(c)
…
>>> z
( ( *, ‘a’, * ), ‘b’, ( ( *, ‘c’, * ), ‘d’, ( *, ‘e’, * ) ) )
>>> z = BinaryTree()
>>> for c in ‘abcde’: z.insert(c)
…
>>> z
( *, ‘a’, ( *, ‘b’, ( *, ‘c’, ( *, ‘d’, ( *, ‘e’, * ) ) ) ) )
>>> z = BinaryTree()
>>> for c in ‘edcba’: z.insert(c)
…
>>> z
( ( ( ( ( *, ‘a’, * ), ‘b’, * ), ‘c’, * ), ‘d’, * ), ‘e’, * )
Обратите внимание на последний результат: если вставляемые в двоичное дерево элементы уже упорядочены, то получается ли ней ная структура и утрачивается способность деления пространства поиска двоичных деревьев (дерево растет только вправо или только влево). Это наихудшая ситуация, и на практике двоичные деревья ее избегают, разделяя значения. Но если вы хотите заняться этой темой дальше, почитайте книгу по структурам данных, в которой описывается технология балансировки деревьев для обеспечения их максимальной густоты.
Использованная литература:
Марк Лутц — Программирование на Python, 4-е издание, II том, 2011
