Структуры

Сортировка выбором

06.07.2020 02:17:13 |

Автор: admin

Всем привет. Эту статью я написал специально к запуску курса Алгоритмы и структуры данных от OTUS.

Введение

Сортировка массива является одной из первых серьезных задач, изучаемых в классическом курсе Алгоритмы и структуры данных дисциплины computer science. В связи с этим задачи на написание сортировок и соответствующие вопросы часто встречаются на собеседованиях на позиции стажера или junior разработчика.

Постановка задачи

Традиционно стоит начать изложение решений задачи с ее постановки. Обычно задача сортировки предполагает упорядочивание некоторого массива целых чисел по возрастанию. Но на самом деле, это является некоторым упрощением. Излагаемые в этом разделе алгоритмы можно применять для упорядочивания массива любых объектов, между которыми установлено отношение порядка (то есть про любые два элемента можно сказать: первый больше второго, второй больше первого или они равны). Упорядочивать можно как по возрастанию, так и по убыванию. Мы же воспользуемся стандартным упрощением.

Сортировка выбором

Одной из простейших сортировок является сортировка выбором.

Описание алгоритма

Сортировка массива выбором осуществляется так: массив делится на две части. Одна из частей называется отсортированной, а другая неотсортированной. Алгоритм предполагает проход по всему массиву с тем, чтобы длина отсортированной части стала равна длине всего массива. В рамках каждой итерации мы находим минимум в неотсортированной части массива и меняем местами этот минимум с первым элементом неотсортированной части массива. После чего мы увеличиваем длину отсортированной части массива на единицу. Пример осуществления одной итерации представлен ниже:
1 3 5 | 8 9 6 -> 1 3 5 6 | 9 8

Реализация

Предлагаю посмотреть на реализацию данного алгоритма на языке C:

