Сбалансированные деревья

  void balanceR(link h)
    { if ((h == 0) || (h->N == 1)) return;
      partR(h, h->N/2);
      balanceR(h->l);
      balanceR(h->r);
    }
    

Рандомизированные BST-деревья

Чтобы проанализировать средние затраты при работе с BST-деревьями, было сделано предположение, что элементы вставляются в случайном порядке (см. ). Применительно к BST-алгоритму основное следствие из этого предположения заключается в том, что каждый узел дерева с равной вероятностью может оказаться корневым, причем это же справедливо и по отношению к поддеревьям. Интересно, что случайность можно включить в алгоритм, чтобы это свойство сохранялось без каких-либо допущений относительно порядка вставки элементов. Идея проста: при вставке нового узла в дерево из N узлов вероятность появления нового узла в корне должна быть равна 1/(N + 1), поэтому нужно просто принять случайное решение использовать вставку в корень с этой вероятностью. Иначе рекурсивно выполняется вставка новой записи в левое поддерево, если ключ записи меньше ключа в корне, и в правое поддерево, если он больше. Реализация этого метода приведена в программе 13.2.

Программа 13.2. Вставка в рандомизированное BST-дерево

Эта функция принимает случайное решение о том, использовать ли метод вставки в корень из программы 12.13 или стандартный метод вставки из программы 12.8. В рандомизированном BST-дереве каждый из узлов с равной вероятностью может быть корнем; поэтому, помещая новый узел в корень дерева размером N с вероятностью 1/(N + 1), мы получаем рандомизированное дерево.

  private:
    void insertR(link h, Item x)
      { if (h == 0) { h = new node(x); return; }
        if (rand() < RAND_MAX/(h->N+1))
          { insertT(h, x); return; }
        if (x.key() < h->item.key())
          insertR(h->l, x);
        else
          insertR(h->r, x);
        h->N++;
      }
  public:
    void insert(Item x)
      { insertR(head, x); }
      

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

Лемма 13.1. Построение рандомизированного BST-дерева эквивалентно построению стандартного BST-дерева из случайной перестановки исходных ключей. Для создания рандомизированного BST-дерева из N элементов используется около 2NlnN сравнений (независимо от порядка вставки элементов), а для поиска в таком дереве требуется приблизительно 2 lnN сравнений.

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

(рис 13.2) Вставка в рандомизированное BST-дерево

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

Различие между производительностью в среднем для рандомизированных и стандартных BST-деревьев очень невелико, но имеет большое значение. Усредненные затраты в обоих случаях одинаковы (хотя для рандомизированных деревьев коэффициент пропорциональности несколько выше), однако в случае стандартных деревьев результат зависит от предположения о вставке элементов в случайном порядке их ключей (все последовательности вставок равновероятны). Во многих практических приложениях это допущение неверно, поэтому рандомизированный алгоритм важен тем, что позволяет избавиться от такого предположения и вместо этого опираться на законы теории вероятностей и степень случайности генератора случайных чисел. При вставке элементов в порядке возрастания их ключей, в обратном порядке или любом другом порядке — BST-дерево все равно будет случайным.

На рис. 13.3 рис 13.3 показано построение рандомизированного дерева для некоторого набора ключей. Поскольку решения, принимаемые алгоритмом, являются случайными, то, скорее всего, последовательность деревьев при каждом выполнении алгоритма будет иной. На рис 13.4 показано, что рандомизированное дерево, построенное из набора элементов, упорядоченных по возрастанию ключей, обладает теми же свойствами, что и стандартное BST-дерево, построенное из случайно упорядоченных элементов (сравните с рис. 12.8 рис 12.8).

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

Лемма 13.2. Вероятность того, что затраты на создание рандомизированного BST-дерева превышают усредненные затраты в а раз, меньше $$$e^{-\alpha}$$$.

Этот результат и аналогичные ему следуют из общего решения вероятностных рекуррентных соотношений, которые были выведены Карпом (Karp) в 1995 г. (см. раздел ссылок). $$$\blacksquare$$$

Например, для построения рандомизированного BST-дерева из 100 000 узлов требуется около 2,3 миллиона сравнений, но вероятность того, что количество сравнений превысит 23 миллиона, значительно меньше 0,01%. Подобная гарантия производительности более чем удовлетворяет практическим требованиям, предъявляемым к обработке реальных наборов данных такого размера. При использовании стандартного BST-дерева такая гарантия для этой задачи невозможна: например, производительность снизится, если данные в значительной степени упорядочены, что маловероятно для случайных данных, но по множеству причин достаточно часто бывает с реальными данными.

По тем же соображениям утверждение, аналогичное лемме 13.2, справедливо и для времени выполнения быстрой сортировки. Но в данном случае это более важно, поскольку отсюда следует еще и то, что затраты на поиск в дереве близки к средним. Независимо от дополнительных затрат при построении деревьев, стандартную реализацию BST-дерева можно использовать для выполнения операций найти при затратах, которые зависят только от формы деревьев, и при отсутствии каких-либо дополнительных затрат на балансировку. Это свойство важно в обычных приложениях, в которых операции найти встречаются гораздо чаще, чем любые другие. Например, описанное в предыдущем абзаце BST-дерево из 100 000 узлов могло бы содержать телефонный справочник и использоваться для выполнения миллионов поисков. Можно быть почти уверенным, что каждый поиск потребует затрат, которые отличаются от среднего значения, равного приблизительно 23 сравнениям, лишь небольшим постоянным коэффициентом. Поэтому на практике можно не беспокоиться, что для большого количества поисков потребуется порядка 100 000 сравнений, в то время как при использовании стандартных BST-деревьев для беспокойства были бы основания.

Один из главных недостатков рандомизированных вставок — затраты на генерацию случайных чисел в каждом из узлов во время каждой вставки.

(рис 13.3) Построение рандомизированного BST-дерева

На этих рисунках показан процесс рандомизированных вставок ключей A B C D E F G H I в первоначально пустое BST-дерево. Дерево на нижнем рисунке выглядит так же, как если бы оно было построено с применением стандартного алгоритма BST-дерева при вставке этих же ключей в случайном порядке.

(рис 13.4) Большое рандомизированное BST-дерево

Это BST-дерево является результатом рандомизированных вставок 200 элементов в порядке возрастания их ключей в первоначально пустое дерево. Дерево выглядит так, как если бы оно было построено из случайно упорядоченных ключей (см. рис 12.8).

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

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

Основной принцип сохранения случайности в деревьях приводит также к эффективным реализациям операций удалить, объединить и других операций АТД таблицы символов, обеспечивая при этом создание случайных деревьев.

Для объединения дерева из N узлов с деревом из M узлов используется базовый метод, описанный в , за исключением принятия случайного решения о выборе корня по принципу: корень объединенного дерева выбирается из дерева с N узлами с вероятностью N/(M + N), а из дерева с М узлами — с вероятностью M/ (M + N). В программе 13.3 приведена реализация этой операции.

Аналогично произвольное решение можно заменить случайным и в алгоритме операции удалить, как показано в программе 13.4. Этот метод соответствует варианту удаления узлов в стандартных BST-деревьях, который не был нами рассмотрен, поскольку без рандомизации он приводил бы к несбалансированным деревьям (см. упражнение 13.21).

Программа 13.3. Объединение рандомизированных BST-деревьев

В данной функции используется тот же подход, что и в программе 12.17, за исключением того, что в ней принимается не произвольное, а случайное решение о том, какой узел использовать в качестве корня объединенного дерева, исходя из равной вероятности помещения в корень любого узла. Приватная функция-член fixN заносит в b->N значение, которое на 1 больше суммы соответствующих полей в поддеревьях (0 для пустых деревьев).

  private:
    link joinR(link a, link b)
      { if (a == 0) return b;
        if (b == 0) return a;
        insertR(b, a->item);
        b->l = joinR(a->l, b->l);
        b->r = joinR(a->r, b->r);
        delete a; fixN(b); return b;
      }
  public:
    void join(ST<Item, Key> b)
      { int N = head->N;
        if (rand()/(RAND MAX/(N+b.head->N)+1) < N)
          head = joinR(head, b.head);
        else
        head = joinR(b.head, head);
      }
      

Программа 13.4. Удаление в рандомизированном BST-дереве

Для удаления используется та же функция remove, что и для стандартных BST-деревьев (см. программу 12.16), но функция joinLR заменена приведенной здесь функцией. В ней принимается не произвольное, а случайное решение, заменить ли удаляемый узел предком или потомком, исходя из того, что каждый узел в результирующем дереве с равной вероятностью может быть его корнем. Чтобы счетчики узлов содержали правильные значения, в качестве последнего оператора в функции removeR нужен вызов функции fixN (см. программу 13.3) для h.

  link joinLR(link a, link b)
    { if (a == 0) return b;
      if (b == 0) return a;
      if (rand()/(RAND_MAX/(a->N+b->N)+1) < a->N)
        { a->r = joinLR(a->r, b); return a; }
      else
        { b->l = joinLR(a, b->l); return b; }
    }
      

Лемма 13.3. Создание дерева с помощью произвольной последовательности случайных операций вставить, удалить и объединить эквивалентно построению стандартного BST-дерева из случайной перестановки ключей дерева.

Как и в случае с леммой 13.1, для доказательства этого утверждения требуется тщательный вероятностный анализ (см. раздел ссылок). $$$\blacksquare$$$

Доказательства свойств вероятностных алгоритмов требуют хорошего понимания теории вероятностей, но понимание таких доказательств отнюдь не обязательно для программистов, использующих эти алгоритмы. Осмотрительный программист в любом случае проверит утверждения, подобные свойству 13.3, независимо от того, как они обоснованы (например, проверив качество генератора случайных чисел или иных особенностей реализации), и, следовательно, сможет уверенно использовать эти методы. Похоже, что рандомизированные BST-деревья представляют собой простейший способ поддержки всех свойств АТД таблицы символов при гарантии почти оптимальной производительности — именно поэтому они находят применение во многих практических приложениях.

Упражнения

13.8. Нарисуйте рандомизированное BST-дерево, образованное вставками элементов с ключами E A S Y Q U T I O N в указанном порядке в первоначально пустое дерево, если реализован плохой метод рандомизации, выполняющий вставку в корень каждый раз при нечетном размере дерева.

