Они похожи на класс ленивых студентов, пытающихся сфальсифицировать свой экзамен.

1656677419 oni pohozhi na klass lenivyh studentov pytayushhihsya sfalsificzirovat svoj ekzamen

Сачин Малхотра

1*tCYpJPPIECnHUWw9BR_vrg
http://blog.noplag.com/wp-content/uploads/2017/01/cheating-on-a-test-clip-art-red-cheating-on-blues-test.png

Представьте, вы зачислены на математический курс одного из самых престижных университетов мира.

У вас совсем скоро экзамен. Очевидно, вы хотите хорошо сдать экзамен.

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

Профессора, чтобы взять под контроль эту проблему, придумали два решения:

  • Количество учащихся в классе никогда не фиксировано. И люди, сидящие в одном классе, сдают тест, сменяют один тест на другой.
  • Рассадка увольняется за пять минут до экзамена. Расположение мест по алфавиту. Но поскольку студенты никогда не фиксируются, а новые могут добавляться или старые изыматься из класса случайным образом, расстановка должна быть четко выпущена, чтобы студенты знали, где они должны сидеть.

Скажем, вы один из тех ленивых студентов, которые хотят списывать, невзирая на последствия. За пять минут до экзамена, когда освобождается рассадка, как можно скорее узнать, кто сидит перед вами, а кто позади?

Вы не сможете обмануть, если не поговорите с этими двумя людьми заранее и не выработаете стратегию, верно?

Рассадка

Профессора обнародовали рассадку для первого теста, который когда-либо проводился таким образом. Скажем, в нем было N учащихся. Если бы эти студенты оставались неизменными от одного экзамена к другому, их было бы очень легко обмануть, не правда ли? Потому что рассадка мест всегда производится по алфавиту.

Поэтому профессора продолжают добавлять или удалять студентов из этого списка от одного теста к другому и выпускают эти изменения только перед каждым тестом. Таким образом, студенты никогда не могли точно знать перед экзаменом, кто будет сидеть впереди или сзади них.

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

Имея список модификаций в любое заданное время T и имя N, нам нужно определить элементы B и A, чтобы B стоял непосредственно перед N, а A – сразу после N, если список нужно отсортировать.

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

О, Аррей, мой старый друг, ты поможешь мне?

Использование массива кажется достаточно обычным подходом.

  • Мы можем просто поместить все имена из уволенного списка в массив.
  • Затем мы сортируем все имена (список выпущенных имен может быть упорядочен случайным образом) по лексикографии
  • И тогда мы можем найти свое имя в списке с помощью бинарной процедуры поиска. Это дало бы нам предшественника и преемника.

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

Мы можем отсортировать список в первый раз, затем продолжать добавлять новые элементы и соответственно удалять старые, двигаясь дальше.

Однако сложность добавления или удаления элемента из массива чрезвычайно высока. O(n) . Поскольку количество студентов может быть очень большим, и мы не знаем, сколько модификаций будет перед новым тестом, это займет много времени, и тест начнется до того, как мы сможем решить проблему. Помните, что модификации получаются всего за пять минут до теста.

Какую еще структуру данных мы имеем, где вставка и удаление можно сделать очень быстро?

Хммм, возможно, Linked List все-таки является моим настоящим другом

Что касается связанного списка, то у него есть собственный набор проблем при разрешении ситуации такого типа. Сначала нам нужно отсортировать список элементов лексикографически. Поскольку это одноразовая операция, поскольку ее нужно делать только для первого экзамена, время, затраченное здесь, не имеет особого значения.

Из следующего экзамена выпускаются только модификации. Добавление или удаление элемента из связанного списка является операцией в постоянном времени, если мы знаем расположение этого элемента в списке.

Поиск элемента в связанном списке – это линейная операция времени – она занимает O(n) . Я знаю, что существуют такие понятия как списки пропуска, но зачем погружаться в нечто подобное, когда мы можем решить эту проблему гораздо лучше, используя другой тип структуры данных?

Введите Binary Search Trees, новичка в городе

Давайте рассмотрим, как мы можем моделировать наши данные с помощью бинарного дерева поиска (BST). Тогда мы увидим, как BST может помочь нам решить проблему, которую мы изначально решили.

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

Для узла с ключом kкаждый ключ в левом поддеревье меньше k и каждый ключ в правом поддеревье больше чем k.

В нашем случае ключами будут имена учащихся.

Рассмотрим следующий пример, чтобы увидеть, как строится бинарное дерево поиска. Это должно придать большую ясность структуре данных.

1*fvAa2lIvPcl3pEF0EwjT_g
http://btechsmartclass.com/DS/images/BST%20Construction.png

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

1*4rHcryjV-ySjXORcxzqQeA
Перекошенное влево бинарное дерево поиск.

Это известно как скошенное бинарное дерево поиска. Если такое случается, то BST фактически превращается в связанный список, и это нам ни при чем. Поэтому у нас есть такое представление о сбалансированности BST, чтобы не столкнуться с этой проблемой.

