Реализация двоичных деревьев Python

realizaciya dvoichnyh derevev python Структуры данных

Двоичные деревья названы так из-за подразумеваемой древовидной структуры ссылок на поддеревья. Обычно их узлы реализуются как тройки значений: (ЛевоеПоддерево, ЗначениеУзла, ПравоеПоддерево). Помимо этого реализация деревьев ничем более не ограничивается. Здесь мы будем использовать подход на основе классов:

     BinaryTree — главный объект, который инициализирует и контролирует фактическое дерево.

     EmptyNode — пустой объект, совместно используемый всеми пустыми поддеревьями (внизу).

     BinaryNode — объекты, представляющие непустые узлы дерева, имеющие значение и два поддерева.

Чтобы не писать отдельные функции поиска, двоичные деревья строят из «интеллектуальных» объектов (экземпляров классов), которые умеют обрабатывать запросы вставки/поиска и вывода и передавать их объектам поддеревьев. Фактически это еще один пример действия отношения композиции в ООП: одни узлы дерева вкладываются в другие и запросы на поиск передаются вложенным поддеревьям. Единственный экземпляр пустого класса совместно используется всеми пустыми поддеревьями двоичного дерева, а при вставке лист EmptyNode заменяется на BinaryNode. Как это реализуется в программном коде, показано в примере 18.14.

Пример 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

Каталог сайтов Всего.ру
Оцените статью
Секреты программирования
Добавить комментарий