13.9. Напишите программу-драйвер, которая 1000 раз выполняет следующий эксперимент для N = 10 и 100: используя программу 13.2, вставляет ключи от 0 до N — 1 (по порядку) в первоначально пустое рандомизированное BST-дерево, а затем выводит $$$\chi^{2}$$$ -распределение для предположения, что вероятность попадания каждого ключа в корень равна 1/N (см. упражнение 14.5).

13.10. Приведите вероятность попадания ключа F в каждую из позиций, показанных на рис 13.2.

13.11. Напишите программу вычисления вероятности того, что рандомизированная вставка завершается в одном из внутренних узлов заданного дерева, для каждого из узлов на пути поиска.

13.12. Напишите программу вычисления вероятности того, что рандомизированная вставка завершается в одном из внешних узлов заданного дерева.

13.13. Реализуйте нерекурсивную версию функции рандомизированной вставки, приведенной в программе 13.2.

13.14. Нарисуйте рандомизированное BST-дерево, образованное вставками элементов с ключами E A S Y Q U T I O N в указанном порядке в первоначально пустое дерево при использовании версии программы 13.2, в которой в выражении, принимающем решение о применении вставки в корень, вызов rand() заменен проверкой (111 % h.N) == 3.

13.15. Выполните упражнение 13.9 для версии программы 13.2, в которой в выражении, принимающем решение о применении вставки в корень, вызов rand() заменен проверкой (111 % h.N) == 3.

13.16. Приведите последовательность случайных решений, которая привела бы к построению вырожденного дерева (все ключи упорядочены, а левые ссылки являются пустыми) из ключей E A S Y Q U T I O N. Какова вероятность возникновения этого события?

13.17. Может ли любое BST-дерево, содержащее ключи E A S Y Q U T I O N, быть построено с помощью какой-либо последовательности случайных решений, если эти ключи вставляются в указанном порядке в первоначально пустое дерево? Обоснуйте свой ответ.

13.18. Определите эмпирическим путем среднее значение и среднеквадратичное отклонение количества сравнений, используемых для успешных и неудачных поисков в рандомизированном BST-дереве, построенном вставками N случайных ключей в первоначально пустое дерево, при N = 103, 104, 105 и 106 .

13.19. Нарисуйте BST-дерево, образованное в результате удаления программой 13.4 ключа Q из дерева, построенного в упражнении 13.14, если для принятия решения об объединении с помещением ключа a в корень используется проверка (111 % (a.N + b.N)) < a.N.

13.20. Нарисуйте BST-дерево, образованное вставками элементов с ключами E A S Y в первоначально пустое дерево, вставками элементов с ключами Q U E S T I O N в другое первоначально пустое дерево и последующим объединением результатов программой 13.3 с проверкой, описанной в упражнении 13.19.

13.21. Нарисуйте BST-дерево, образованное вставками элементов с ключами E A S Y Q U T I O N в указанном порядке в первоначально пустое дерево и последующим удалением ключа Q программой 13.4, если используется плохой генератор случайных чисел, всегда возвращающий 0.

13.22. Экспериментально определите рост высоты BST-дерева при выполнении длинной последовательности чередующихся случайных вставок и удалений с помощью программ 13.2 и 13.3 в дереве из N узлов, при N = 10, 100 и 1000 и при выполнении N2 пар вставок-удалений для каждого N.

13.23. Сравните результаты, полученные в упражнении 13.22, с результатом удаления и повторной вставки наибольшего ключа в рандомизированном дереве из N узлов с помощью программ 13.2 и 13.3, для N = 10, 100 и 1000 и при выполнении N² пар вставок-удалений для каждого N.

13.24. Добавьте в программу из упражнения 13.22 возможность определения среднего количества вызовов функции rand() при удалении одного элемента.

Скошенные деревья бинарного поиска

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

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

Скошенная вставка (splay insertion) перемещает вновь вставленные узлы в корень, применяя трансформации, показанные на рис 13.5 (стандартная вставка в корень, если ссылки от корня к узлу-внуку на пути поиска имеют различную ориентацию) и в правой части рис 13.6 (две ротации в корне, если ссылки от корня к узлу-внуку на пути поиска имеют одинаковую ориентацию). Построенные таким образом BST-деревья называются скошенными BST-деревьями (splay BST). Программа 13.5 является рекурсивной реализацией скошенной вставки; пример одиночной вставки приведен на рис 13.7, а пример построения дерева показан на рис 13.8. Различие между скошенной и стандартной вставками в корень может показаться несущественным, но оно достаточно важно: операция скоса исключает худший случай квадратичного времени выполнения — главный недостаток стандартных BST-деревьев.

(рис 13.5) Двойная ротация в BST-дереве (ориентации различны)

В приведенном дереве (вверху) в результате ротации влево в узле G, за которой следует ротация вправо в узле L, узел I помещается в корень (внизу). Эти ротации могут завершать процесс вставки в стандартном или скошенном BST-дереве.

Лемма 13.4. Количество сравнений, используемых при построении скошенного дерева N вставками в первоначально пустое дерево, равно O (N lgN).

Это утверждение — следствие более жесткой леммы 13.5, которая будет рассмотрена ниже. $$$\blacksquare$$$

Константа, подразумеваемая в O-нотации, равна 3. Например, для построения BST-дерева из 100 000 узлов с помощью скошенных вставок всегда требуется менее 5 миллионов сравнений. Это не гарантирует, что полученное дерево поиска будет хорошо сбалансировано или что каждая операция будет эффективной, но очень важна полученная гарантия общего времени выполнения; на практике фактическое время выполнения, скорее всего, окажется еще меньше.

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

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

Лемма 13.5. Количество сравнений, требуемых для любой последовательности M операций вставить или найти в скошенном BST-дереве из N узлов, равно

O ((N + M) lg(N + M)).

Доказательство этого утверждения, приведенное Слитором (Sleator) и Тарьяном (Tarjan) в 1985 г., является классическим примером амортизационного анализа алгоритмов (см. раздел ссылок). Подробно оно будет рассмотрено в части VIII. $$$\blacksquare$$$

(рис 13.6) Двойная ротация в BST-дереве (ориентации одинаковы)

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

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

Граничное значение, приведенное в свойстве 13.5 — это граница общих затрат на все операции в худшем случае. Как это обычно бывает для граничных значений в худшем случае, они могут быть гораздо выше фактических затрат. Операция скоса перемещает последние посещенные элементы ближе к вершине дерева; поэтому данный метод удобен для приложений поиска с неравномерной структурой запросов — особенно для приложений со сравнительно небольшим, или даже медленно изменяющимся, набором элементов, к которым выполняется обращение.

Программа 13.5. Скошенная вставка в BST-дерево

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

Программа проверяет четыре варианта для двух шагов пути поиска от корня и выполняет соответствующие ротации:

влево-влево: дважды выполняет ротацию влево в корне;

влево-вправо: выполняет ротацию влево в левом дочернем узле, а затем вправо в корне;

вправо-вправо: дважды выполняет ротацию вправо в корне;

вправо-влево: выполняет ротацию вправо в правом дочернем узле, а затем влево в корне.

  private:
    void splay(link h, Item x)
      { if (h == 0)
          { h = new node(x, 0, 0, 1); return; }
        if (x.key() < h->item.key())
          { link hl = h->l; int N = h->N;
            if (hl == 0)
              { h = new node(x, 0, h, N+1); return; }
            if (x.key() < hl->item.key())
              { splay(hl->l, x); rotR(h); }
            else
              { splay(hl->r, x); rotL(hl); }
            rotR(h);
          }
        else
          { link hr = h->r; int N = h->N;
            if (hr == 0)
              { h = new node(x, h, 0, N+1); return; }
            if (hr->item.key() < x.key())
              { splay(hr->r, x); rotL(h); }
            else
              { splay(hr->l, x); rotR(hr); }
            rotL(h);
          }
        }
    public:
      void insert(Item item)
        { splay(head, item); }
      

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

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

(рис 13.7) Скошенная вставка

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

(рис 13.8) Построение скошенного дерева

Здесь показана последовательность скошенных вставок записей с ключами A S E R C H I N G в первоначально пустое дерево.

(рис 13.9) Балансировка худшего случая скошенного дерева с помощью серии поисков

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

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

Если в дереве могут быть повторяющиеся ключи, то операция скоса может привести к тому, что элементы с ключами, равными ключу в данном узле, попадут по обе стороны от этого узла (см. упражнение 13.38). Из этого следует, что найти все элементы с данным ключом будет не так легко, как в случае стандартных BST-деревьев. Необходимо либо проверять наличие равных ключей в обоих поддеревьях, либо воспользоваться каким-либо альтернативным методом обработки повторяющихся ключей из описанных в .

Упражнения

13.25. Нарисуйте скошенное BST-дерево, образованное скошенными вставками элементов с ключами E A S Y Q U T I O N в указанном порядке в первоначально пустое дерево.

13.26. Сколько ссылок дерева должно быть изменено для выполнения двойной ротации? Сколько ссылок действительно изменяется при выполнении каждой из двойных ротаций в программе 13.5?

13.27. Добавьте в программу 13.5 реализацию операции найти со скосом.

13.28. Реализуйте нерекурсивную версию функции скошенной вставки из программы 13.5.

13.29. Используйте программу-драйвер из упражнения 12.30 для определения эффективности скошенных BST-деревьев как самоорганизующихся структур поиска, сравнив их со стандартными BST-деревьями для распределения поисковых запросов, определенных в упражнениях 12.31 и 12.32.

13.30. Нарисуйте все структурно различные BST-деревья, которые могут быть получены скошенными вставками N ключей в первоначально пустое дерево, для 2 < N < 7.

13.31. Определите вероятность того, что каждое из деревьев в упражнении 13.30 образовано вставками N случайных различных элементов в первоначально пустое BST-дерево.

13.32. Определите эмпирически среднее значение и среднеквадратичное отклонение количества сравнений, используемых при успешном и неудачном поиске в BST-дереве, построенном скошенными вставками N случайных ключей в первоначально пустое дерево, при N = 103, 104, 105 и 106 . Не следует выполнять сами операции поиска: просто постройте деревья и вычислите длину их путей. Являются ли скошенные BST-деревья более сбалансированными, чем произвольные BST-деревья, или менее, или одинаково?

