Предыдущие две статьи знакомили с исходным кодом и теорией hashmap, сегодня я расскажу об оставшейся части красно-черного дерева. Хорошее понимание красно-черного дерева очень полезно для нашего последующего понимания хэш-карты или других структур данных. Например, почему jdk обновляет односвязный список в хэш-карте до красно-черного дерева?
Чтобы понять красно-черные деревья, мы должны сначала понять некоторые основные концепции обычных бинарных деревьев.
Родительский узел и дочерний узел, я не буду больше говорить об этом. должен знать.
Если родительский узел некоторых дочерних узлов является узлом, то они являются родственными узлами.
Если узел не имеет родителя, он является корневым узлом.
Если узел не имеет дочерних узлов, считать его листовым узлом.
Рассмотрим следующее бинарное дерево:
Aвысота узла: количество ребер от узла A до самого дальнего листового узла. Например, высота узла A здесь равна 3
Eглубина узла: количество ребер от корневого узла A до узла E, которое здесь, очевидно, равно 2, поэтому глубина узла E равна 2.
E Количество слоев узлов: глубина узла E + 1. Таким образом, количество слоев узла E здесь равно 3.
Посмотрите еще раз на эту картинку:
Рисунок 1 называетсяполное бинарное дерево:
Условие 1: все листовые узлы находятся внизу
Условие 2: за исключением листовых узлов, у каждого узла есть 2 левых и правых дочерних узла.
Полное бинарное дерево понять несложно, да и говорить особо нечего. Продолжаем смотреть на рисунок 2,
Рисунок 2 называетсяполное бинарное дерево:
Условие 1: Листовые узлы могут быть только внизу2 слоя.
Условие 2: Листовые узлы последнего слоя располагаются слева.
Условие 3: За исключением последнего слоя, количество дочерних узлов других слоев должно быть максимальным. (Это также можно понимать так: после удаления последнего слоя это должно быть полное бинарное дерево.)
Что ж, кажется, что судить о полном бинарном дереве немного сложно. Это не имеет значения. Давайте потренируемся на нескольких картинках.
Посмотрите еще несколько картинок:
Рисунок 1: Это не полное бинарное дерево, и условие 1 не выполняется. Поскольку второй слой имеет конечный узел
Рисунок 2: Условие 2 не выполнено, последний слой листовых узлов на рисунке 2 повернут вправо.
Рисунок 3: Условие 3 не выполняется, потому что мы обнаружили, что это не полное бинарное дерево после удаления последнего слоя.
Зачем нужно полное бинарное дерево и что эта штука делает? Почему условие 2 требует, чтобы последний слой листовых узлов располагался слева? Вы не можете пойти прямо?
Прежде всего, нам нужно определить понятие,Помимо использования связанных списков, двоичные деревья также могут быть реализованы с использованием массивов.
О бинарном дереве, реализуемом связным списком, говорить особо нечего, их слишком много в интернете, на самом деле структура данных — это поле данных, а затем левый указатель и правый указатель.
Итак, если вы используете для этого массив, как сохранить двоичное дерево? Посмотрите на картинку ниже:
Это легко понять, число представляет собой нижний индекс массива. Например, узел A помещается в позицию [1], узел F помещается в позицию [6], узел I помещается в позицию [9] и т. д.
Итак, после математической индукции мы можем абстрагироваться от следующих правил:
Если бинарное дерево хранится в массиве, следующие правила таблицы, соответствующие узлам, таковы:
Правило 1: Нижний индекс 2*i должен быть левым дочерним узлом.
Правило 2: Если индекс равен 2*i+1, это должен быть правильный дочерний узел.
Правило 3: Узел с индексом i/2 должен быть родительским узлом узла i.
Следовательно, пока мы помещаем корневой узел бинарного дерева в любую позицию массива, мы должны иметь возможность соединить все бинарное дерево последовательно, используя приведенные выше правила, и все это является методом хранения массива бинарного дерева. .
Преимущество использования массива для хранения двоичного дерева заключается в том, что он может сохранить два указателя слева и справа, что может сэкономить место в памяти.
Посмотрите на другую картинку:
Посмотрите на это бинарное дерево, индексы нашего массива 1, 2, 3, 4, 7, 8, 9, 13.
Потрачено 5, 6, 10, 11, 12. Потрачено впустую эти 5 массивов свободного места.
Таким образом, преимущество полного двоичного дерева заключается в том, что оно не тратит пространство массива, поэтому для полного двоичного дерева наиболее подходящим методом является хранение в виде массива.Например, куча использует для хранения массив. структура хранения для бинарного дерева
обход предварительного заказа: Сначала выведите сам узел, затем левое поддерево, затем правое поддерево.
Неупорядоченный обход: левое поддерево - сам узел - правое поддерево
пост-порядковый обход: левое поддерево - правое поддерево - сам узел
Про эти три метода обхода много говорить не буду, много ищу в интернете.
С этими предвзятыми концепциями мы можем продолжать копать глубже.
Что такое бинарное дерево поиска?
бинарное дерево поиска: Для любого узла значение его левого узла должно быть меньше этого узла, а значение его правого узла должно быть больше этого узла.
Затем давайте выполним его операцию поиска и вставки в двоичном дереве поиска. Зачем этому учиться, ведь для большинства структур данных измерение его
Производительность в основном зависит от эффективности поиска и вставки данных. Например, массивы и связанные списки — это две структуры данных с диаметрально противоположной эффективностью поиска и вставки.
Без лишних слов давайте сначала посмотрим, как выполняется операция поиска в бинарном дереве поиска:
На самом деле это тоже очень просто.Для бинарного дерева поиска значение левого узла "родительский узел" правого узла.
Итак, чтобы найти значение, мы просто переходим от вершины бинарного дерева поиска к корневому узлу:
Если это значение больше узла, то перейти в правое поддерево для продолжения рекурсивного поиска, если это значение меньше значения узла, то перейти в левое поддерево для поиска. пока не нашел
Я не буду писать эту рекурсивную функцию, идея алгоритма всем известна, вы можете попрактиковаться сами.
Операция вставки бинарного дерева поиска немного сложнее:
1. Если вставляемое значение больше значения узла, а правое поддерево этого узла пусто, то поместить его непосредственно на позицию правого узла этого узла (обратите внимание, что это конечное условие рекурсия)
2. Если он не пустой, то продолжаем операцию шага 1, пока не найдем соответствующую позицию узла.
- Если вставляемое значение меньше значения узла, а левое поддерево этого узла пусто, то оно помещается непосредственно в позицию левого узла узла. . И так далее. и шаги 1-2 это идея
Видно, что рекурсия является основной идеей реализации алгоритмов, связанных с бинарным деревом.
Кроме того, самый важный момент, давайте рассмотрим характеристики этого бинарного дерева поиска и вы обнаружите: если мы напечатаем это бинарное дерево поиска методом неупорядоченного обхода, то Полученный результат должен быть упорядоченным. Временная сложность o(n)
Поэтому бинарное дерево поиска также называют бинарным отсортированным деревом.
Что делать, если в двоичном дереве поиска есть повторяющиеся данные для вставки?
Вопрос хороший вопрос.Вот 2 решения.Если интересно,можете реализовать.
план 1:
При нормальных обстоятельствах, если мы используем связанный список для реализации двоичного дерева, тогда базовой структурой данных должно быть поле данных и левый и правый указатели, право, затем
Мы можем искусственно добавить поле, называемое дополнительным указателем. Для чего этот указатель? Этот указатель предназначен для объединения повторяющихся данных.
Возьмем, к примеру, следующий пример:
Этот способ обработки немного похож на способ борьбы с хэш-коллизиями в хэш-карте?
Тогда кто-то должен снова спросить, какой смысл вставлять повторяющиеся значения в бинарное дерево поиска?
В реальном производстве структура данных, которую мы храним, не может быть простым значением int, а является объектом, поэтому в каждом объекте должно быть много полей. Например, объект продукта может иметь много полей, цену, название продукта, изображение продукта и т. д. Если в качестве ключевого значения бинарного дерева поиска используется цена товара, Тогда это обязательно произойдет, потому что товары с одинаковой ценой могут быть разными товарами, например, iphone и mate20 оба продаются по 7000 юаней, но очевидно, что это не так. тоже самое
Сценарий 2:
При вставке данных, если обнаруживается, что вставленное значение совпадает со значением узла, то это значение вставляется в позицию правого узла этого узла. (то есть, Вставка значения большего, чем узел, аналогична вставке значения, равного узлу)
Таким образом, ввиду этой ситуации, наш метод поиска необходимо изменить, нельзя сказать, что выход из рекурсии происходит, когда найдено то же значение, что и узел, но после того, как найдено значение того же узла. Продолжайте находить его правое поддерево, чтобы увидеть, есть ли значение, совпадающее с искомым значением, до конечного узла (обратите внимание на условия выхода из рекурсии)
Насколько эффективно бинарное дерево поиска? Выглядит не так хорошо, как хеш-таблица, какой смысл в существовании?
На самом деле, если мы посмотрим на алгоритм бинарного дерева поиска, мы можем получить результат, что его эффективность поиска составляет O(logn), что полностью уступает эффективности поиска по хеш-таблице, O(1). Кроме того, бинарное дерево поиска легко превратить в односвязный список в крайних случаях, поэтому мы все знаем, что эффективность поиска в односвязном списке равна O(N). Это еще медленнее.
Но даже в этом случае бинарное дерево поиска имеет некоторые преимущества, которых нет у хеш-таблицы:
-
Двоичное дерево поиска может легко сортировать данные с обходом по порядку, что невозможно для хэш-таблицы.
-
Когда хеш-таблица сталкивается с хэш-конфликтом, ее необходимо расширить.Эта операция расширения занимает довольно много времени, а производительность иногда нестабильна.Хотя производительность двоичного дерева поиска также нестабильна, Но у нас есть более специальное сбалансированное бинарное дерево поиска, которое может стабилизировать временную сложность на уровне O(logn)
-
Двоичное дерево поиска относительно простое, структура данных понятна с первого взгляда, достаточно рекурсивной рекурсии, но хеш-таблица, как вы знаете, очень сложна в реализации.
Таким образом, вы можете знать, что хэш-карта и бинарное дерево поиска имеют свои преимущества, как их использовать, зависит от реальной ситуации, но вам нужно знать разницу между этими двумя структурами данных. Где плюсы и минусы и почему?
Что за долгожданное красно-черное дерево? Какова связь со сбалансированным бинарным деревом поиска, о котором мы упоминали выше?
Как мы упоминали ранее, обычное бинарное дерево поиска в крайних случаях вырождается в односвязный список, например:
Как видите, этому бинарному дереву поиска очень не повезло, оно все в левой части и совсем не сбалансировано, похоже на односвязный список, на первый взгляд очень медленная структура данных.
Поэтому так называемое сбалансированное бинарное дерево поиска состоит в том, чтобы найти способ, обеспечивающий в процессе вставки, бинарное дерево поиска становится сбалансированным, так называемое сбалансированное То есть не может быть все слева или все справа, лучше всего иметь обе стороны, и чем ближе высоты левого и правого поддеревьев, тем лучше и сбалансированнее. Потому что только тогда наша временная сложность стабилизируется на уровне O(logn)
Существует множество способов реализации сбалансированного бинарного дерева поиска, наиболее известным из которых является красно-черное дерево.Для тех из нас, кто обычно пишет бизнес-код, а не профессиональные алгоритмы Красно-черное дерево может почти представлять собой сбалансированное бинарное дерево поиска, и они бесконечно близки.
Но на что мы должны обратить внимание, так это на то, что красно-черное дерево является приблизительно сбалансированным сбалансированным бинарным деревом поиска, а не строго сбалансированным бинарным деревом.Заинтересованные студенты могут проверить дерево AVL Это строго сбалансированное бинарное дерево, но из-за того, что эта штука слишком строгая, эффективность каждой вставки и удаления слишком низкая, поэтому мало кто использует его в производственной среде.
Что касается конкретной реализации красно-черного дерева, я не буду здесь много говорить, потому что реализация красно-черного дерева более сложна. Я никогда в жизни не напишу красно-черное дерево, если я действительно хочу его использовать, то на самом деле гораздо проще написать таблицу переходов, чем красно-черное дерево. . Также легко понять.
Поэтому заинтересованные студенты могут здесь поискать актуальную информацию о красно-черных деревьях и открыть глаза. Учащимся, которым это не интересно, нужно только знать, что красно-черное дерево представляет собой сбалансированное двоичное дерево поиска, которое для решения структуры данных состоит в том, что обычное двоичное дерево поиска легко вырождается в односвязный список при вставке данных, что сильно снижает КПД. Его высота будет бесконечно близка к log2n, поэтому Эффективность его поиска можно стабилизировать на уровне O(logn). Вот почему реализация hashmap в старшей версии jdk использует красно-черное дерево вместо односвязного списка для разрешения коллизий хешей.