Понятие сбалансированности определяется различными подходами, такими как красные черные деревья или деревья AVL. Дальнейшее объяснение этих деревьев выходит за рамки данной статьи.

Возвращаясь к упорядочению наших данных в сбалансированном BST: ключами нашего BST будут имена студентов, а лексикографическое сопоставление будет использовано для определения структуры BST.

Предположим, что тест сдали миллион студентов. Если наше двоичное дерево поиска сбалансировано, то сложность выполнения любой операции ограничена верхним пределом. O(log(n)) . Следовательно, для 1 миллиона узлов максимальное количество узлов для сканирования будет всего 14.

1*WX_no1yjkuvyro78viF21w

Это значительно уменьшает сложность, просто упорядочивая данные определенным образом. Это преимущество представления данных в a сбалансированный Двоичное дерево поиск.

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

Что касается сбалансированного бинарного дерева поиска, то время, которое нужно вставить, удалить или найти элемент, ограничено O(log(n)) . И именно это делает эту структуру данных очень увлекательной.

Однако мы до сих пор не решили нашу первоначальную проблему. Учитывая имя студента, мы хотим найти студента, сидящего позади и прямо перед ними. Это сводится к поиску последователь и предшественник в заданном бинарном дереве поиска.

Обход в порядке и порядке сортировки в BST

Интересным свойством бинарных деревьев поиска есть то, что мы можем получать элементы в отсортированном порядке (даже в обратном порядке), выполняя порядковый обход дерева бинарного поиска.

Таким образом, порядковый преемник узла X – это элемент, который следует сразу после X в порядковом обходе над данным BST. Для нашей проблемы мошенничества этим преемником в порядке будет сидящий перед нами студент.

Предшественник узла X по порядку – это элемент, который стоит непосредственно перед X в обходе за порядком (или элемент, который следует сразу после X в обратный обход в порядке) над данным BST. Для нашей проблемы со списыванием этим предшественником в порядке будет студент, сидящий прямо за нами.

Преемник в BST

Есть два разных случая, которые нам нужно рассмотреть, когда находим порядкового преемника узла в BST.

Первый случай когда существует правильный дочерний элемент для узла, преемника которого мы пытаемся найти. Рассмотрим следующий пример.

1*HT_4eHf-yWORRyajZGfbqg

Здесь мы хотели найти порядкового преемника выделенного узла 8. Поскольку он имеет правый дочерний элемент, преемником в порядке будет крайний левый узел в дереве с правым дочерним узлом или 15 как корневой.. Следовательно, в этом случае этот узел будет 10.

Второй случай это когда нет правильного ребенка.

1*z6Q879IxNa5B6jRC6s1CaQ

В этом случае преемник по порядку имеет две возможности:

  1. Одна из них заключается в том, что рассматриваемый узел является левым потомком своего отца. В этом случае правопреемником по порядку будет сам отец. Следовательно, для нашего данного случая преемник по порядку будет 10.
  2. Второй случай, когда текущий узел является правым дочерним элементом отца. И у него нет правильного ребенка. Следовательно, это крайний правый узел у BST, и у него нет преемника по порядку.

Обработка первого случая достаточно проста для бинарного дерева поиска. Во втором случае, когда заданный узел не имеет правильного дочернего элемента (или каких-либо родительских указателей), нам придется полагаться на наш старый добрый механизм рекурсии и выполнять обход в порядке, пока мы не выясним родительский элемент нашего заданного узла.

Следовательно, сложность в худшем случае может быть O(n), если имеет место случай, приведенный выше.

Используя этот алгоритм, мы можем быстро узнать студента, который будет сидеть прямо перед нами на экзамене.

Предшественник у BST

Это полная противоположность предыдущему случаю.

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

1*8LEzigzWixE_psr5BDeqdA

Это тот случай, когда узел имеет левый дочерний элемент. Нам нужно найти крайний правый дочерний элемент дерева с корнем в этом левом дочернем элементе — крайний правый узел в дереве с корнем 2.

1*MXJ1lCqihi0bmcfelm5WFA

Без левого ребенка. Потому нам нужно найти отца.

Если вы внимательно присмотритесь, я только что изменил порядок обхода здесь, а остальной код такой же, как и раньше. (ПРИМЕЧАНИЕ: этот код используется, когда нет левого дочернего узла, для которого мы хотим найти предшественника по порядку).

Предшественник в установленном порядке становится обратным преемником в установленном порядке.

Ну, теперь, когда вы знаете, как вы должны организовать список мест для сидения в классе, получите хорошие оценки???. Шучу!! Обман – это плохо – никогда этого не делайте!

Надеюсь, вы поняли основную идею различных способов использования структур данных и как найти последователя и предшественника в BST.

РЕДАКТИРОВАТЬ: Благодарность Деви Годаял за то, что она указала на ряд серьезных ошибок в начальном черновике, а также за то, что статья была хорошо оформлена 🙂 🙂

Добавить комментарий

Ваш адрес email не будет опубликован.