13.33. Добавьте в программу из упражнения 13.32 выполнение N случайных (скорее всего, неудачных) поисков со скосом в каждом из созданных деревьев. Как влияет скос на среднее количество сравнений при неудачном поиске?

13.34. Добавьте в программы из упражнений 13.32 и 13.33 возможность измерения времени их выполнения вместо подсчета количества сравнений. Проведите те же эксперименты. Объясните любые изменения в выводах, получаемых из экспериментальных результатов.

13.35. Сравните применение скошенных BST-деревьев со стандартными BST-деревьями в задаче построения индекса по фрагменту реального текста, содержащего по меньшей мере 1 миллион символов. Измерьте время, требуемое для построения индекса и средние длины путей в BST-деревьях.

13.36. Определите экспериментально среднее количество сравнений при успешном поиске в скошенном BST-дереве, построенном вставками произвольных ключей, при N = 103, 104, 105 и 106 .

13.37. Проверьте экспериментально идею использования скошенных вставок, а не стандартных вставок в корень, для рандомизированных BST-деревьев.

13.38. Нарисуйте скошенное BST-дерево, образованное вставками элементов с ключами 0 0 0 0 0 0 0 0 0 0 0 0 1 в указанном порядке в первоначально пустое дерево.

Нисходящие 2-3-4-деревья

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

Для гарантии сбалансированности создаваемых BST-деревьев используемые структуры деревьев должны обладать определенной гибкостью. Для получения такой гибкости предположим, что узлы в наших деревьях могут содержать более одного ключа. А именно, мы допустим существование 3-узлов и 4-узлов, которые могут содержать, соответственно, два и три ключа. 3-узлы содержат три ссылки: одна на все элементы, ключи которых меньше обоих его ключей, одна на все элементы, ключи которых имеют значения между двумя его ключами, и одна на все элементы, ключи которых больше обоих его ключей. Аналогично, 4-узел имеет четыре ссылки: по одной для каждого из интервалов, определенных его тремя ключами. Тогда узлы в стандартном BST-дереве можно было бы называть 2-узлами: они содержат один ключ и две ссылки. Позже мы рассмотрим эффективные способы определения и реализации базовых операций с этими расширенными узлами; пока же будем считать, что есть удобные способы работы с ними, и посмотрим, как они позволяют формировать деревья.

Определение 13.1. 2-3-4-дерево поиска — это либо пустое дерево, либо дерево, содержащее три типа узлов: 2-узлы — с одним ключом, левой ссылкой на дерево с меньшими ключами и правой ссылкой на дерево с большими ключами; 3-узлы — с двумя ключами, с левой ссылкой на дерево с меньшими ключами, средней ссылкой на дерево, ключи которых имеют значения между значениями ключей данного узла, и правой ссылкой на дерево с большими ключами; и 4-узлы с тремя ключами и четырьмя ссылками на деревья, значения ключей которых определены диапазонами, образованными ключами узла.

Определение 13.2. Сбалансированное 2-3-4-дерево поиска — это 2-3-4-дерево поиска, все ссылки на пустые деревья которого расположены на одинаковом расстоянии от корня.

В этой главе термин 2-3-4-дерево будет применяться к сбалансированным 2-3-4-деревьям поиска (в других контекстах он означает более общую структуру). Пример 2-3-4-дерева приведен на рис 13.10.

Алгоритм поиска ключей в таком дереве представляет собой обобщение алгоритма поиска для BST-деревьев. Чтобы выяснить, находится ли ключ в дереве, мы сравниваем его с ключами в корне: если он равен любому из них, поиск успешен; в противном случае мы переходим по ссылке от корня к поддереву, соответствующему множеству значений ключей, к которому принадлежит искомый ключ, и затем рекурсивно выполняем поиск в этом дереве. Существует ряд способов представления 2-, 3- и 4-узлов и организации поиска соответствующей ссылки; мы отложим рассмотрение этих решений до раздела 13.4, где будет рассмотрено очень удобное решение.

Для вставки нового узла в 2-3-4-дерево можно было бы, как в BST-деревьях, выполнить неудачный поиск, а затем присоединить узел, но при этом новое дерево оказалось бы несбалансированным. Основная причина важности 2-3-4-деревьев состоит в том, что они позволяют выполнять вставки, всегда сохраняя полную сбалансированность дерева. Например, легко видеть, что делать, если поиск заканчивается на 2-узле: достаточно преобразовать его в 3-узел. Аналогично, если поиск заканчивается на 3-узле, его достаточно преобразовать в 4-узел. Но что делать, если поиск прерывается на 4-узле? Решение состоит в том, что можно найти место для нового ключа, сохраняя сбалансированность дерева, вначале разделив 4-узел на два 2-узла, и затем передав средний узел вверх к родительскому узлу. Эти три описанных случая показаны на рис 13.11.

А что делать, если необходимо разбить 4-узел, родительский узел которого также является 4-узлом? Одним из возможных выходов было бы разбиение и родительского узла, но узел-предок также может оказаться 4-узлом и т.д. — возможно, пришлось бы разделять узлы на всем пути вверх по дереву. Более простой подход — обеспечить, чтобы путь поиска не завершался в 4-узле, разбивая любой 4-узел, попадающийся при следовании вниз по дереву.

А именно, каждый раз, когда встречается 2-узел с дочерним 4-узлом, такая пара преобразуется в 3-узел с двумя дочерними 2-узлами; а когда встречается 3-узел с дочерним 4-узлом, такая пара преобразуется в 4-узел с двумя дочерними 2-узлами (см. рис 13.12). Разбиение 4-узлов возможно потому, что можно перемещать не только ключи, но и ссылки. Два 2-узла имеют столько же (четыре) ссылок, что и 4-узел, поэтому разбиение можно выполнить, не внося никаких изменений ниже (или выше) разбиваемого узла. 3-узел не преобразуется в 4-узел одним лишь добавлением еще одного ключа; требуется еще одна ссылка (в данном случае — дополнительная ссылка, созданная разбиением). Очень важно, что эти преобразования являются чисто локальными: не нужно проверять или изменять никакую часть дерева, кроме показанной на рис 13.12. Каждое преобразование передает один из ключей 4-узла в его родительский узел и соответствующим образом преобразует ссылки.

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

Еще один нюанс: когда корень дерева становится 4-узлом, мы просто разбиваем его, преобразуя в треугольник, состоящий из трех 2-узлов, как для первого разбиваемого узла в предыдущем примере. Разбиение корня после вставки несколько удобнее ожидания очередной вставки для выполнения разбиения, поскольку в этом случае не нужно заботиться о родительском узле корня. Разбиение корня (и только эта операция) приводит к увеличению высоты дерева на один уровень.

(рис 13.10) 2-3-4-дерево

На этом рисунке изображено 2-3-4-дерево, содержащее ключи A S R C H I N G E X M P L.

В таком дереве ключ можно отыскать, используя ключи в корневом узле для нахождения ссылки на нужное поддерево, с последующим рекурсивным продолжением поиска. Например, для поиска ключа P в этом дереве нужно пройти по правой ссылке от корня, поскольку P больше I, затем — по средней ссылке от правого дочернего узла корня, поскольку P находится между N и R, и, наконец, завершить успешный поиск в 2-узле, содержащем ключ P.

(рис 13.11) Вставка в 2-3-4-дерево

2-3-4-дерево, состоящее только из 2-узлов, аналогично BST-дереву (вверху). Ключ C можно вставить, преобразовав 2-узел, в котором прерывается поиск C, в 3-узел (второй сверху рисунок). Аналогично можно вставить ключ H, преобразовав 3-узел, в котором прерывается его поиск, в 4-узел (третий сверху рисунок). Но вставка ключа I выполняется сложнее, поскольку его поиск прерывается в 4-узле. Мы разбиваем 4-узел, передаем его средний ключ родительскому узлу, и преобразуем этот узел в 3-узел (четвертый сверху рисунок в рамке). Такое преобразование создает допустимое 2-3-4-дерево, в нижней части которого появляется место для I . И, наконец, мы вставляем I в 2-узел, на котором теперь прерывается поиск, и преобразуем этот узел в 3-узел (нижний рисунок).

(рис 13.12) Разбиение 4-узлов в 2-3-4-дереве

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

(рис 13.13)

Построение 2-3-4-дерева

Здесь показан результат вставки элементов с ключами A S E R C H I N G X в первоначально пустое 2-3-4-дерево. Каждый встречающийся по пути поиска 4-узел разбивается, обеспечивая свободное место для нового элемента в нижней части дерева.

На рис 13.13 показано построение 2-3-4-дерева последовательной вставкой набора ключей. В отличие от стандартных BST-деревьев, которые разрастаются вниз от вершины, эти деревья растут снизу вверх. Поскольку 4-узлы разбиваются на пути от вершины вниз, такие деревья называются нисходящими 2-3-4-деревьями. Этот алгоритм важен, поскольку он создает практически идеально сбалансированные деревья поиска, хотя в процессе прохождения по дереву выполняется всего лишь несколько локальных преобразований.

Лемма 13.6. При поиске в 2-3-4-деревьях из N узлов посещается максимум lgN+1 узлов.

Каждый внешний узел находится на одинаковом расстоянии от корня: выполняемые преобразования не оказывают никакого влияния на расстояние между любым узлом и корнем, за исключением случая, когда выполняется разбиение корня (в этом случае расстояние между всеми узлами и корнем увеличивается на 1). Если все узлы являются 2-узлами, приведенное утверждение справедливо, поскольку такое дерево подобно полному бинарному дереву; если в дереве присутствуют 3- и 4-узлы, высота может быть только меньше. $$$\blacksquare$$$

Лемма 13.7. Для вставок в 2-3-4-деревьях из N узлов требуется разбиение менее lg N + 1 узлов в худшем случае и, скорее всего, менее одного разбиения узла в среднем.

В самом худшем случае все узлы на пути к точке вставки являются 4-узлами, и все потребуется разбить. Но в дереве, построенном из случайной перестановки N элементов, маловероятен не только этот худший случай, но и в среднем, вероятно, потребуется очень мало операций разбиения, поскольку 4-узлы в деревьях встречаются не так часто. Например, в большом дереве на рис. 13.14 рис 13.14 все 4-узлы, кроме двух, расположены на нижнем уровне. До сих пор специалистам не удавалось аналитически точно проанализировать производительность 2-3-4-деревьев, но из эмпирически полученных результатов видно, что для балансировки деревьев используется очень мало разбиений. Худший случай равен лишь lg N, а в практических ситуациях и он недостижим. $$$\blacksquare$$$

