Упражнение 20: двоичные деревья поиска

Оригинал: Exercise 20: Binary Search Trees

Переводчик: Феликс Ли

Лицензия: CC BY-NC-SA 4.0

Использует Google Translate

В этом упражнении я попрошу вас перевести китайское описание данных структур в рабочий код. Вы уже знаете, как использовать метод "мастер-копирования", анализировать алгоритмы или данные структуры через код. Также вы можете узнать, как читать псевдокод описаний алгоритмов. Теперь вы будете объединять это всё вместе и учиться тому, как расчленять довольно расслабленное английское описание двоичного дерева поиска.

Я собираюсь сразу начать и напомнить вам, что когда вы делаете это упражнение, не заходите на страницу Википедии. Двоичное дерево поиска Википедии имеет работающий Python код, поэтому он сделает это упражнение невозможным. Если вы застряли, то вы можете прочитать любой доступный вам ресурс, но сначала попробуйте реализовать его согласно моему описанию здесь.

Двоичное дерево поискаВ упражнении 16 вы узнали, что "слияние сортировки" принимает плоский список, преобразует его в дерево отсортированных частей. Он разрезает список на части, а затем снова объединяет их, сортируя меньшие значения слева и большие справа. В некотором роде, двоичное дерево поиска (BSTree) является структурой данных, которая сама по себе отсортирована и не использует списки для хранения элементов. Основное назначение BSTree — организовать пары узлов ключ = значение в виде дерева, чтобы они оставались отсортированными при вставке или удалении их.Начальная структура BSTree состоит из одного узла ключ=значение, который имеет левый или правый подузел (оба являются ссылками). При вставке нового ключ=значение, задача BSTree заключается в том, чтобы начать со корневого узла и сравнивать ключ нового элемента со всеми узлами: если новый ключ меньше или равен текущему, двигаться влево; если новый ключ больше текущего, двигаться вправо. В конце концов, BSTree находит место в дереве, где, следуя первоначальному пути, вы должны найти этот узел, выполняя ту же процедуру. Все последующие операции выполняются аналогично, путём сравнения любого ключа с каждым узлом, перемещаясь влево или вправо до тех пор, пока не найдёте узел или не достигнете конца. Таким образом, BSTree является альтернативой словаря из упражнения 17, поэтому он должен иметь такие же операции. Базовый узел BSTree будет требовать свойства left, right, key и value для создания структуры дерева. Возможно, вам также понадобится свойство parent, в зависимости от того, как вы реализуете это (Примечание переводчика: если вы записываете родителей при прохождении, то это свойство не требуется). Затем, BSTree должен выполнять следующие операции над корневым узлом BSTree:

• get> Принимает ключ, проходит по дереву, находит узел или возвращает None, если достигнут конец. Если предоставленный ключ меньше или равен ключу текущего узла, то движемся влево. Если ключ больше ключа текущего узла, то движемся вправо. Если вы встретили узел, который не имеет левого или правого потомка, значит, вы завершили прохождение этого пути, и такой узел отсутствует. Можно использовать рекурсивный подход или цикл while.> set

Этот метод практически такой же как get. Единственное отличие состоит в том, что при достижении конечного узла новый узел типа BSTreeNode присоединяется к левому или правому потомку, тем самым продлевая дерево новой веткой.

delete

Удаление узла из BSTree — это сложная операция, поэтому у меня есть отдельный раздел, посвящённый удалению. Кратко говоря, существует три случая: узел является листовым (не имеет потомков), имеет одного потомка или имеет двух потомков. Если узел является листовым, его просто удаляют. Если узел имеет одного потомка, он заменяется этим потомком. Если узел имеет двух потомков, процесс становится более сложным, поэтому прочтите ниже раздел об удалении.

list

Проходит по всему дереву и выводит все узлы. Основной особенностью команды list является возможность проходить по дереву различными способами, что приводит к различным результатам. Например, если вы сначала прошли по левой стороне, а затем по правой, вы получите другой результат, чем если бы вы сделали это в обратном порядке. Если вы прошли по всем путям до самого низа дерева, а затем вернулись к корню, вывод будет другим. Вы также можете выводить узлы во время прохода по дереву от корня до листовых узлов. Попробуйте различные способы прохода и посмотрите, какие результаты они дают.## Удаление

Помните, что при удалении узла нам нужно учитывать три случая (которые я называю D):

• Узел D является "листовым" узлом, так как у него нет потомков (ни левых, ни правых). Его можно просто удалить из родительского узла.
• Узел D имеет только одного потомка (либо левого, либо правого, но не обоих сразу). В этом случае можно переместить значение этого потомка в узел D, после чего удалить этот потомок. Это эквивалентно замене узла D своим потомком (или "перемещению потомка выше").
• Узел D имеет левого и правого потомков, что требует выполнения более сложных действий. Сначала найдите минимальный потомок узла D.right, который станет преемником. Затем установите значение D.key равным значению successor.key, и примените ту же процедуру удаления к потомкам преемника. Вам, скорее всего, также потребуются операции find_minimum и replace_node_in_parent, чтобы выполнить эти два действия. Я упомянул, что вам может понадобиться атрибут parent, в зависимости от того, как вы его реализуете. Я буду предполагать использование узла parent, так как это обычно проще.

Примечание

Удаление узлов из дерева вызывает неприязнь практически у всех. Это сложная операция, которую даже моя любимая книга по алгоритмам — "Руководство по дизайну алгоритмов" Steven S. Skiena — пропускает, потому что её реализация "кажется немного пугающей". Если вам сложно разобраться с delete, не расстраивайтесь.## Часто задаваемые вопросы

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

Секрет решения этой проблемы состоит в том, чтобы сначала перевести английский текст в грубое псевдокод. Затем преобразуйте грубое псевдокод в более точный псевдокод. Как только у вас будет более точный псевдокод, вы сможете перевести его в код Python. Обратите особое внимание на конкретные слова; одно английское слово может означать многое в Python. Иногда вам придется просто сделать догадку и запустить тест, чтобы проверить правильность.

Тестирование тоже очень важно, поэтому применение методологии "тест-первым" для этой задачи может быть хорошей идеей. Вы знаете, что должны выполнять эти операции, поэтому вы можете написать тест для них, а затем позволить тесту работать.

Исследовательское обучение* Можно ли создать патологический тест, который вставляет элементы таким образом, чтобы BSTree был просто усложнённой связным списком?

• Что произойдёт, если вы попытаетесь удалить "вершину" этого BSTree?
• Какова скорость работы BSTree по сравнению с вашим недавно оптимизированным Dictionary?
• С использованием вашего процесса анализа производительности и настройки, насколько быстро вы сможете реализовать BSTree?