void choiseSortFunction(double A[], size_t N){    for(size_t tmp_min_index = 0; tmp_min_index < N;                                  tmp_min_index++) {        //ищем минимум        for(size_t k = tmp_min_index + 1; k < N; k++) {            if (A[k] < A[tmp_min_index]) {                double min_value = A[k];                A[k] = A[tmp_min_index];                A[tmp_min_index] = min_value;            }        }    }}

Анализ

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

$display$

В процессе вычислений, мы воспользовались сначала свойствами О нотации, а затем формулой для вычисления суммы арифметической прогрессии.

Для порядка необходимо оценить еще и дополнительную память, которая требуется для выполнения алгоритма. Здесь все гораздо проще: мы выделяли память только для счетчиков цикла и переменной буфера, позволяющей обменивать 2 элемента массива местами. Поэтому:

$display$

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

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

Двусторонняя сортировка выбором

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

Рекурсивная сортировка выбором

В качестве упражнения можно попробовать написать алгоритм не с использованием цикла, а с использованием рекурсии. На java это может выглядеть следующим образом:

public static int findMin(int[] array, int index){    int min = index - 1;    if(index < array.length - 1) min = findMin(array, index + 1);    if(array[index] < array[min]) min = index;    return min;}  public static void selectionSort(int[] array){    selectionSort(array, 0);}  public static void selectionSort(int[] array, int left){    if (left < array.length - 1) {        swap(array, left, findMin(array, left));        selectionSort(array, left+1);    }}  public static void swap(int[] array, int index1, int index2) {    int temp = array[index1];    array[index1] = array[index2];    array[index2] = temp;}

Итоги

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

Если вы хотите подробнее узнать о курсе, приглашаю всех на бесплатный вебинар, который пройдет уже 10 июля.

Подробнее..

Категории: Программирование , Алгоритмы , Высокая производительность , Промышленное программирование , Блог компании otus. онлайн-образование , Собеседование , Сортировка , Структуры , Данных , Линейная , Квадратичная , Устойчивость , Поразрядная

Сортировка вставками

09.07.2020 12:23:49 |

Автор: admin

Всем привет. Сегодня продолжаем серию статей, которые я написал специально к запуску курса Алгоритмы и структуры данных от OTUS.

Введение

Сортировка массива является одной из первых серьезных задач, изучаемых в классическом курсе Алгоритмы и структуры данных дисциплины computer science. В связи с этим задачи на написание сортировок и соответствующие вопросы часто встречаются на собеседованиях на позиции стажера или junior разработчика.

Постановка задачи

Традиционно стоит начать изложение решений задачи с ее постановки. Обычно задача сортировки предполагает упорядочивание некоторого массива целых чисел по возрастанию. Но на самом деле, это является некоторым упрощением. Излагаемые в этом разделе алгоритмы можно применять для упорядочивания массива любых объектов, между которыми установлено отношение порядка (то есть про любые два элемента можно сказать: первый больше второго, второй больше первого или они равны). Упорядочивать можно как по возрастанию, так и по убыванию. Мы же воспользуемся стандартным упрощением.

Сортировка вставками

В прошлый раз мы поговорили об одной из простейших сортировок сортировке выбором. Сегодня речь пойдет о несколько более сложном алгоритме сортировке вставками.

Описание алгоритма

Сортировка массива вставками осуществляется так: также как и в случае сортировки выбором массив делится на две части. Одна из частей называется отсортированной, а другая неотсортированной. Алгоритм предполагает проход по всему массиву с тем, чтобы длина отсортированной части стала равна длине всего массива. В рамках каждой итерации мы берем первый элемент неотсортированной части массива и осуществляем с ним следующую операцию: пока наш элемент строго меньше чем предыдущий меняем их местами. После чего увеличиваем длину отсортированной части массива на единицу. Таким образом путем последовательного перемещения изучаемого элемента мы добиваемся того, чтобы он встал на свое место. Пример осуществления одной итерации представлен ниже:
1 3 5 | 2 9 6 -> 1 3 2 5 9 6 -> 1 2 3 5 9 6 -> 1 2 3 5 | 9 6

Реализация

Предлагаю посмотреть на реализацию данного алгоритма на языке C:

void insertionSortFunction(double array[], int size) {    int i, j, temp;    // i представляет длину отсортированной части массива, начинаем с 1, потому что один элемент сам по себе считается упорядоченным    for (i = 1; i < size; i++) {        temp = array[i];        for (j = i - 1; j >= 0; j--) {            if (array[j] < temp) {                break;            }              array[j + 1] = array[j];            array[j] = temp;        }    }}

Анализ

Предлагаю проанализировать данный алгоритм.

Начать анализ проще всего будет с получения асимптотики памяти. Независимо от длины и структуры предлагаемого для сортировки массива выделяется память только для двух счетчиков цикла и одной вспомогательной переменной, служащей для осуществления обмена двух переменных значениями. Таким образом всегда верно:

$display$

.

Со временем все несколько интереснее. Тело внутреннего цикла само по себе выполняется за O(1), то есть не зависит от размера сортируемого массива. Это означает, что для понимания асимптотики алгоритма необходимо посчитать сколько раз выполняется это тело. Но количество итераций внутреннего цикла зависит от того, насколько хорошо упорядочены (или не упорядочены) элементы сортируемого массива. Для осуществления анализа необходимо посмотреть несколько случаев.

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

$display$

Таким образом, сортировка осуществляется за линейное время.

В худшем случае число итераций предполагается наибольшим, то есть break никогда не срабатывает. На первой итерации внешнего цикла осуществляется одна итерация внутреннего цикла. На второй итерации внешнего цикла осуществляется 2 итерации внутреннего цикла. Продолжая рассуждение дальше, можно прийти к тому, что на последней ((n 1) ой) итерации внешнего цикла выполниться (n 1) итерация внутреннего цикла. Получаем:

$display$

Для осуществления вычислений мы воспользовались свойствами О нотации и формулой суммы арифметической прогрессии.

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

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

. То есть мы просто подсчитываем сколько раз выполняется тело внутреннего цикла. Таким образом, получаем

.

Если подводить итоги, то асимптотика алгоритма по памяти

$display$

по времени в лучшем случае

$display$

и в среднем и в худшем случаях

$display$

Поэтому данную сортировку относят к классу квадратичных сортировок.

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

Итоги

Мы рассмотрели еще одну квадратичную сортировку: сортировку вставками, посмотрели на ее устойчивую реализацию. Сортировка является преимущественно учебной, хотя на практике она может применяться благодаря неплохой асимптотике в лучшем случае: если к достаточно большому упорядоченному объему данных понадобится добавить новые данные так, чтобы все данные были опять упорядочены, может пригодится внутренний цикл for. Таким образом, можно поддерживать за

$display$

упорядоченность объема данных.

Узнать о курсе подробнее.

Подробнее..

Категории: Программирование , Алгоритмы , Высокая производительность , Промышленное программирование , Блог компании otus. онлайн-образование , Собеседование , Сортировка , Структуры , Данных , Линейная , Квадратичная , Устойчивость , Поразрядная , Вставками

Быстрая сортировка

25.10.2020 18:16:57 |

Автор: admin

Всем привет. Сегодня продолжаем серию статей, которые я написал специально к запуску курса Алгоритмы и структуры данных от OTUS. По ссылке вы сможете подробно узнать о курсе, а также бесплатно посмотреть запись Demo-урока по теме: Три алгоритма поиска шаблона в тексте.

Введение

Сортировка массива является одной из первых серьезных задач, изучаемых в классическом курсе Алгоритмы и структуры данных дисциплины computer science. В связи с этим задачи на написание сортировок и соответствующие вопросы часто встречаются на собеседованиях на позиции стажера или junior разработчика.

Постановка задачи

Традиционно стоит начать изложение решений задачи с ее постановки. Обычно задача сортировки предполагает упорядочивание некоторого массива целых чисел по возрастанию. Но на самом деле, это является некоторым упрощением. Излагаемые в этом разделе алгоритмы можно применять для упорядочивания массива любых объектов, между которыми установлено отношение порядка (то есть про любые два элемента можно сказать: первый больше второго, второй больше первого или они равны). Упорядочивать можно как по возрастанию, так и по убыванию. Мы же воспользуемся стандартным упрощением.

Быстрая сортировка

В прошлый раз мы поговорили о чуть более сложной сортировке сортировке вставками. Сегодня речь пойдет о существенно более сложном алгоритме быстрой сортировке (еще ее называют сортировкой Хоара).

Описание алгоритма

Алгоритм быстрой сортировки является рекурсивным, поэтому для простоты процедура на вход будет принимать границы участка массива от l включительно и до r не включительно. Понятно, что для того, чтобы отсортировать весь массив, в качестве параметра l надо передать 0, а в качестве r n, где по традиции n обозначает длину массива.

В основе алгоритма быстрой сортировке лежит процедура partition. Partition выбирает некоторый элемент массива и переставляет элементы участка массива таким образом, чтобы массив разбился на 2 части: левая часть содержит элементы, которые меньше этого элемента, а правая часть содержит элементы, которые больше или равны этого элемента. Такой разделяющий элемент называется пивотом.

Реализация partiion'а:

partition(l, r):

pivot = a[random(l ... r - 1)]

m = l

for i = l ... r - 1:

if a[i] < pivot:

swap(a[i], a[m])

m++

return m

Пивот в нашем случае выбирается случайным образом. Такой алгоритм называется рандомизированным. На самом деле пивот можно выбирать самым разным образом: либо брать случайный элемент, либо брать первый / последний элемент учатка, либо выбирать его каким-то умным образом. Выбор пивота является очень важным для итоговой сложности алгоритма сортировки, но об этом несколько позже. Сложность же процедуры partition O(n), где n = r l длина участка.

Теперь используем partition для реализации сортировки:

Реализация partiion'а:

sort(l, r):

if r - l = 1:

return

m = partition(l, r)

sort(l, m)

sort(m, r)

Крайний случай массив из одного элемента обладает свойством упорядоченности. Если массив длинный, то применяем partition и вызываем процедуру рекурсивно для двух половин массива.

Если прогнать написанную сортировку на примере массива 1 2 2, то можно заметить, что она никогда не закончится. Почему так получилось?

При написании partition мы сделали допущение все элементы массива должны быть уникальны. В противном случае возвращаемое значение m будет равно l и рекурсия никогда не закончится, потому как sort(l, m) будет вызывать sort(l, l) и sort(l, m). Для решения данной проблемы надо массив разделять не на 2 части (< pivot и >= pivot), а на 3 части (< pivot, = pivot, > pivot) и вызывать рекурсивно сортировку для 1-ой и 3-ей частей.

Анализ

Предлагаю проанализировать данный алгоритм.

Временная сложность алгоритма выражается через нее же по формуле: T(n) = n + T(a * n) + T((1 a) * n). Таким образом, когда мы вызываем сортировку массива из n элементов, тратится порядка n операций на выполнение partition'а и на выполнения себя же 2 раза с параметрами a * n и (1 a) * n, потому что пивот разделил элемент на доли.

В лучшем случае a = 1 / 2, то есть пивот каждый раз делит участок на две равные части. В таком случае: T(n) = n + 2 * T(n / 2) = n + 2 * (n / 2 + 2 * T(n / 4)) = n + n + 4 * T(n / 4) = n + n + 4 * (n / 4 + 2 * T(n / 8)) = n + n + n + 8 * T(n / 8) =. Итого будет log(n) слагаемых, потому как слагаемые появляются до тех пор, пока аргумент не уменьшится до 1. В результате T(n) = O(n * log(n)).

В худшем случае a = 1 / n, то есть пивот отсекает ровно один элемент. В первой части массива находится 1 элемент, а во второй n 1. То есть: T(n) =n + T(1) + T(n 1) = n + O(1) + T(n 1) = n + O(1) + (n 1 + O(1) + T(n 2)) = O(n^2). Квадрат возникает из-за того, что он фигурирует в формуле суммы арифметической прогрессии, которая появляется в процессе расписывания формулы.

В среднем в идеале надо считать математическое ожидание различных вариантов. Можно показать, что если пивот делит массив в отношении 1:9, то итоговая асимптотика будет все равно O(n * log(n)).

Сортировка называется быстрой, потому что константа, которая скрывается под знаком O на практике оказывается достаточно небольшой, что привело к широкому распространению алгоритма на практике.

Подробнее..

Категории: Программирование , Алгоритмы , Высокая производительность , Промышленное программирование , Блог компании otus. онлайн-образование , Собеседование , Сортировка , Структуры , Данных , Линейная , Квадратичная , Устойчивость , Поразрядная , Вставками

Понимаем красно-черное дерево. Часть 2. Балансировка и вставка

14.05.2021 00:09:24 |

Автор: admin

Это вторая часть из серии статей "Понимаем красно-черное дерево". Если вы пропустили первую часть, настоятельно рекомендую ознакомиться с ней здесь. Там мы разобрали причину появления кчд и расставили по полочкам некоторые его свойства.

В данной части мы разберем вставку и балансировку. Эти вещи идут бок о бок, без балансировки дерево будет терять свои свойства, и толка от него будет мало.

Держа в голове, что кчд - это 2-3 дерево (иногда я буду напоминать об этом), мы сразу начнем с его построения. Но некоторые уточнения все же нужны сейчас.

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

Также давайте разберемся с тремя операциями, которые понадобятся нам при балансировке. Я прошу не задумываться о них сейчас и вникнуть подробнее уже во время построения дерева. Я приведу их описание здесь, чтобы они не мешались потом:)

Первые две операции - это операции поворота. Эти операции также известны как малый левый и правый поворот, например, для АВЛ-дерева. Логика та же, но дополняется все это работой с цветами нод. Третья операция специализирована для кчд деревьев - это переворот цвета или свап цвета.

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

Левосторонний поворот(левый малый поворот)

Здесь мы будем поворачивать наш узел влево. Картинка иллюстрирует поворот операцию.

иллюстрация левого поворота

В первую очередь мы видим, что parentNode (здесь parentNode - это x, childNode - y) не только меняется местом с childNode, но и цветом. Но! Важно уточнить, что, если childNode принимает цвет своего родителя, то цвет parentNode всегда определяется как красный, независимо от предыдущего цвета потомка (левосторонний поворот просходит только тогда, когда цвет childNode - красный, поэтому нам легче сказать, что parentColor = RED, нежели свапать значения). Также обратите внимание на "переезд" левых потомков childNode (да, вам понадобится tempNode). Тут все так же логично, и это не нарушает баланс. Те потомки, что меньше childNode, больше parentNode, и childNode, соответственно, имеют такое же отношение (меньше/больше) к parentNode, как parentNode к своему родителю.

Правосторонний поворот(малый правый поворот)

Тот же поворот, но в другую сторону. Логика аналогична левостороннему.

иллюстрация правого поворота

Свап цвета

Свап цвета применяется тогда, когда у parentNode два красных потомка. Потомки становятся черными, а parentNode - красным. Операция легкая, обсуждать тут нечего.

Важно сказать, что все три операции изменяют дерево только локально (свап цвета изменяет ноду на уровень выше, но мы считаем это локальным изменением), и вызываем мы их на уровне parentNode! Мы не теряем сбалансированность на других этажах (если она была). В этом вы можете убедиться самостоятельно.

Построение красно-черного дерева.

Итак, начнем построение нашего дерева.

Сначала добавим корень со значением 24. Тут как всегда все просто. Вы помните, что все добавленные ноды имеют красный цвет, кроме корня дерева.

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

Нода со значением 1 становится потомком ноды 5. Здесь мы видим две идущие подряд красные ноды. В таком случае, нам нужно совершить нашу первую балансировку!

спойлер

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

В конце этой части я приведу алгоритм и порядок проверок и выполнений операции балансировки для кчд. Но для того, чтобы вы поняли балансировку, а не просто запомнили, давайте попробуем покопаться сами.

Итак, в нашем арсенале 3 операции: правостороний поворот, левостороений поворот, свап цветов.

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

Давайте пока просто попробуем подставить наши операции. Свап цвета нам не подходит - для свапа нужно два потомка с красным цветом. Левостороний поворот не имеет смысла, так как красных нод справа нет. Остается один вариант - правостороний поворот в ноде 24. Итог вы видите на картинке.

Теперь мы видим, что у корня два красных потомка. Вот здесь то нам и понадобится операция свапа цвета! Результат ниже. (По правилам свапа нода 24 должна была стать красной, но так как это корень, цвет снова стал черным)

В итоге у нас снова корректное левосторонее кчд (и даже без красных нод)! А вот как это выглядело бы в 2-3 дереве.

На картинке видно, что в 2-3 дереве нам нужно меньше операций ("просачивание" ноды против поворота + свапа), но это не значит, что на практике сортировать его проще:) Операции вращения, кстати, не имеют аналогов с операциями 2-3 дерева, а операция свапа цвета - это, по сути, наше "просачивание" значения наверх.

Двигаемся дальше. Вставляем значение 15. Нода уходит в левого потомка ноды 24. Здесь балансировка не нужна.

Вставляем 3. Нода будет меньше корня, но уже больше 1, поэтому нода становится правым потомком ноды-1.

Как мы видим, красная нода находится справа. И снова балансировка. В прошлый раз нас спасла комбинация правосторонний поворот + свап цвета. В этот раз поворот в право нас не спасет (как и свап цвета, я думаю, это очевидно). Сделаем поворот влево и посмотрим, что получится.

Вуаля! Наше дерево снова корректно.

Я думаю, что уже сейчас вырисовываются какие-то правила и закономерности действий, но давайте не будем торопиться и рассмотрим еще пару примеров.

Последнее наше значение - 8. Куда оно встанет, догадайтесь сами. Результат мы видим на картинке. Такая ситуация нам уже встречалась, и мы знаем, что делать.

Правосторонний поворот + свап цвета дает нам следующий результат.

Видим, что на нашем уровне(нода 15) ситуация стала лучше - сама нода красная, оба потомка черного цвета. Условия валидны. Поднимаясь на уровень выше, мы снова видим проблему - красная нода справа. Как это решить мы также знаем. Левосторонний поворот!

Ожидаемый итог - снова корректное левостороннее красно-черное дерево.

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

Вот в целом и все. За исключением пары моментов, построение дерева будет выглядеть примерно так. Как и в случае 2-3 дерева попробуйте сейчас сами добавить пару значений в дерево (ноды 13 и 16, например, интересный случай).

Как я уже говорил выше - операция балансировки это дело локальное, поэтому мы не думаем и не должны думать о том, что происходит на этаж выше\ниже. Это очень удобно при написании кода.

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

Алгоритм балансировки кчд

если правая нода красная и левая нода черная - левостороний поворот
если левая нода красная и левая нода левой ноды красная - правосторонний поворот
если левая нода красная и правостороняя нода красная - делаем свап цветаВсе использования операций логичны - вращаем ноду влево, если красная нода справа. Вращаем ноду вправо, если две красные ноды идут подряд, чтобы потом сделать свап цвета. Не старайтесь запомнить это, постарайтесь понять!

Теперь вы можете пробежаться по построению дерева еще раз и проанализировать, свериться со свойствами из первой статьи, задаться вопросами "а что будет если...?" (поверьте, это очень полезно!). В целом, это все, что я хотел рассказать вам про вставку ноды в левостороннее красно-черное дерево.

Немного об операции поиска значения

Операция получения ничем не будет отличаться от поиска в любом другом бинарном дереве - цвет тут никак не учавствует.

Заключение

На этом я закончу нашу вторую часть про вставку и балансировку кчд. Задавайте свои вопросы, критикуйте и дополняйте статью ниже! В заключительной, третьей, части я расскажу про самую сложную тему красно-черного дерева - удаление элемента. До встречи:)Все использования операций логичны - вращаем ноду влево, если красная нода справа. Вращаем ноду вправо, если две красные ноды идут подряд, чтобы потом сделать свап цвета. Не старайтесь запомнить это, постарайтесь понять!