Приведенного описания достаточно для определения алгоритма поиска с использованием 2-3-4-деревьев, который гарантирует достаточно высокую производительность в худшем случае. Однако мы находимся лишь на полпути к реализации. Можно написать алгоритмы, действительно выполняющие преобразования с различными типами данных, представляющими 2-, 3- и 4-узлы, но в большинстве встречающихся задач реализация такого непосредственного представления не очень удобна. Как и в случае скошенных BST-деревьев, дополнительные расходы на обработку более сложных узлов могут сделать алгоритмы более медленными, чем стандартный поиск по BST-дереву. Главное назначение балансировки — страховка от худшего случая, но хотелось бы, чтобы затраты, связанные с этим, были низкими, и чтобы не было дополнительных затрат при каждом выполнении алгоритма. К счастью, как будет показано в разделе 13.4, существует довольно простое представление 2-, 3- и 4-узлов, которое позволяет выполнять преобразования однотипным способом при небольших дополнительных затратах по сравнению со стандартным поиском в бинарном дереве.

(рис 13.14) Большое 2-3-4-дерево

Это 2-3-4-дерево — результат 200 случайных вставок в первоначально пустое дерево. Все пути поиска в дереве содержат не более шести узлов.

Описанный алгоритм — всего лишь один из возможных способов поддержания баланса в 2-3-4-деревьях поиска. Разработаны и некоторые другие методы, позволяющие достичь таких же результатов.

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

Такой вид восходящей балансировки можно выполнять в деревьях, которые содержат только 2- или 3-узлы (и не имеют 4-узлов). Это подход ведет к большему количеству операций разбиения узлов во время выполнения алгоритма, но его проще программировать, поскольку приходится учитывать меньше случаев. Еще один подход уменьшает количество разбиений узлов, отыскивая перед разбиением 4-узла его родственные узлы, не являющиеся 4-узлами.

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

Упражнения

13.39. Нарисуйте сбалансированное 2-3-4-дерево поиска, образованное нисходящими вставками элементов с ключами E A S Y Q U T I O N в указанном порядке в первоначально пустое дерево.

13.40. Нарисуйте сбалансированное 2-3-4-дерево поиска, образованное восходящими вставками элементов с ключами E A S Y Q U T I O N в указанном порядке в первоначально пустое дерево.

13.41. Какова минимальная и максимальная возможная высота сбалансированных 2-3-4-деревьев, содержащих N узлов?

13.42. Какова минимальная и максимальная возможная высота сбалансированных 2-3-4-деревьев бинарного поиска, содержащих N узлов?

13.43. Нарисуйте все структурно различные сбалансированные 2-3-4-деревья бинарного поиска, содержащие N ключей, для $$$2 \leq N\leq 12$$$.

13.44. Найдите вероятность того, что каждое из деревьев, нарисованных в упражнении 13.43, является результатом вставки N случайных различных элементов в первоначально пустое дерево.

13.45. Составьте таблицу, содержащую количество изоморфных деревьев из упражнения 13.43 для каждого значения N — в том смысле, что они могут быть преобразованы одно в другое путем обмена поддеревьев в узлах.

13.46. Опишите алгоритмы поиска и вставки в сбалансированные 2-3-4-5-6-деревья поиска.

13.47. Нарисуйте несбалансированное 2-3-4-дерево поиска, образованное вставками элементов с ключами E A S Y Q U T I O N в указанном порядке в первоначально пустое дерево с использованием следующего метода. Если поиск завершается в 2-или 3-узле, он преобразовывается в 3- или 4-узел, как в сбалансированном алгоритме; если поиск завершается в 4-узле, соответствующая ссылка в этом 4-узле заменяется новым 2-узлом.

RB-деревья

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

Основная идея заключается в представлении 2-3-4-деревьев в виде стандартных BST-деревьев (содержащих только 2-узлы), но с добавлением в каждом узле дополнительного информационного бита для кодирования 3-узлов и 4-узлов. Мы будем считать, что ссылки могут быть двух различных типов: красные ссылки (R-ссылки), которые объединяют небольшие бинарные деревья, образующие 3-узлы и 4-узлы, и черные ссылки (B-ссылки), которые объединяют 2-3-4-дерево. А именно, как показано на рис 13.15, 4-узлы представляются тремя 2-узлами, соединенными R-ссылками, а 3-узлы — двумя 2-узлами, соединенными одной R-ссылкой. R-ссылка в 3-узле может быть левой или правой, следовательно, каждый 3-узел может быть представлен двумя способами.

В любом дереве на каждый узел указывает одна ссылка, значит, окрашивание ссылок эквивалентно окрашиванию узлов. Поэтому мы используем по одному дополнительному разряду в каждом узле для хранения цвета ссылки, указывающей на этот узел. 2-3-4-деревья, представленные таким образом, называются красно-черными (или RB-) деревьями бинарного поиска. Ориентация каждого 3-узла определяется динамикой алгоритма, который будет описан ниже. Можно было бы выдвинуть правило, чтобы все 3-узлы были ориентированы одинаково, но это ни к чему. Пример RB-дерева показан на рис 13.16. Если в нем исключить R-ссылки и свернуть соединяемые ими узлы, в результате получится 2-3-4-дерево, показанное на рис 13.10.

RB-деревья обладают двумя важными свойствами: (1) стандартный метод найти для BST-деревьев работает без всяких изменений; (2) существует прямое соответствие между RB-деревьями и 2-3-4-деревьями, поэтому, используя и сохраняя это соответствие, можно реализовать алгоритм обработки сбалансированного 2-3-4-дерева. Мы возьмем лучшее из обоих подходов: простой метод поиска по стандартному BST-дереву и простой метод вставки-балансировки в 2-3-4-дереве поиска.

(рис 13.15) 3-узлы и 4-узлы в RB-деревьях

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

Метод поиска не проверяет поле, представляющее цвет узла, поэтому механизм балансировки не увеличивает время выполнения основной процедуры поиска. Каждый ключ вставляется только один раз, но в типичном приложении его поиск может выполняться многократно, поэтому общее время поиска сокращается (поскольку деревья сбалансированы) за счет сравнительно небольших затрат (т.к. во время поиска балансировка не выполняется). Невелики и дополнительные затраты, связанные со вставкой: действия по балансировке нужно выполнять только при обнаружении 4-узлов, а в дереве их количество невелико, поскольку они всегда разбиваются. Внутренним циклом процедуры вставки является код продвижения вниз по дереву (как и для операций вставки или поиска-вставки в стандартных BST-деревьях), с добавлением одной дополнительной проверки: если узел имеет два дочерних R-узла, он является частью 4-узла. Столь небольшие дополнительные затраты — основной фактор, определяющий эффективность RB-деревьев бинарного поиска.

Рассмотрим теперь RB-представление двух преобразований, выполнение которых может потребоваться при обнаружении 4-узла. 2-узел с дочерним 4-узлом становится 3-узлом с двумя дочерними 2-узлами, а 3-узел с дочерним 4-узлом становится 4-узлом с двумя дочерними 2-узлами. Когда в нижнюю часть дерева добавляется новый узел, его можно представить в виде 4-узла, который должен быть разбит с передачей среднего узла вверх для вставки в тот нижний узел, в котором завершился поиск — нисходящий процесс гарантирует, что это либо 2-узел, либо 3-узел. Преобразование, требуемое при обнаружении 2-узла с дочерним 4-узлом, выполняется без труда, и такое же преобразование работает применительно к 3-узлу, " правильно " присоединенному к 4-узлу, как показано в двух первых примерах на рис 13.17.

Остаются еще две ситуации, которые могут возникнуть при обнаружении 3-узла с дочерним 4-узлом — они показаны в последних двух примерах на рис. 13.17 рис 13.17. (На самом деле существует четыре таких ситуации, поскольку другая ориентация 3-узлов может дать еще два зеркальных изображения.) В этих случаях простое разбиение 4-узла приводит к образованию двух последовательных R-ссылок, т.е. результирующее дерево не является 2-3-4-деревом в соответствии с принятыми соглашениями. Эта ситуация не так уж плоха, поскольку имеются три узла, соединенных R-ссылками: достаточно преобразовать дерево так, чтобы R-ссылки исходили из одного и того же узла.

К счастью, уже знакомые нам операции ротации — именно то, что необходимо для достижения требуемого эффекта. Начнем с более простого из двух оставшихся случаев — третьего примера на рис 13.17, где 4-узел, присоединенный к 3-узлу, разбивается с порождением двух идущих друг за другом одинаково ориентированных R-ссылок. Эта ситуация не возникла бы, если бы 3-узел был ориентирован по-другому — значит, нужно изменить структуру дерева, переключив ориентацию 3-узла и сведя тем самым этот случай ко второму, когда достаточно простого разбиения 4-узла. Изменение структуры дерева для переориентации 3-узла достигается выполнением единственной ротации с дополнительным требованием изменения цвета двух задействованных узлов. Осталось рассмотреть случай, когда 4-узел, соединенный с 3-узлом, разбивается и оставляет две идущие подряд R-ссылки, которые ориентированы по-разному. Выполнением ротации можно свести этот случай к случаю с одинаково ориентированными ссылками, который затем обрабатывается, как было описано выше. Это преобразование сводится к выполнению тех же операций, что и при выполнении двойных ротаций влево-вправо и вправо-влево, которые использовались в разделе 13.2 для скошенных BST-деревьев, хотя нужны кое-какие дополнительные действия для правильной переустановки цветов. Примеры операций вставки в RB-деревья приведены на рис 13.18 и 13.19.

(рис 13.16) RB-дерево

На этом рисунке изображено RB-дерево, содержащее ключи .

(рис 13.17) Разбиение 4-узлов в RB-дереве

