Красно-черные деревья

Я хотел бы обратиться только к вопросу "Поэтому, что делает двоичные деревья полезными в некоторых общих задачах, которые Вы делаете при программировании?"

Это - большая тема, на которой не соглашаются многие люди. Некоторые говорят, что алгоритмы, преподававшие в градусе CS, такие как деревья двоичного поиска и ориентированные графы, не используются в ежедневном программировании и поэтому не важны. Другие не соглашаются, говоря, что эти алгоритмы и структуры данных являются основой для всего нашего программирования, и важно понять их, даже если Вы никогда не должны писать один для себя. Это проникает в переговоры о хороших методах интервьюирования и найма. Например, у Steve Yegge есть статья о интервьюирование в Google , который обращается к этому вопросу. Помните эти дебаты; опытные люди не соглашаются.

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

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

я использовал двоичные деревья в форме BSP (двоичное разделение пространства) деревья в 3-й графике. Я в настоящее время смотрю на деревья снова для сортировки больших сумм геокодируемых данных и других данных для визуализации информации в приложениях Flash/Flex. Каждый раз, когда Вы раздвигаете границу аппаратных средств, или Вы хотите работать на более низких спецификациях оборудования, понимание и выбирание лучшего алгоритма могут иметь значение между отказом и успехом.

BSTs заставляют мир вращаться, как сказано Micheal. Если Вы ищете хорошее дерево, чтобы реализовать, смотреть на деревья AVL (Википедия). У них есть балансирующееся условие, таким образом, они, как гарантируют, будут O (logn). Этот вид ищущей эффективности делает логичным поместить в любой вид индексации процесса. Единственной вещью, которая была бы более эффективной, будет хеш-функция, но те становятся ужасными быстрый, быстро, и второпях. Кроме того, Вы сталкиваетесь День рождения Paradox (также известный как проблема ящика).

, Какой учебник Вы используете? Мы использовали Структуры данных и Анализ в Java Mark Allen Weiss. У меня на самом деле есть он открытый в моей полировке, поскольку я ввожу это. Это имеет большой раздел о Красно-черных деревьях, и даже включает код, необходимый для реализации всех деревьев, о которых это говорит.

Красные Черные Деревья и B-деревья используются во всех видах персистентного устройства хранения данных; потому что деревья сбалансированы, производительность обходов ширины и глубины смягчена.

Почти все современные системы баз данных используют деревья для хранения данных.

Лучшее описание красно-черных деревьев, которые я видел, является тем в Cormen, Leisersen и 'Введении Rivest в Алгоритмы'. Я мог даже понять его достаточно для неравнодушной реализации одного (только вставка). Существует также довольно много апплетов такой как Этот на различных веб-страницах, которые анимируют процесс и позволяют Вам смотреть и ступать через графическое представление алгоритма, создающего древовидную структуру.

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

IME, почти никто не понимает древовидный алгоритм RB. Люди могут повторить правила назад Вам, но они не понимают, почему те правила и куда они происходят из. Я не исключение :-)

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

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

Затем вам понадобится часть "путь" результирующего массива.

Почему вы готовы платить за дерево за хеш-таблицу? ПРИКАЗ! Хеш-таблицы не имеют порядка, с другой стороны, BST всегда имеют естественный порядок в силу своей структуры. Так что, если вы обнаружите, что бросаете кучу данных в массив или другой контейнер, а затем сортируете их позже, BST может быть лучшим решением.

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

Красно-черные деревья используются внутри почти в каждом упорядоченном контейнере языковых библиотек, C ++ Set and Map, .NET SortedDictionary, Java TreeSet и т. Д.

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