Теперь вы можете пробежаться по построению дерева еще раз и проанализировать, свериться со свойствами из первой статьи, задаться вопросами "а что будет если...?" (поверьте, это очень полезно!). В целом, это все, что я хотел рассказать вам про вставку ноды в левостороннее красно-черное дерево.

Немного об операции поиска значения

Операция получения ничем не будет отличаться от поиска в любом другом бинарном дереве - цвет тут никак не учавствует.

Заключение

На этом я закончу нашу вторую часть про вставку и балансировку кчд. Задавайте свои вопросы, критикуйте и дополняйте статью ниже! В заключительной, третьей, части я расскажу про самую сложную тему красно-черного дерева - удаление элемента. До встречи:)Все использования операций логичны - вращаем ноду влево, если красная нода справа. Вращаем ноду вправо, если две красные ноды идут подряд, чтобы потом сделать свап цвета. Не старайтесь запомнить это, постарайтесь понять!

Теперь вы можете пробежаться по построению дерева еще раз и проанализировать, свериться со свойствами из первой статьи, задаться вопросами "а что будет если...?" (поверьте, это очень полезно!). В целом, это все, что я хотел рассказать вам про вставку ноды в левостороннее красно-черное дерево.

Немного об операции поиска значения

Операция получения ничем не будет отличаться от поиска в любом другом бинарном дереве - цвет тут никак не учавствует.