В RB-дереве операция разбиения 4-узла, который не имеет родителем 4-узел, изменяет цвета узлов дерева, образующих 4-узел с последующим возможным выполнением одной или двух ротаций. Если родительский узел является 2-узлом (верхний рисунок) или 3-узлом с подходящей ориентацией (второй сверху рисунок), ротации не требуются. Если 4-узел располагается на центральной ссылке 3-узла (нижний рисунок), необходима двойная ротация; иначе достаточно одиночной ротации (третий сверху рисунок).

(рис 13.18) Вставка в RB-дерево

На этом рисунке показан результат (внизу) вставки записи с ключом I в RB-дерево (вверху). В этом случае процесс вставки состоит из разбиения 4-узла C с изменением цвета (в центре), последующим добавлением нового 2-узла в нижней части и преобразованием узла, содержащего ключ H, в 3-узел.

(рис 13.19) Вставка в RB-дерево с использованием ротаций

На этом рисунке показан результат (внизу) вставки записи с ключом G в RB-дерево (вверху). Для этого выполняется разбиение 4-узла с ключом I с изменением цвета (второй сверху рисунок), затем добавление нового узла в нижнюю часть (третий сверху рисунок) и, наконец, выполнение (с возвратом к каждому узлу на пути поиска после вызовов рекурсивных функций) ротации влево в узле C и ротации вправо в узле R, которые завершают процесс разбиения 4-узла.

Программа 13.6 является реализацией операции вставить для RB-деревьев, которая выполняет преобразования, приведенные на рис 13.17. Рекурсивная реализация позволяет изменять цвета 4-узлов при продвижении вниз по дереву (перед рекурсивными вызовами), а затем выполнять ротации при продвижении вверх по дереву (после рекурсивных вызовов). Эту программу было бы трудно понять без двух уровней абстракции, разработанных для ее реализации. Несложно убедиться, что рекурсивный подход реализует ротации, изображенные на рис 13.17; затем можно убедиться, что программа действительно реализует высокоуровневый алгоритм для 2-3-4-деревьев — разбивает 4-узлы при продвижении вниз по дереву, а затем вставляет новый элемент в 2- или 3-узел там, где путь поиска завершается в нижней части дерева.

Программа 13.6. Вставка в RB-деревья бинарного поиска

Данная функция реализует вставку в 2-3-4-деревья, используя их RB-представления. В тип node добавлен бит цвета red (и соответствующим образом расширен его конструктор): 1 означает, что узел красный, а 0 — черный. При продвижении вниз по дереву (перед рекурсивным вызовом) обнаруженные 4-узлы разбиваются путем изменения разрядов цвета во всех трех узлах. По достижении нижней части дерева для вставляемого элемента создается новый R-узел, и возвращается ссылка на него. При продвижении вверх по дереву (после рекурсивного вызова) проверяется, необходима ли ротация. Если путь поиска содержит две одинаково ориентированных R-ссылки, выполняется единственная ротация от верхнего узла, а затем разряды цвета изменяются так, чтобы получился правильный 4-узел. Если путь поиска содержит две по-разному ориентированных R-ссылки, выполняется единственная ротация от нижнего узла, в результате чего этот случай сводится к предыдущему, но уровнем выше.

  private:
    int red(link x)
      { if (x == 0) return 0; return x->red; }
    void RBinsert(link h, Item x, int sw)
      { if (h == 0)
          { h = new node(x); return; }
        if (red(h->l)  red(h->r))
          { h->red = 1; h->l->red = 0; h->r->red = 0; }
        if (x.key() < h->item.key())
          { RBinsert(h->l, x, 0);
            if (red(h)  red(h->l)  sw) rotR(h);
            if (red(h->l)  red(h->l->l))
              { rotR(h); h->red = 0; h->r->red = 1; }
          }
       else
        { RBinsert(h->r, x, 1);
          if (red(h)  red(h->r)  !sw) rotL(h);
          if (red(h->r)  red(h->r->r))
            { rotL(h); h->red = 0; h->l->red = 1; }
        }
      }
   public:
      void insert(Item x)
        { RBinsert(head, x, 0); head->red = 0; }
      

На рис. 13.20 рис 13.20, который можно считать более подробной версией рис 13.13, показано, как программа 13.6 строит RB-деревья, представляющие сбалансированные 2-3-4-деревья, с помощью вставки последовательности ключей. На рис 13.21 изображено дерево, построенное для большей последовательности; среднее количество узлов, проверяемых во время поиска случайного ключа в этом дереве, равно лишь 5,81. Сравните это значение со значением , и с 5,74 — наименьшим возможным для идеально сбалансированного дерева. Ценой лишь нескольких ротаций мы получаем дерево, сбалансированное гораздо лучше любого другого из приведенных в этой главе и состоящего из этих же ключей. Программа 13.6 — эффективный и сравнительно компактный алгоритм вставки, использующий структуру бинарного дерева, который гарантирует логарифмическое количество шагов для всех операций поиска и вставки. Это одна из немногих реализаций таблиц символов, обладающих подобным свойством, и ее стоит использовать в качестве библиотечной реализации, когда точно неизвестны свойства обрабатываемой последовательности ключей.

(рис 13.20) Построение RB-дерева

Здесь показана последовательность вставок записей с ключами A S E R C H I N X в первоначально пустое RB-дерево.

Лемма 13.8. Для поиска в RB-дереве с N узлами требуется менее 2lgN+2 сравнений.

Ротация в RB-дереве требуется только для разбиений, которые в 2-3-4-дереве соответствуют 3-узлу с последующим 4-узлом; таким образом, эта лемма — следствие леммы 13.2. Худший случай возникает тогда, когда путь к точке вставки состоит из чередующихся 3-узлов и 4-узлов. $$$\blacksquare$$$

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

Лемма 13.9. Для поиска в RB-дереве с N узлами, построенном из случайных ключей, в среднем требуется около 1,002 lgN сравнений.

Константа 1,002, установленная с помощью частичного анализа и моделирования (см. раздел ссылок), достаточно мала, чтобы считать RB-деревья оптимальными для практического применения, но вопрос о том, действительно ли RB-деревья являются асимптотически оптимальными, остается открытым. Равна ли 1 эта константа в предельном случае? $$$\blacksquare$$$

Поскольку в рекурсивной реализации программы 13.6 некоторые действия выполняются до рекурсивных вызовов, а некоторые — после них, ряд модификаций дерева выполняется при продвижении вниз, а ряд — на обратном пути вверх. Поэтому балансировка не выполняется в ходе лишь нисходящего прохождения. Это обстоятельство мало влияет на большинство приложений, поскольку глубина рекурсии гарантированно мала. Для некоторых приложений, связанных с несколькими независимыми процессами, которые обращаются к одному и тому же дереву, может потребоваться нерекурсивная реализация, которая в каждый момент времени активно оперирует только постоянным количеством узлов (см. упражнение 13.66).

Для приложения, которое хранит в дереве и другую информацию, операция ротации может оказаться дорогостоящей: возможно, придется обновлять информацию во всех узлах поддеревьев, затрагиваемых ротацией. Для таких приложений можно обеспечить, чтобы каждая вставка выполняла не более одной ротации, используя RB-деревья для реализации восходящих 2-3-4-деревьев поиска, которые описаны в конце раздела 13.3.

(рис 13.21) Большое RB-дерево бинарного поиска

Это RB-дерево — результат вставки случайно упорядоченных ключей в первоначально пустое дерево. Для выполнения неудачных поисков в этом дереве требуется от 6 до 12 сравнений.

Вставка в эти деревья вызывает разбиение 4-узлов на пути поиска, которое требует изменений цвета, но не выполнения ротаций в RB-представлении, за которыми следует одна одиночная или двойная ротация (один из случаев, показанных на рис 13.17), если первый 2-узел или 3-узел встречается выше на пути поиска (см. упражнение 13.59).

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

Как было сказано в конце раздела 13.3, RB-представления 2-3-4-деревьев входят в число нескольких схожих стратегий, которые были предложены для реализации сбалансированных бинарных деревьев (см. раздел ссылок). Как было показано, балансировка деревьев достигается операциями ротации: мы рассмотрели специфическое представление деревьев, которое упрощает принятие решения о моменте выполнения ротации. Другие представления деревьев ведут к другим алгоритмам, часть из которых мы сейчас кратко рассмотрим.

Старейшая и наиболее изученная структура данных для сбалансированных деревьев — сбалансированное по высоте, или AVL-дерево, исследованное Адельсоном-Вельским и Ландисом. Для этих деревьев характерно, что высоты двух поддеревьев каждого узла различаются максимум на 1. Если вставка приводит к тому, что высота одного из поддеревьев какого-либо узла увеличивается на 1, условие баланса может нарушиться. Однако в любом случае одна одиночная или двойная ротация восстановит баланс. Основанный на этом наблюдении алгоритм аналогичен методу восходящей балансировки 2-3-4-деревьев: выполняется рекурсивный поиск узла, затем, после рекурсивного вызова, выполняется проверка разбаланса и, при необходимости, одиночная или двойная ротация для восстановления баланса (см. упражнение 13.61). Для принятия решения о том, какие ротации нужно выполнять (если нужно), требуется знать, является ли высота каждого узла на 1 меньше, равна или на 1 больше высоты его родственного узла. Для прямого кодирования этой информации требуется по два бита на каждый узел, хотя, используя RB-абстракцию, можно обойтись и без дополнительной памяти (см. упражнения 13.62 и 13.65).

Поскольку 4-узлы не играют никакой специальной роли в алгоритме с использованием 2-3-4-деревьев, можно строить сбалансированные деревья по существу так же, но используя только 2-узлы и 3-узлы. Построенные таким образом деревья называются 2-3-деревьями; они были открыты Хопкрофтом (Hopcroft) в 1970 г. 2-3-деревья не обладают гибкостью, достаточной для построения удобного алгоритма нисходящей вставки. Кроме того, RB-структура может упростить реализацию, но восходящие 2-3-деревья не дают особых преимуществ по сравнению с восходящими 2-3-4-деревьями, поскольку для поддержания баланса по-прежнему требуются одиночные и двойные ротации. Восходящие 2-3-4-деревья несколько лучше сбалансированы и обладают тем преимуществом, что для каждой вставки требуется максимум одна ротация.

В будет рассмотрен еще один важный тип сбалансированных деревьев — расширение 2-3-4-деревьев, называемое B-деревьями. B-деревья допускают существование до M ключей в одном узле для больших значений M и широко используются в приложениях поиска, работающих с очень большими файлами.

