Красно-черные деревья
https://stackoverflow.com/questions/20734
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я видел бинарные деревья и бинарный поиск, упомянутые в нескольких книгах, которые я прочитал в последнее время, но, поскольку я все еще начинаю изучать информатику, мне еще предстоит пройти курс, который действительно посвящен алгоритмам и данным. структуры серьезным образом.
Я проверил типичные источники (Википедия, Google), и большинство описаний полезности и реализации (в частности) красно-черных деревьев оказались запутанными и трудными для понимания.Я уверен, что для человека с необходимым опытом это имеет смысл, но на данный момент это читается почти как иностранный язык.
Так что же делает двоичные деревья полезными в некоторых типичных задачах, которые вы выполняете во время программирования?Помимо этого, какие деревья вы предпочитаете использовать (пожалуйста, приложите пример реализации) и почему?
Решение
Красно-черные деревья хороши для создания хорошо сбалансированных деревьев.Основная проблема с двоичными деревьями поиска заключается в том, что их очень легко сделать несбалансированными.Представьте, что ваше первое число — 15.Тогда все последующие числа становятся все меньше 15.У вас будет дерево, которое очень тяжелое с левой стороны и ничего не имеет с правой стороны.
Красно-черные деревья решают эту проблему, заставляя ваше дерево балансироваться всякий раз, когда вы вставляете или удаляете.Это достигается посредством серии ротаций между узлами-предками и дочерними узлами.Алгоритм на самом деле довольно простой, хотя и немного длинный.Я бы посоветовал взять учебник CLRS (Кормена, Лизерсона, Ривеста и Штейна) «Введение в алгоритмы» и прочитать о деревьях RB.
Реализация также не такая уж и короткая, поэтому, вероятно, не лучше включать ее сюда.Тем не менее, деревья используются широко для высокопроизводительных приложений, которым требуется доступ к большому количеству данных.Они обеспечивают очень эффективный способ поиска узлов с относительно небольшими затратами на вставку/удаление.Опять же, я бы посоветовал взглянуть на CLRS, чтобы узнать, как они используются.
Хотя BST не могут использоваться явно, один из примеров использования деревьев вообще есть почти в каждой современной СУБД.Точно так же ваша файловая система почти наверняка представлена в виде какой-то древовидной структуры, и файлы также индексируются таким же образом.Деревья питают Google.Деревья питают практически каждый веб-сайт в Интернете.
Другие советы
Я хотел бы ответить только на вопрос: «Так что же делает двоичные деревья полезными в некоторых типичных задачах, которые вы выполняете во время программирования?»
Это большая тема, по которой многие люди не согласны.Некоторые говорят, что алгоритмы, изучаемые на курсах компьютерной техники, такие как бинарные деревья поиска и ориентированные графы, не используются в повседневном программировании и поэтому не имеют значения.Другие не согласны, утверждая, что эти алгоритмы и структуры данных являются основой всего нашего программирования, и их важно понимать, даже если вам никогда не придется писать их самостоятельно.Это попадает в разговоры о хороших методах проведения собеседований и найма сотрудников.Например, Стив Йегге есть статья о собеседование в Google который касается этого вопроса.Помните эту дискуссию;опытные люди не согласны.
В типичном бизнес-программировании вам может вообще не потребоваться создавать бинарные деревья или даже деревья очень часто.Однако вы будете использовать множество классов, которые внутренне работают с использованием деревьев.Многие из основных организационных классов на каждом языке используют деревья и хеши для хранения данных и доступа к ним.
Если вы участвуете в более высокопроизводительных начинаниях или в ситуациях, которые выходят за рамки норм бизнес-программирования, деревья станут вашими непосредственными друзьями.Как сказал другой автор, деревья — это основные структуры данных для баз данных и индексов всех видов.Они полезны при интеллектуальном анализе и визуализации данных, расширенной графике (2D и 3D) и множестве других вычислительных задач.
Я использовал двоичные деревья в виде Деревья BSP (разделение двоичного пространства) в 3д графике.В настоящее время я снова изучаю деревья, чтобы сортировать большие объемы геокодированных данных и других данных для визуализации информации в приложениях Flash/Flex.Всякий раз, когда вы расширяете границы возможностей аппаратного обеспечения или хотите работать с более низкими характеристиками оборудования, понимание и выбор лучшего алгоритма может стать решающим фактором между неудачей и успехом.
Ни в одном из ответов не упоминается, для чего именно хороши BST.
Если вы хотите просто выполнить поиск по значениям, тогда хеш-таблица будет работать намного быстрее, вставка и поиск O (1) (в лучшем случае амортизированный).
BST будет поиском O (log N), где N — количество узлов в дереве, вставки также будут O (log N).
Деревья RB и AVL важны, как и другой ответ, упомянутый из-за этого свойства: если простой BST создается с упорядоченными значениями, то высота дерева будет равна количеству вставленных значений, это плохо для производительности поиска.
Разница между деревьями RB и AVL заключается в поворотах, необходимых для ребалансировки после вставки или удаления, деревья AVL имеют значение O (log N) для ребалансировки, а деревья RB — O (1).Примером преимущества этой постоянной сложности является случай, когда вы можете хранить постоянный источник данных, и если вам нужно отслеживать изменения для отката, вам придется отслеживать O (log N) возможных изменений с помощью дерева AVL.
Почему вы готовы платить за стоимость дерева вместо хеш-таблицы?ЗАКАЗ!Хэш-таблицы не имеют порядка, а BST всегда естественным образом упорядочены в силу своей структуры.Поэтому, если вы обнаружите, что помещаете кучу данных в массив или другой контейнер, а затем сортируете их позже, BST может быть лучшим решением.
Свойство order дерева дает вам ряд возможностей упорядоченной итерации: по порядку, в глубину, в ширину, в предварительном порядке и после порядка.Эти итерационные алгоритмы полезны в разных обстоятельствах, если вы хотите их найти.
Красно-черные деревья используются внутри почти каждого упорядоченного контейнера языковых библиотек, C++ Set and Map, .NET SortedDictionary, Java TreeSet и т. д.
Итак, деревья очень полезны, и вы можете использовать их довольно часто, даже не подозревая об этом.Скорее всего, ты никогда не будешь нуждаться написать его самостоятельно, хотя я бы очень рекомендовал это как интересное упражнение по программированию.
Красные, черные деревья и B-деревья используются во всех видах постоянного хранилища;поскольку деревья сбалансированы, производительность обхода в ширину и глубину снижается.
Почти все современные системы баз данных используют деревья для хранения данных.
По словам Майкла, BST заставляют мир вращаться.Если вы ищете хорошее дерево для реализации, взгляните на Деревья АВЛ (Википедия).У них есть условие балансировки, поэтому они гарантированно будут O(logn).Такая эффективность поиска делает логичным использование любого процесса индексации.Единственное, что было бы более эффективно, — это функция хеширования, но она становится ужасной быстро и в спешке.Кроме того, вы столкнетесь с Парадокс дня рождения (также известная как проблема с ячейками).
Какой учебник вы используете?Мы использовали Структуры данных и анализ в Java Марк Аллен Вайс.Я на самом деле держу его открытым на коленях, пока пишу это.В нем есть отличный раздел о красно-черных деревьях, и даже есть код, необходимый для реализации всех деревьев, о которых он говорит.
Красно-черные деревья остаются сбалансированными, поэтому вам не придется идти глубоко, чтобы достать предметы.Сэкономленное время делает RB-деревья O(log()n)) в ХУДШЕМ случае, тогда как неудачные бинарные деревья могут попасть в одностороннюю конфигурацию и привести к плохому выбору в O(n).Это действительно происходит на практике или на случайных данных.Поэтому, если вам нужен критичный по времени код (извлечение данных из базы данных, сетевой сервер и т. д.), вы используете деревья RB для поддержки упорядоченных или неупорядоченных списков/наборов.
Но RBTrees для нубов!Если вы занимаетесь искусственным интеллектом и вам нужно выполнить поиск, вы обнаружите, что вам приходится много разветвлять информацию о состоянии.Вы можете использовать постоянный красно-черный для создания новых состояний в O(log(n)).Постоянное красно-черное дерево сохраняет копию дерева до и после морфологической операции (вставка/удаление), но без копирования всего дерева (обычно и операции O(log(n))).У меня есть постоянное красно-черное дерево с открытым исходным кодом для Java.
Лучшее описание красно-черных деревьев, которое я когда-либо видел, содержится в книге Кормена, Лейзерсена и Ривеста «Введение в алгоритмы».Я мог даже понять это достаточно, чтобы частично реализовать его (только вставка).Есть также довольно много апплетов, таких как Вот этот на различных веб-страницах, которые анимируют процесс и позволяют вам наблюдать и пошагово графически представлять алгоритм построения древовидной структуры.
Поскольку вы спрашиваете, какое дерево используют люди, вам нужно знать, что красно-черное дерево по своей сути является B-деревом 2-3-4 (т.е. B-деревом порядка 4).B-дерево — это нет эквивалент двоичного дерева (как указано в вашем вопросе).
ЗдесьЭто отличный ресурс, описывающий первоначальную абстракцию, известную как симметричное двоичное B-дерево, которое позже превратилось в RBTree.Вам нужно хорошо разбираться в B-деревьях, прежде чем это обретет смысл.Обобщить:«Красная» ссылка в красно-черном дереве — это способ представления узлов, которые являются частью узла B-дерева (значения в пределах ключевого диапазона), тогда как «черные» ссылки — это узлы, которые соединены вертикально в B-дереве.
Итак, вот что вы получите, если переведете правила красно-черного дерева в термины B-дерева (я использую формат Правило Красного Чёрного дерева => B Древовидный эквивалент):
1) Узел либо красный, либо черный.=> Узел в b-дереве может быть либо частью узла, либо узлом нового уровня.
2) Корень черный.(Это правило иногда опускается, поскольку оно не влияет на анализ) => Корневой узел можно рассматривать либо как часть внутреннего корневого узла, либо как дочерний элемент воображаемого родительского узла.
3) Все листья (НОЛЬ) черные.(Все листья имеют тот же цвет, что и корень.) => Поскольку одним из способов представления RB-дерева является исключение листьев, мы можем исключить это.
4) Оба потомка каждого красного узла черные.=> Дочерние элементы внутреннего узла B-дерева всегда лежат на другом уровне.
5) Каждый простой путь от данного узла к любому из его листьев-потомков содержит одинаковое количество черных узлов.=> B-дерево поддерживается сбалансированным, поскольку оно требует, чтобы все конечные узлы находились на одинаковой глубине (следовательно, высота узла B-дерева представлена количеством черных ссылок от корня до листа красно-черного дерева). )
Кроме того, есть более простая «нестандартная» реализация Роберта Седжвика. здесь:(Он автор книги Алгоритмы вместе с Уэйном)
Здесь много-много тепла, но мало света, так что посмотрим, сможем ли мы его обеспечить.
Первый, RB-дерево представляет собой ассоциативную структуру данных, в отличие, скажем, от массива, который не может принимать ключ и возвращать связанное значение, ну, если только это не целочисленный «ключ» в разреженном индексе 0% смежных целых чисел.Массив также не может увеличиваться в размерах (да, я тоже знаю о realloc(), но под прикрытием этого требуется новый массив, а затем memcpy()), поэтому, если у вас есть какое-либо из этих требований, массив не подойдет. .Эффективность памяти массива идеальна.Нулевые потери, но не очень умные и гибкие — Realloc() не выдерживает.
Второй, в отличие от bsearch() для массива элементов, который ЯВЛЯЕТСЯ ассоциативной структурой данных, дерево RB может динамически увеличиваться (И уменьшаться) в размерах.bsearch() отлично работает для индексации структуры данных известного размера, которая останется в этом размере.Поэтому, если вы заранее не знаете размер своих данных или необходимо добавить или удалить новые элементы, функция bsearch() отсутствует.Bsearch() и qsort() хорошо поддерживаются в классическом C и имеют хорошую эффективность использования памяти, но недостаточно динамичны для многих приложений.Однако они мои личные фавориты, потому что они быстрые, простые и, если вы не имеете дело с приложениями реального времени, зачастую они достаточно гибкие.Кроме того, в C/C++ вы можете сортировать массив указателей на записи данных, указывая, например, на элемент структуры {}, который вы хотите сравнить, а затем переупорядочивать указатель в массиве указателей так, чтобы указатели считывались по порядку. в конце сортировки указателя ваши данные отсортированы.Использование этого с файлами данных, отображенными в памяти, чрезвычайно эффективно, быстро и довольно просто.Все, что вам нужно сделать, это добавить несколько символов «*» к функциям сравнения.
Третий, в отличие от хэш-таблицы, которая также должна иметь фиксированный размер и не может быть увеличена после заполнения, дерево RB будет автоматически расти и балансировать себя, чтобы поддерживать гарантию производительности O(log(n)).Особенно если ключом дерева RB является целое число, это может быть быстрее, чем хэш, потому что, хотя сложность хеш-таблицы равна O (1), эта 1 может быть очень дорогостоящим вычислением хеш-функции.Множественные целочисленные сравнения с 1 тактом часто превосходят хеш-вычисления с 100 и более тактами, не говоря уже о перехешировании и использовании пространства malloc() для коллизий хэшей и повторных хэшей.Наконец, если вам нужен доступ к ISAM, а также доступ по ключам к вашим данным, хэш исключается, поскольку в хеш-таблице нет упорядочения данных, в отличие от естественного упорядочения данных в любой реализации дерева.Классическое использование хеш-таблицы — предоставление компилятору доступа по ключу к таблице зарезервированных слов.Эффективность памяти превосходна.
Четвертый, и очень последним в любом списке находится связанный или двусвязный список, который, в отличие от массива, естественным образом поддерживает вставку и удаление элементов и, как следствие, изменение размера.Это самая медленная из всех структур данных, поскольку каждый элемент знает только, как добраться до следующего элемента, поэтому вам придется искать в среднем ссылки (element_knt/2), чтобы найти данные.Он в основном используется там, где вставки и удаления где-то в середине списка являются обычным явлением, и особенно там, где список является циклическим и требует дорогостоящего процесса, что делает время чтения ссылок относительно небольшим.Мой общий совет — использовать массив произвольного размера вместо связанного списка, если ваше единственное требование — возможность увеличения его размера.Если у вас закончился размер массива, вы можете перераспределить() больший массив.STL делает это за вас «под обложкой», когда вы используете вектор.Грубо, но потенциально в 1000 раз быстрее, если вам не нужны вставки, удаления или поиск по ключам.Эффективность использования памяти низкая, особенно для двусвязных списков.Фактически, двусвязный список, требующий двух указателей, столь же неэффективен по памяти, как и красно-черное дерево, но при этом не имеет НИ ОДНОЙ из своих привлекательных характеристик быстрого и упорядоченного поиска.
Пятый, Деревья поддерживают множество дополнительных операций над отсортированными данными, чем любая другая структура данных.Например, во многих запросах к базе данных используется тот факт, что диапазон конечных значений можно легко указать, указав их общего родителя, а затем сосредоточив последующую обработку на той части дерева, которой «владеет» родитель.Потенциал многопоточности, предлагаемый этим подходом, должен быть очевиден, поскольку необходимо заблокировать только небольшую область дерева, а именно, только узлы, которыми владеет родительский элемент, и сам родительский элемент.
Короче говоря, деревья — это Кадиллак структур данных.Вы платите высокую цену с точки зрения используемой памяти, но получаете полностью самоподдерживающуюся структуру данных.Вот почему, как указано в других ответах здесь, базы данных транзакций почти исключительно используют деревья.
Если вы хотите увидеть, как графически должно выглядеть красно-черное дерево, я закодировал реализацию красно-черного дерева, которую вы можете Скачать здесь
IME, алгоритм дерева RB почти никто не понимает.Люди могут повторять вам правила, но они не понимают. почему эти правила и откуда они берутся.Я не исключение :-)
По этой причине я предпочитаю алгоритм AVL, поскольку его легко постигать.Как только вы это поймете, вы сможете написать его с нуля, потому что это имеет для вас смысл.
Деревья могут быть быстрыми.Если у вас есть миллион узлов в сбалансированном двоичном дереве, в среднем потребуется двадцать сравнений, чтобы найти какой-либо один элемент.Если у вас миллион узлов в связанном списке, то в среднем потребуется пятьсот тысяч сравнений, чтобы найти один и тот же элемент.
Однако если дерево несбалансировано, оно может быть таким же медленным, как и список. и также потребуется больше памяти для хранения.Представьте себе дерево, в котором у большинства узлов есть правый дочерний элемент, но нет левого дочернего узла;это является список, но вам все равно нужно иметь место в памяти, чтобы поместить левый узел, если он появится.
В любом случае, АВЛ-дерево был первым алгоритмом сбалансированного двоичного дерева, и статья в Википедии о нем довольно ясна.Статья в Википедии о красно-черных деревьях ясна как грязь, если честно.
Помимо двоичных деревьев, B-деревья — это деревья, каждый узел которых может иметь множество значений.B-дерево нет двоичное дерево, просто так оно и называется.Они действительно полезны для эффективного использования памяти;каждый узел дерева может иметь размер, соответствующий одному блоку памяти, чтобы вам не приходилось (медленно) искать массу разных вещей в памяти, которая была выгружена на диск.Вот феноменальный пример B-дерево.