Заключение

На этом я закончу нашу вторую часть про вставку и балансировку кчд. Задавайте свои вопросы, критикуйте и дополняйте статью ниже! В заключительной, третьей, части я расскажу про самую сложную тему красно-черного дерева - удаление элемента. До встречи:)Все использования операций логичны - вращаем ноду влево, если красная нода справа. Вращаем ноду вправо, если две красные ноды идут подряд, чтобы потом сделать свап цвета. Не старайтесь запомнить это, постарайтесь понять!

Теперь вы можете пробежаться по построению дерева еще раз и проанализировать, свериться со свойствами из первой статьи, задаться вопросами "а что будет если...?" (поверьте, это очень полезно!). В целом, это все, что я хотел рассказать вам про вставку ноды в левостороннее красно-черное дерево.

Немного об операции поиска значения

Операция получения ничем не будет отличаться от поиска в любом другом бинарном дереве - цвет тут никак не учавствует.

Заключение

На этом я закончу нашу вторую часть про вставку и балансировку кчд. Задавайте свои вопросы, критикуйте и дополняйте статью ниже! В заключительной, третьей, части я расскажу про самую сложную тему красно-черного дерева - удаление элемента. До встречи:)Все использования операций логичны - вращаем ноду влево, если красная нода справа. Вращаем ноду вправо, если две красные ноды идут подряд, чтобы потом сделать свап цвета. Не старайтесь запомнить это, постарайтесь понять!