Мы уже определили RB-деревья их соответствием 2-3-4-деревьям. Интересно также сформулировать непосредственные структурные определения.

Определение 13.3. RB-дерево бинарного поиска — это дерево бинарного поиска, в котором каждый узел помечен как красный (R) либо черный (B), с наложением дополнительного ограничения, что никакие два красных узла не могут появляться друг за другом на любом пути от внешней ссылки до корня.

Определение 13.4. Сбалансированное RB-дерево бинарного поиска — это RB-дерево бинарного поиска, в котором все пути от внешних ссылок до корня содержат одинаковое количество черных узлов.

А теперь рассмотрим альтернативный подход к разработке алгоритма с использованием сбалансированного дерева. В нем полностью игнорируется абстракция 2-3-4-дерева и формулируется алгоритм вставки, который сохраняет основное свойство сбалансированных RB-деревьев бинарного поиска с помощью ротаций. Например, использование восходящего алгоритма соответствует присоединению нового узла в нижней части пути поиска с помощью R-ссылки, затем продвижению вверх по пути поиска с выполнением ротаций или изменений цвета, как это делалось в случаях, представленных на рис 13.17, для разбиения любой встретившейся пары последовательных R-ссылок. Основные выполняемые при этом операции — те же, что и в программе 13.6 и в ее восходящем аналоге, но при этом имеются незначительные различия, поскольку 3-узлы могут быть ориентированы в любом направлении, операции могут выполняться в ином порядке и с равным успехом могут приниматься различные решения о выполнении ротаций.

Подведем итоги: используя RB-деревья для реализации сбалансированных 2-3-4-деревьев, можно разработать таблицу символов, в которой операция найти для ключа в файле, состоящем, скажем, из 1 миллиона элементов, может быть выполнена путем сравнения этого ключа приблизительно с 20 другими ключами. В худшем случае требуется не более 40 сравнений. Более того, с каждым сравнением связаны лишь небольшие накладные расходы, и поэтому быстрое выполнение операции найти гарантировано даже в очень больших файлах.

Упражнения

13.48. Нарисуйте RB-дерево бинарного поиска, образованное нисходящими вставками элементов с ключами E A S Y Q U T I O N в указанном порядке в первоначально пустое дерево.

13.49. Нарисуйте RB-дерево бинарного поиска, образованное восходящими вставками элементов с ключами E A S Y Q U T I O N в указанном порядке в первоначально пустое дерево.

13.50. Нарисуйте RB-дерево, образованное в результате вставки по порядку латинских букв от A до K в первоначально пустое дерево, а затем опишите, что обычно происходит при построении дерева в процессе вставки возрастающей последовательности ключей.

13.51. Приведите последовательность вставок, в результате которой будет создано RB-дерево, изображенное на рис 13.16.

13.52. Сгенерируйте два случайных RB-дерева с 32 узлами. Нарисуйте их (вручную или с помощью программы). Сравните их с (несбалансированными) BST-деревьями, построенными из этих же ключей.

13.53. Сколько различных RB-деревьев соответствуют 2-3-4-дереву, содержащему t3-узлов?

13.54. Нарисуйте все структурно различные RB-деревья поиска, содержащие N ключей, для $$$2 \leq N\leq 12$$$.

13.55. Для каждого из деревьев в упражнении 13.43 определите вероятность того, что оно является результатом вставки N случайных различных элементов в первоначально пустое дерево.

13.56. Составьте таблицу, в которой приведено количество деревьев для каждого значения N из упражнения 13.54, являющихся изоморфными в том смысле, что они могут быть преобразованы одно в другое путем обмена поддеревьев в узлах.

13.57. Покажите, что в RB-дереве, состоящем из N узлов, в худшем случае длина почти всех путей от корня к внешнему узлу равна 2lgN .

13.58. Сколько ротаций требуется в худшем случае для вставки в RB-дерево, состоящее из N узлов?

13.59. Используя RB-представление и тот же рекурсивный подход, что и в программе 13.6, реализуйте операции создать, найти и вставить для таблиц символов, основанных на использовании восходящих сбалансированных 2-3-4-деревьев. Совет: код может быть похож на программу 13.6, но должен выполнять операции в другом порядке.

13.60. Используя RB-представление и тот же рекурсивный подход, что и в программе 13.6, реализуйте операции создать, найти и вставить для таблиц символов, основанных на использовании восходящих сбалансированных 2-3-деревьев.

13.61. Используя тот же рекурсивный подход, что и в программе 13.6, реализуйте операции создать, найти и вставить для таблиц символов, основанных на использовании сбалансированных по высоте (AVL-) деревьев.

13.62. Измените реализацию из упражнения 13.61, чтобы использовать RB-деревья (содержащие по 1 биту на узел) для кодирования информации о балансе высоты.

13.63. Реализуйте сбалансированные 2-3-4-деревья, используя представление RB-дерева, в котором 3-узлы всегда наклонены вправо. Примечание: это изменение позволяет исключить из внутреннего цикла операции вставить одну битовую проверку.

13.64. Для сохранения сбалансированности 4-узлов программа 13.6 выполняет ротации. Разработайте использующую представление в виде RB-дерева реализацию сбалансированных 2-3-4-деревьев, в которой 4-узлы могут быть представлены любыми

тремя узлами, соединенными двумя R-ссылками (полностью сбалансированными или несбалансированными).

13.65. Не используя дополнительную память для хранения бита цвета, реализуйте для RB-деревьев операции создать, найти и вставить, воспользовавшись следующим приемом. Чтобы окрасить узел в красный цвет, поменяйте местами две его ссылки. А чтобы проверить, является ли узел красным, проверьте, больше ли его левый дочерний узел, чем правый. Для обеспечения возможного обмена ссылок придется модифицировать функции сравнения. Этот прием заменяет сравнения битов сравнениями ключей, что может потребовать больших затрат, однако он демонстрирует, что в случае необходимости можно избавиться от дополнительного поля в узлах.

13.66. Реализуйте нерекурсивную функцию вставки в RB-дерево бинарного поиска (см. программу 13.6), соответствующую вставке в сбалансированное 2-3-4-дерево за один проход. Совет: введите ссылки gg, g и p, которые указывают, соответственно, на прадеда, деда и родителя текущего узла в дереве. Все эти ссылки могут потребоваться для выполнения двойной ротации.

13.67. Напишите программу, которая вычисляет долю B-узлов в заданном RB-дереве бинарного поиска. Протестируйте программу, вставив N случайных ключей в первоначально пустое дерево, для N = 103, 104, 105 и 106 .

13.68. Напишите программу, которая вычисляет долю элементов, находящихся в 3-узлах и 4-узлах заданного 2-3-4-дерева поиска. Протестируйте программу, вставив N случайных ключей в первоначально пустое дерево, для N = 103, 104, 105 и 106 .

13.69. Используя по одному биту на узел для представления цвета, можно представлять 2-, 3- и 4-узлы. Сколько битов на узел потребовалось бы для представления бинарным деревом 5-, 6-, 7- и 8-узлов?

13.70. Эмпирически вычислите среднее значение и среднеквадратичное отклонение количества сравнений, используемых при успешном и неудачном поиске в RB-дереве, построенном вставками N случайных узлов в первоначально пустое дерево, для N = 103, 104, 105 и 106 .

13.71. Добавьте в программу из упражнения 13.70 возможность подсчета количества ротаций и разбиений узлов, используемых для построения деревьев. Проанализируйте полученные результаты.

13.72. Воспользуйтесь программой-драйвером из упражнения 12.30 для сравнения самоорганизующегося поиска в скошенных BST-деревьях с гарантированной производительностью, обеспечиваемой в худшем случае RB-деревьями бинарного поиска, и со стандартными BST-деревьями для распределений запросов на поиск, определенных в упражнениях 12.31 и 12.32 (см. упражнение 13.29).

13.73. Реализуйте функцию найти для RB-деревьев, которая выполняет ротации и изменяет цвета узлов при продвижении вниз по дереву, чтобы обеспечить, что узел в нижней части пути поиска не является 2-узлом.

13.74. Воспользуйтесь решением упражнения 13.73 для реализации функции удалить для RB-деревьев. Найдите узел, который должен быть удален, продолжите поиск до нахождения 3-узла или 4-узла в нижней части пути и переместите узел-наследник из нижней части, чтобы заменить удаленный узел.

Слоеные списки

В этом разделе мы рассмотрим способ разработки быстрых реализаций операций с таблицами символов, который на первый взгляд кажется совершенно не похожим на рассмотренные методы на базе деревьев, хотя в действительности они очень тесно связаны. Этот подход основан на рандомизированной структуре данных и практически наверняка обеспечивает почти оптимальную производительность всех базовых операций для АТД таблицы символов. Лежащая в основе алгоритма структура данных, которая была разработана Пуфом (Pugh) в 1990 г. (см. раздел ссылок), называется слоеным списком (skip list, часто переводится как " список пропусков " ). В ней используются дополнительные ссылки в узлах связного списка для пропуска больших частей списка во время поиска.

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

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

Определение 13.5. Слоеный список — это упорядоченный связный список, в котором каждый узел содержит различное количество ссылок, причем i-е ссылки в узлах образуют односвязные списки, пропускающие узлы с менее чем i ссылками.

На рис 13.23 изображен этот же слоеный список и приведен пример поиска и вставки нового узла. Для выполнения поиска просматривается верхний список, пока не будет найден ключ поиска или узел с меньшим ключом, содержащий ссылку на узел с большим ключом. Затем мы переходим ко второму сверху списку и повторяем эту процедуру, продолжая этот процесс, пока не будет найден искомый ключ или пока на нижнем уровне не будет обнаружено его отсутствие. Для вставки выполняется поиск со вставкой в списки нового узла при переходе с уровня k на уровень k — 1, если новый узел содержит не менее k дополнительных ссылок.

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

(рис 13.22) Двухуровневый связный список

Каждый третий узел в этом списке содержит вторую ссылку, поэтому можно " скакать " по списку с почти в три раза большей скоростью по сравнению с использованием только первых ссылок. Например, до двенадцатого узла в списке (P), можно добраться из начала списка, пройдя лишь по пяти ссылкам: по вторым ссылкам на C, G, L, N, а затем по первой ссылке узла N на P.

