Nano Hash - криптовалюты, майнинг, программирование

Порядок вставки для наихудшего случая черной высоты красного черного дерева

Допустим, мы имеем дело с клавишами 1-15. Чтобы получить наихудшую производительность обычного BST, вы должны вставить ключи в порядке возрастания или убывания следующим образом:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

Тогда BST по существу станет связанным списком.

В лучшем случае BST вы должны вставить ключи в следующем порядке, они расположены таким образом, что следующий вставленный ключ составляет половину всего вставляемого диапазона, поэтому первый 15/2 = 8, затем 8 /2 = 4 и т.д...

8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15

Тогда BST будет хорошо сбалансированным деревом с оптимальной высотой 3.

Лучший случай для красно-черного дерева также может быть построен с помощью лучшего случая из BST. Но как построить наихудший случай для красно-черного дерева? Это то же самое, что и худший случай для BST? Есть ли конкретный шаблон, который приведет к наихудшему случаю?

red-black-tree binary-search-tree insertion-order
27.02.2013

  • Эй, это отличный вопрос, я думаю. И мне особенно интересно узнать ответ. Возможно, здесь помогут люди из cstheory stackexchange. Так что, если вы можете опубликовать его там? 02.03.2013
  • Я наткнулся на этот документ: citeseerx.ist.psu.edu/ viewdoc/summary?doi=10.1.1.46.1458 03.03.2013
  • Не могли бы вы уточнить half of the total range to be inserted? Просто интересно, так и не разобрался 31.07.2013
  • Худший случай скорее хорош. Википедия говорит: Балансировка дерева не идеальна, но она достаточно хорош, чтобы гарантировать поиск за время O(log n), где n — общее количество элементов в дереве. и: [...] полезно [...] в приложениях реального времени [...] и планировщик Completely Fair Scheduler, используемый в текущих ядрах Linux, и реализация системных вызовов epoll использует красно-черные деревья. 10.04.2019

Ответы:


1

Вы ищете тощее дерево, верно? Это можно сделать, вставив [1 ... , 2^(n+1)-2] в обратном порядке.

02.08.2013

2

Вы не сможете. Красно-черное дерево держит себя «густым», поэтому оно будет вращаться, чтобы исправить дисбаланс. Длина приведенного выше наихудшего случая для красно-черного дерева ограничена двумя элементами, но это все же не «плохой» случай; это то, что ожидается, поскольку lg(2) = 1, и у вас есть 1 слой за корнем с двумя элементами. Как только вы добавите третий элемент, вы получите следующее:

B                   B
 \                 / \
  R       =>      R   R
   \
    R
16.05.2013
  • только потому, что дерево уравновешивает себя, не означает, что нет худшего случая. в экземпляре дерева rb наихудший случай, вероятно, включает последовательность вставок, вокруг которых плохо работают правила самобалансировки. 17.05.2013
  • Это правда, есть наихудший случай, но это не будет линейный массив, как вы написали. Я неправильно понял ваш вопрос? Изменить: для данного набора элементов существует наихудший случай. 18.05.2013
  • Числа, разделенные запятыми, предназначены для представления порядка вставки, а не массива. Это проясняет ситуацию? 20.05.2013
  • Да, и это делает проблему довольно интересной. Будет хорошая тема для дипломной работы. 20.05.2013
    • Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..