Теперь вы можете пробежаться по построению дерева еще раз и проанализировать, свериться со свойствами из первой статьи, задаться вопросами "а что будет если...?" (поверьте, это очень полезно!). В целом, это все, что я хотел рассказать вам про вставку ноды в левостороннее красно-черное дерево.

Немного об операции поиска значения

Операция получения ничем не будет отличаться от поиска в любом другом бинарном дереве - цвет тут никак не учавствует.

Заключение

На этом я закончу нашу вторую часть про вставку и балансировку кчд. Задавайте свои вопросы, критикуйте и дополняйте статью ниже! В заключительной, третьей, части я расскажу про самую сложную тему красно-черного дерева - удаление элемента. До встречи:)

Все использования операций логичны - вращаем ноду влево, если красная нода справа. Вращаем ноду вправо, если две красные ноды идут подряд, чтобы потом сделать свап цвета. Не старайтесь запомнить это, постарайтесь понять!

Теперь вы можете пробежаться по построению дерева еще раз и проанализировать, свериться со свойствами из первой статьи, задаться вопросами "а что будет если...?" (поверьте, это очень полезно!). В целом, это все, что я хотел рассказать вам про вставку ноды в левостороннее красно-черное дерево.

Немного об операции поиска значения

Операция получения ничем не будет отличаться от поиска в любом другом бинарном дереве - цвет тут никак не учавствует.