(рис 13.23) Поиск и вставка в слоеном списке

Добавляя дополнительные уровни к структуре, показанной на рис 13.22, и позволяя ссылкам пропускать различное количество узлов, мы получаем пример обобщенного списка пропусков. Для поиска ключа в этом списке процесс начинается с самого верхнего уровня с переходом вниз при каждой встрече ключа, который не меньше ключа поиска. Вот как выполняется (вверху) поиск ключа L: начав с уровня 3, следуем по первой ссылке, затем спускаемся по G (считая пустые ссылки ссылками на сигнальные узлы), затем до I, спускаемся на уровень 2, поскольку S больше чем L, затем спускаемся на уровень 1, поскольку M больше L. Для вставки узла L с тремя ссылками мы связываем его с тремя списками там, где при поиске были обнаружены ссылки на большие ключи.

Управление памятью — вероятно, наиболее сложный аспект использования слоеных списков. Объявления типов и код для выделения памяти под новые узлы будут рассмотрены при обсуждении алгоритма вставки. Пока же достаточно отметить, что доступ к узлу, который следует за узлом t на (к + 1)-ом уровне слоеного списка, обеспечивается выражением t->next[k]. Рекурсивная реализация в программе 13.7 демонстрирует, что поиск в слоеных списках не только является очевидным обобщением поиска в односвязных списках, но и подобен бинарному поиску или поиску в BST-деревьях. Вначале проверяется, содержится ли ключ поиска в текущем узле; если нет, ключ в текущем узле сравнивается с ключом поиска. Если он больше, выполняется один рекурсивный вызов, а если меньше — другой.

Программа 13.7. Поиск в слоеных списках

Для k, равного 0, этот код эквивалентен программе 12.6, выполняющей поиск в односвязных списках. Для общего случая k мы переходим к следующему узлу списка на уровне k, если его ключ меньше ключа поиска, и вниз на уровень k-1, если его ключ не меньше.

  private:
    Item searchR(link t, Key v, int k)
    { if (t == 0) return nullItem;
      if (v == t->item.key()) return t->item;
      link x = t->next[k];
      if ((x == 0) || (v < x->item.key()))
        { if (k == 0) return nullItem;
          return searchR(t, v, k-1);
        }
      return searchR(x, v, k);
    }
  public:
    Item search(Key v)
    { return searchR(head, v, lgN); }
      

Первой задачей, с которой мы сталкиваемся при необходимости вставки нового узла в слоеный список, является определение количества ссылок, которые должен содержать узел. Все узлы содержат по меньшей мере одну ссылку; следуя интуитивному представлению, отображенному на рис 13.22, на втором уровне можно пропускать сразу по t узлов, если один из каждых t узлов содержит по меньшей мере две ссылки; продолжая далее, мы приходим к заключению, что один из каждых t^j узлов должен содержать по меньшей мере j + 1 ссылок.

Для создания узлов с таким свойством мы выполняем рандомизацию с помощью функции, которая возвращает значение j + 1 с вероятностью 1/tj . Имея j, мы создаем новый узел с j ссылками и вставляем его в слоеный список, применяя рекурсивную схему, которая используется для операции найти, как показано на рис 13.23. После достижения уровня j мы включаем новый узел в список при каждом спуске на уровень ниже. К этому моменту уже установлено, что элемент в текущем узле меньше ключа поиска и указывает (на уровне j) на узел, не меньший ключа поиска.

(рис 13.24) Построение слоеного списка

Здесь показан процесс вставки элементов с ключами A S E R C H I N G в первоначально пустой слоеный список. Узлы содержат j ссылок с вероятностью 1/2j .

При инициализации слоеного списка создается ведущий узел с максимальным количеством уровней, разрешенным в этом списке, и пустыми ссылками на всех уровнях. В программах 13.8 и 13.9 реализованы инициализация и вставка для слоеных списков.

На рис 13.24 показано построение слоеного списка из набора ключей, вставляемых в случайном порядке; а на рис 13.25 приведен более объемный пример. На рис 13.26 показано построение слоеного списка для тех же ключей, что и на рис 13.24, но вставляемых в порядке возрастания. Как и для рандомизированных BST-деревьев, стохастические свойства слоеных списков не зависят от порядка вставки ключей.

Лемма 13.10. Для поиска и вставки в рандомизированный слоеный список с параметром t в среднем требуется порядка $$$(t\log_{t}{N})/2=(t/(2\lg{t}))\lg{N}$$$ сравнений.

Мы ожидаем, что слоеный список должен иметь порядка $$$t\log_{t}{N}$$$ уровней, поскольку $$$t\log_{t}{N}$$$ больше наименьшего значения j, для которого tj = N . На каждом уровне мы ожидаем, что на предыдущем уровне было пропущено примерно t узлов, а перед спуском на следующий уровень придется перебрать приблизительно половину из них. Как видно из примера на рис 13.25, количество уровней мало, но точное аналитическое обоснование этого свойства довольно сложно (см. раздел ссылок). $$$\blacksquare$$$

Программа 13.8. Структуры данных и конструктор слоеного списка

Узлы в слоеных списках содержат массив ссылок, поэтому конструктор класса node должен выделить памяти под этот массив и обнулить все его ссылки. Константа lgNmax — максимальное количество уровней, которое разрешено в списке: ее значение можно задать равным пяти для совсем маленьких списков или 30 — для огромных. Переменная N, как обычно, содержит количество элементов в списке, а lgN — количество уровней. Пустой список является ведущим узлом с lgNmax пустыми ссылками, при этом N и lgN должны быть равны 0.

  private:
    struct node
      { Item item; node **next; int sz;
        node(Item x, int k)
          { item = x; sz = k; next = new node*[k];
            for (int i = 0; i < k; i++) next[i] = 0;
          }
      };
    typedef node *link;
    link head;
    Item nullItem;
    int lgN;
  public:
    ST(int)
      { head = new node(nullItem, lgNmax); lgN = 0; }
      

Программа 13.9. Вставка в слоеные списки

Мы генерируем новый j-связный узел с вероятностью 1 / 2j , затем перемещаемся по пути поиска точно так же, как в программе 13.7, но включаем новый узел при спуске на каждый из j нижних уровней.

  private:
    int randX()
      { int i, j, t = rand();
        for (i = 1, j = 2; i < lgNmax; i++, j += j)
          if (t > RAND MAX/j) break;
        if (i > lgN) lgN = i;
        return i;
      }
  void insertR(link t, link x, int k)
    { Key v = x->item.key(); link tk = t->next[k];
      if ((tk == 0) || (v < tk->item.key()))
        { if (k < x->sz)
            { x->next[k] = tk; t->next[k] = x; }
          if (k == 0) return;
          insertR(t, x, k-1); return;
        }
      insertR(tk, x, k);
    }
  public:
    void insert(Item v)
      { insertR(head, new node(v, randX()), lgN); }
      

(рис 13.25) Большой слоеный список

Здесь показан результат вставки в случайном порядке 50 ключей в первоначально пустой список. Доступ к каждому из ключей можно получить, пройдя не более чем по 7 ссылкам.

Лемма 13.11. Слоеные списки содержат в среднем (t / (t — 1)) N ссылок.

Имеется N ссылок на нижнем уровне, N/t ссылок на первом уровне, около N/t² ссылок на втором уровне и т.д., что в сумме дает примерно $$$$N (1 + 1/t + 1/t^{2} + 1/t^{3}...) = N/ (1 - 1/t )$$$$ ссылок во всем списке. $$$\blacksquare$$$

Выбор подходящего значения t приводит нас к обычному балансу между временем выполнения и требуемым объемом памяти. При t = 2 в слоеных списках требуется в среднем около lg N сравнений и 2N ссылок — показатель, сравнимый с лучшей производительностью при использовании BST-деревьев. Для больших значений t время поиска и вставки увеличивается, но объем дополнительной памяти, требуемой для ссылок, уменьшается. Продифференцировав выражение из свойства 13.10, можно определить, что ожидаемое количество сравнений, требуемое для выполнения поиска в слоеном списке, минимально при t = e.

В следующей таблице приведены значения коэффициента при Nlg N в выражении, где определяется количество сравнений, необходимых для построения таблицы из N элементов:

t	2	e	3	4	8	16
lg t	1,00	1,44	1,58	2,00	3,00	4,00
t / lg t	2,00	1,88	1,89	2,00	2,67	4,00

Если для выполнения сравнений, переходов по ссылкам и рекурсивного спуска требуются затраты, которые существенно отличаются от приведенных значений, можно аналогично выполнить более точные расчеты (см. упражнение 13.83).

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

Реализация других функций таблицы символов с помощью слоеных списков очевидна. Например, в программе 13.10 приведена реализация операции удалить, в которой применяется та же рекурсивная схема, что и для операции вставить в программе 13.9. Для удаления узла он удаляется из всех списков (в которые он был включен операцией вставить), и после удаления узла из нижнего списка он освобождается (в отличие от его создания перед просмотром списка для вставки). Операция объединить реализуется с помощью объединения списков (см. упражнение 13.78); для реализации операции выбрать в каждый узел добавляется поле, содержащее количество узлов, пропущенных ссылкой на него самого высокого уровня (см. упражнение 13.77).

(рис 13.26) Построение списка пропусков, содержащего упорядоченные ключи

Здесь показан процесс вставки элементов с ключами A C E G H I N R S в первоначально пустой слоеный список. Стохастические свойства списка не зависят от порядка вставки ключей.

Программа 13.10. Удаление в слоеных списках

Для удаления из слоеного списка узла с заданным ключом мы удаляем его из списка каждого уровня, в который он включен, а затем, по достижении нижнего уровня, удаляем сам узел.

  private:
    void removeR(link t, Key v, int k)
      { link x = t->next[k];
        if (!(x->item.key() < v))
          { if (v == x->item.key())
              { t->next[k] = x->next[k]; }
            if (k == 0) { delete x; return; }
            removeR(t, v, k-1); return;
          }
        removeR(t->next[k], v, k);
      }
  public:
    void remove(Item x)
      { removeR(head, x.key(), lgN); }
      

