Rust: реализация двоичного дерева

Поскольку Rust приобрел довольно широкую известность и пополнил ряды своих преданных поклонников, я решил отложить в сторону любимый JS и заняться изучением нового языка. Должен сказать, что предприятие не для слабонервных. К счастью, за исключением редких случаев недопонимания, компилятор  —  ваш верный друг, поскольку всегда укажет на ошибки и даже предложит решения. Посвятив освоению языка какое-то время и преодолев первый крутой подъем кривой обучаемости, вы начинаете влюбляться в Rust  —  что со мной и произошло! 

В этой статье во всей красе Rust будет представлена реализация моей любимой структуры данных: двоичного дерева. Это обычное дерево, которое состоит из узлов, содержащих (потенциально глубоко) вложенные значения. Особенностью такого дерева является наличие у его узлов только двух дочерних значений: левого и правого. Как правило, подобные структуры служат для представления математических выражений, но могли бы использоваться и для парсинга простых грамматик. В интересах планируемой реализации нашим узлам также полезно было бы узнать, какой тип операции они представляют. Постараемся придать ей обобщенный вид без привязки базовой структуры к какому-либо типу. Перед вами простое представление двоичного дерева: 

Двоичное дерево с нестандартной маркировкой 

На этом изображении терминальные узлы отмечены цифрами. Обратите внимание, что двоичные деревья смещены влево и расположены в глубину. Это значит, что при обходе дерева процесс вычисления начнется с самого дальнего левого узла, рекурсивно переходя от узлов левее к узлам правее. Далее я объясню более подробно. 

Придумаем минимальную структуру для представления данных узла: 

Рекурсивные типы вызывают гнев компилятора

…компилятор тут же на нас разозлился. Структура не может напрямую ссылаться на саму себя, поскольку она становится рекурсивным типом, что недопустимо в Rust. Но, к счастью, есть возможность поместить рекурсивные узлы в Box, тем самым косвенно показав, что это указатель, ссылающийся на объект в куче. Посмотрим, поможет ли данный прием решить нашу проблему:  

Box предоставляет уровень косвенной адресации 

Сработало. Box добавил уровень косвенной адресации через сохранение указателя на BTNode, позволяя нам обойти запрет на рекурсивный тип. А что же насчет Op? Им будет enum, представляющее возможные операции с узлами. В нашем примере ограничимся простыми арифметическими действиями: 

enum представляет ряд простых арифметических операций

Довольно просто. У нас есть вариант для нескольких базовых арифметических операций. Обратили внимание на Id(T)? Это особая операция. Поскольку нам необходимо, чтобы значения в дереве были экземплярами структур BTNode, нет никакой возможности поместить в него i32 напрямую. Проблема в том, что согласно нашим ожиданиям терминальными значениями должны быть исходные числа. Допустим, у нас есть выражение (3 + 4) * (5 * 2). Можно представить его в виде дерева с тремя узлами: корневой узел Mul с левым и правым значениями узлов; его левый потомок  —  узел Add с левым и правым значениями, т. е. 3 и 4; и правый потомок  —  узел Mul со значениями 5 и 2. Эти исходные числа называются терминальными значениями.

Такое название обусловлено тем, что эти узлы располагаются на концах дерева. Если обычный узел  —  это ветвь, то терминальный  —  это лист. Достигнув подобного узла, вы не увидите более глубоких вложений, по которым можно было бы пройти вслед за выполнением кода, в связи с чем его внутреннее значение можно истолковать как исходное значение, а не как узел. Чтобы получить терминальные значения из узлов, необходимо выбрать для сохранения данных вариант Op::Id(T) . Пока мы на этом этапе, вероятно, стоит подумать о том, что упакованные в Box левый и правый узлы могут быть не определены в терминальном узле. С учетом этого каждый из них следует обернуть в Option:

Opion узла <T>, упакованного в Box 

Итак, мы определили узлы таким образом, чтобы их потомки могли быть упакованным значением Some или None. Хотя, определенно, это выглядит презабавно. Придадим коду чуть более привлекательный вид с помощью псевдонима типа: 

Объявление псевдонима типа для узлов-потомков 

Можно разместить эту инструкцию в начале кода, заменив длинную версию в BTNode. Досконально продумав способ определения узлов, перейдем к определению дерева: 

Приятная взгляду и простая структура 

Поскольку мы уделили достаточно времени определению узлов, дальше сложностей уже не возникнет. Наше дерево либо пустое, либо его вершина содержит значение Some. Поскольку вложенные узлы являются значениями указателей на узлы-потомки, то у нас есть все необходимое для определения дерева. Поработав с его данными, приступим к реализации и начнем с узлов. 

Конструктор для узлов 

Ничего сложного. Конструктор был вертикально расширен, и теперь у нас есть способ создавать экземпляры структуры узлов. А представьте процесс объявления new для каждого узла  —  написать придется немало! Предлагаю внести немного абстракции и создать специальные конструкторы. 

Специальные конструкторы для узлов

Каждая из этих функций создает специальную версию BTNode, которая в дальнейшем упрощает их объявление. Все они отталкиваются от исходного конструктора BTNode::new, за исключением IdNode, создающей BTNode напрямую, поскольку значения его правого и левого узлов не важны, и ее интересует только значение i32.

Настало время подумать о реализации какой-нибудь функциональности для дерева. Ему нужна одна главная функция  —  обход узлов для получения одного значения. Нам предстоит ее написать.

Обход двоичного дерева 

Я также включил простой конструктор. Давайте разберем этот код. Если посмотреть на сигнатуру для реализации i32, то увидим, что она принимает ссылку указателя на узел и возвращает i32. Прежде всего мы объявляем изменяемую пару левого и правого значений Option<i32> и инициализируем их как None  —  после обхода узлов-потомков сможем их переприсвоить . Далее рекурсивно вызываем collapse для узлов-потомков, чтобы переприсвоить левое и правое значения только при условии, что любое из них является нетерминальным узлом, т. е. узлом, не принадлежащим к IdNodes. Затем наступает очередь if let с левым и правым значениями для извлечения их в i32. Во время этой операции мы переопределяем переменные l и r как неизменяемые (когда повторно объявляем их с помощью let). Наконец, мы сопоставляем операцию узлов, объединяя и возвращая значения (или вызываем panic! при случайном делении на 0).

Создадим дерево на основе этого рисунка: 

Двоичное дерево с условными обозначениями — неидеально, поскольку написано от руки 

Это дерево представляет выражение (10 - (2 * 2)) + (8 + (10 / 2)). Зеленые числа указывают порядок, согласно которому алгоритм обходит узлы, а красные будут использоваться в качестве значений узлов. 

Создание и обход двоичного дерева 

В консоли должен появиться вывод 19. Такой же результат получился бы и у нас, если бы сами выполнили обход по узлам.  

По этой ссылке можно перейти в “песочницу” Rust и поэкспериментировать с кодом. 

В статье был рассмотрен простой пример, но Op enum вполне способен представлять и что-нибудь другое. Мы могли бы реализовать дерево для другого типа, применив его в иных целях, например для парсинга простой грамматики скрипта или накопления специальных эффектов в видео игре. В мире компьютерной науки такая структура данных, как двоичное дерево, находит себе успешное практическое использование. 

Благодарю за внимание и надеюсь, что материал статьи был для вас полезен. 

Читайте также:

Читайте нас в Telegram, VK и Яндекс.Дзен


Перевод статьи Ross: Rust: Binary Tree

Предыдущая статьяAirflow и Kubernetes  -  лучшее решение для конвейеров данных Geoblink
Следующая статьяСоздание интерфейсов, удобных для алгоритмов