Заключение

На этом я закончу нашу вторую часть про вставку и балансировку кчд. Задавайте свои вопросы, критикуйте и дополняйте статью ниже! В заключительной, третьей, части я расскажу про самую сложную тему красно-черного дерева - удаление элемента. До встречи:)

Подробнее..

Категории: C++ , Структуры , Бинарные деревья

	Русский
	English

Структуры

Сортировка выбором

Введение

Постановка задачи

Сортировка выбором

Описание алгоритма

Реализация

Анализ

Двусторонняя сортировка выбором

Рекурсивная сортировка выбором

Итоги

Сортировка вставками

Введение

Постановка задачи

Сортировка вставками

Описание алгоритма

Реализация

Анализ

Итоги

Быстрая сортировка

Введение

Постановка задачи

Быстрая сортировка

Описание алгоритма

Анализ

Читать ещё:

Понимаем красно-черное дерево. Часть 2. Балансировка и вставка

Левосторонний поворот(левый малый поворот)

Правосторонний поворот(малый правый поворот)

Свап цвета

Построение красно-черного дерева.

Немного об операции поиска значения

Заключение

Немного об операции поиска значения

Заключение

Немного об операции поиска значения

Заключение

Немного об операции поиска значения

Заключение

Немного об операции поиска значения

Заключение

Немного об операции поиска значения

Заключение

Категории

Последние комментарии