Слоеные списки легко обобщить в качестве систематического способа быстрого перемещения по связному списку, однако важно понимать, что лежащая в их основе структура данных — всего лишь альтернативное представление сбалансированного дерева. Например, на рис 13.27 приведено представление в виде слоеного списка сбалансированного 2-3-4-дерева с рис 13.10.

Алгоритмы для сбалансированного 2-3-4-дерева из раздела 13.3 можно реализовать, используя абстракцию слоеного списка, а не абстракцию RB-дерева из раздела 13.4. Результирующий код получается при этом несколько сложнее кода рассмотренных представлений (см. упражнение 13.80). В мы еще вернемся к этой взаимосвязи между слоеными списками и сбалансированными деревьями.

Идеальный слоеный список, показанный на .

(рис 13.27) Представление 2-3-4-дерева в виде слоеного списка

Здесь представлено 2-3-4-дерево с рис 13.10 в виде слоеного списка. В общем случае слоеные списки соответствуют сбалансированным многопутевым деревьям с одной или более ссылкой на узел (допускаются и 1-узлы без ключей и с 1 ссылкой). Для построения слоеного списка, соответствующего дереву, мы присваиваем каждому узлу количество ссылок, равное его высоте в дереве, а затем связываем узлы по горизонтали. Для построения дерева, соответствующего слоеному списку, мы группируем пропущенные узлы и рекурсивно связываем их с узлами на следующем уровне.

Упражнения

13.75. Нарисуйте слоеный список, образованный вставками элементов с ключами E A S Y Q U T I O N в указанном порядке в первоначально пустой список, если функция randX возвращает последовательность значений 1, 3, 1, 1, 2, 2, 1, 4, 1 и 1.

13.76. Нарисуйте слоеный список, образованный вставками элементов с ключами E A I N O Q S T U Y в указанном порядке в первоначально пустой список, если функция randX возвращает такие же значения, как и в упражнении 13.75.

13.77. Реализуйте операцию выбрать для таблицы символов на основе слоеного списка.

13.78. Реализуйте операцию объединить для таблицы символов на основе слоеного списка.

13.79. Измените реализации операций найти и вставить, приведенные в программах 13.7 и 13.9, так, чтобы списки заканчивались не пустыми ссылками, а сигнальными узлами.

13.80. С помощью слоеных списков реализуйте операции создать, найти и вставить для таблиц символов, использующих абстракцию сбалансированного 2-3-4-дерева.

13.81. Сколько случайных чисел требуется в среднем для построения слоеного списка с параметром t, если используется функция randX из программы 13.9?

13.82. Для t = 2 измените программу 13.9 так, чтобы в функции randX исключить цикл for. Совет: последние j разрядов в двоичном представлении числа t принимают значение любого отдельного разряда j с вероятностью 1/2^j.

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

13.84. Разработайте реализацию слоеного списка, в которой узлы содержат сами ссылки, а не ссылку на массив ссылок, как в программах 13.7 — 13.10. Совет: поместите массив в конец узла.

Характеристики производительности

Как для конкретного приложения осуществить выбор между рандомизированными BST-деревьями, скошенными BST-деревьями, RB-деревьями бинарного поиска и слоеными списками? До сих пор наше внимание было сосредоточено на различной природе гарантирования производительности, которую обеспечивают эти алгоритмы. Главными определяющими факторами всегда являются время и память, но необходимо учитывать и ряд других аспектов. В этом разделе мы кратко рассмотрим вопросы реализации, эмпирические исследования, оценки времени выполнения и требования к памяти.

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

Из трех основанных на деревьях алгоритмов проще всего реализовать рандомизированные BST-деревья. Здесь главные требования — надежность генератора случайных чисел и не слишком большие затраты времени на генерацию случайных битов. Скошенные деревья несколько более сложны, но являются очевидным обобщением стандартного алгоритма вставки в корень. RB-деревья бинарного поиска требуют еще немного большего кодирования, поскольку в них нужно проверять и изменять биты цвета. Одно из преимуществ RB-деревьев по сравнению с двумя другими алгоритмами — возможность использования битов цвета для проверки логики при отладке и для обеспечения быстрого поиска в любой момент времени на протяжении жизни дерева. Рассматривая скошенное BST-дерево, невозможно выяснить, все ли необходимые преобразования выполнил создавший его код; программная ошибка может приводить (только!) к проблемам, связанным с производительностью. Аналогично, ошибка в генераторе случайных чисел, используемом для рандомизированных BST-деревьев или слоеных списков, может привести к не замеченным в противном случае проблемам производительности.

Слоеные списки легко реализовать, и они особенно привлекательны, если требуется поддерживать полный набор операций для таблиц символов, поскольку для них можно легко сформулировать и естественно реализовать все операции — найти, вставить, удалить, объединить, выбрать и сортировать. Внутренний цикл для выполнения поиска в слоеных списках длиннее, чем в деревьях (для него требуется дополнительный индекс в массиве ссылок или дополнительный рекурсивный вызов для спуска на уровень ниже), поэтому время поиска и вставки несколько увеличено. Кроме того, слоеные списки ставят программиста в зависимость от генератора случайных чисел, поскольку отладка программы, поведение которой носит случайный характер — весьма сложная задача, и некоторые программисты очень не любят работать с узлами, содержащими случайное количество ссылок.

В , для 32-разрядных целых ключей. Приведенные в этой таблице данные подтверждают аналитические результаты, полученные в разделах 13.2, 13.4 и 13.5. RB-деревья работают со случайными ключами гораздо быстрее, чем другие алгоритмы. Пути в них на 35% короче, чем в рандомизированных или скошенных BST-деревьях, а в их внутренних циклах выполняется меньше действий. Рандомизированные деревья и слоеные списки требуют генерации по меньшей мере одного случайного числа для каждой вставки, а скошенные BST-деревья выполняют ротацию в каждом узле для каждой вставки и каждого поиска. Дополнительные затраты при использовании RB-деревьев бинарного поиска заключаются в проверке значений двух битов в каждом узле во время вставки, а иногда приходится выполнять и ротацию. При неравномерном доступе скошенные BST-деревья могут обеспечить более короткие пути, но эта экономия, скорее всего, будет перекрыта тем, что и для поиска, и для вставки потребуются ротации в каждом узле во внутреннем цикле, за исключением, быть может, крайних случаев.

Экспериментальное сравнение реализаций сбалансированных деревьев

N	Построение						Неудачные поиски
	B	T	R	S	C	L	B	T	R	S	C	L
1250	0	1	3	2	1	2	1	1	0	0	0	2
2500	2	4	6	3	1	4	1	1	1	2	1	3
5000	4	7	14	8	5	10	3	3	3	3	2	7
12500	11	23	43	24	16	28	10	9	9	9	7	18
25000	27	51	101	50	32	57	19	19	26	21	16	43
50000	63	114	220	117	74	133	48	49	60	46	36	98
100000	159	277	447	282	177	310	118	106	132	112	84	229
200000	347	621	996	636	411	670	235	234	294	247	193	523

Обозначения:
B	Стандартное BST-дерево (программа 12.8)
T	BST-дерево, построенное вставками в корень (программа 12.13)
R	Рандомизированное BST-дерево (программа 13.2)
S	Скошенное BST-дерево (упражнение 13.33 и программа 13.5)
C	RB-дерево бинарного поиска (программа 13.6)
L	Слоеный список (программы 13.7 и 13.9)

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

Скошенные BST-деревья не требуют использования дополнительной памяти под информацию о балансе; RB-деревья бинарного поиска требуют 1 дополнительный бит, а рандомизированные BST-деревья требуют наличия поля счетчика. Во многих приложениях поле счетчика используется и для других целей, поэтому для рандомизированных BST-деревьев оно может и не вызывать дополнительных затрат. На самом деле добавление этого поля может потребоваться и при использовании скошенных BST-деревьев, RB-деревьев бинарного поиска или слоеных списков. При необходимости RB-деревья бинарного поиска можно сделать столь же эффективными по памяти, как и скошенные BST-деревья, исключив бит цвета (см. упражнение 13.65). В современных приложениях объем памяти не столь важен, как когда-то, однако аккуратный программист всегда избегает напрасных затрат. Например, необходимо помнить, что некоторые системы для небольшого поля счетчика или 1-разрядного поля цвета в узле могут использовать целое 32-разрядное слово, а некоторые другие системы могут упаковывать поля в памяти так, что их распаковка требует значительного дополнительного времени. Если объем памяти ограничен, слоеные списки с большим параметром t могут уменьшить объем памяти, требуемый для ссылок, почти в два раза — ценой более медленного (но все же логарифмического) поиска. Некоторые приемы позволяют реализовать основанные на деревьях методы с использованием лишь одной ссылки на узел (см. упражнение 12.68).

Подводя итоги, можно сказать, что все рассмотренные в этой главе методы обеспечивают высокую производительность типичных приложений, при этом каждый метод обладает собственными достоинствами для тех, кто заинтересован в разработке высокопроизводительных реализаций таблиц символов. Скошенные BST-деревья обеспечивают высокую производительность как метод самоорганизующегося поиска, особенно когда типичны частые обращения к небольшому набору ключей. Рандомизированные BST-деревья обычно работают быстрее, и с их помощью легче реализовать полнофункциональные таблицы символов. Слоеные списки просты для понимания и могут обеспечить логарифмическую зависимость времени поиска при меньших по сравнению с другими методами затратах памяти. А RB-деревья бинарного поиска привлекательны для библиотечных реализаций таблицы символов, поскольку они обеспечивают гарантированные границы производительности в худшем случае и наиболее быстрые алгоритмы поиска и вставки случайных данных.

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

Упражнения

13.85. Разработайте реализацию таблицы символов, использующую рандомизированные BST-деревья, которая содержит деструктор, конструктор копирования и перегруженную операцию присваивания и поддерживает операции создать, подсчитать, найти, вставить, удалить, объединить, выбрать и сортировать для АТД таблицы символов первого класса с поддержкой клиентских дескрипторов элементов (см. упражнения 12.6 и 12.7).

13.86. Разработайте реализацию таблицы символов, использующую слоеные списки, которая содержит деструктор, конструктор копирования и перегруженную операцию присваивания и поддерживает операции создать, подсчитать, найти, вставить, удалить, объединить, выбрать и сортировать для АТД таблицы символов первого класса с поддержкой клиентских дескрипторов элементов (см. упражнения 12.6 и 12.7).