Двоичные деревья поиска

// Если удаляем корень дерева, надо указать новый корень дерева

  If (del.nodeParent == NIL) Then

    Tree.root = nodeTemp;

  Else

  Begin

    // Указываем родителю удаляемой вершины качестве потомка

    // потомок удаляемой вершины

    If (del.nodeParent.left == del) Then

      del.nodeParent.left = nodeTemp;

    Else

      del.nodeParent.right = nodeTemp;

  End

  If (del != node) Then // Если случай 3

  Begin

    node.key = del.key; // Скопировать ключ

    { копирование дополнительных данных }

  End

  Return del;

End

NIL, NULL и маленькие хитрости

Нередко алгоритмы, просто выглядящие на бумаге, становятся нагромождением сплошных конструкций if в реальной программе. Почему? Ответ очевиден: многие алгоритмы для работы с деревьями предполагают, что (NIL).parent == (NIL).left == (NIL).right == NIL. Вроде всё ясно и даже логично, но ведь во многих языках программирования NIL/NULL – это ноль. А обращение по нулевому адресу памяти чревато нехорошими вещами. Что же делать? Ведь мало того, что все эти if тормозят программу, в них легко запутаться! Решение просто: мы не будем использовать NIL! Действительно, алгоритмам совершенно всё равно, какое численное значение имеет NIL, главное, чтобы адрес любой реальной вершины в дереве не был ему равен. Поэтому вместо NIL мы будем использовать адрес переменной, проинициализированной особым образом. Я покажу это на языке С++, но думаю, этот пример можно будет перевести и на другие языки, хотя там, скорее всего, нет шаблонов, и придется пожертвовать типобезопасностью.

template <class CTree>class CTreeBase

{

protected:

  CTree * lpCParent;

  CTree * lpCLeft;

  CTree * lpCRight;

public:

  CTreeBase(CTreeBase * lpCParentInit, CTreeBase * lpCLeftInit,

    CTreeBase * lpCRightInit)

  {

    lpCParent = (CTree *)lpCParentInit;

    lpCLeft   = (CTree *)lpCLeftInit;

    lpCRight  = (CTree *)lpCRightInit;

  }

};

/////////////////////////////////////

class CTree : public CTreeBase<CTree>

{

private:

  int data;

protected:

  static CTreeBase<CTree> treeNil;

};

////////////////////////////////////////////////////////////

CTreeBase<CTree> CTree::treeNil(&treeNil, &treeNil, &treeNil);

Теперь везде в классе CTree можно использовать переменную treeNil. Преимущества очевидны. Потратив каких-то двенадцать (3 * sizeof(CTree *)) байт памяти, мы упростили разработку и ускорили выполнение программы.

Основная проблема использования ДДП

Основной проблемой использования ДДП является то, что методы вставки и удаления вершин, гарантируя сохранение свойства упорядоченности, совершенно не способствуют оптимизации основных операций над ДДП. Например, если вставить в ДДП последовательность возрастающих или убывающих чисел, оно превратится, по сути, в двусвязный список, а основные операции будут занимать время, пропорциональное количеству вершин, а не его логарифму.

Таким образом, для получения производительности порядка O(log2N) нужно, чтобы дерево имело как можно более высокую сбалансированность (то есть имело возможно меньшую высоту). Обычно выделяются несколько типов сбалансированности. Полная сбалансированность, это когда для каждой вершины дерева количества вершин в левом и правом поддеревьях различаются не более чем на 1. К сожалению, такой сбалансированности трудно добиться на практике. Поэтому на практике используются менее жесткие виды сбалансированности. Например, русскими математиками Г. М. Адельсон-Вельским и Е.М.Ландисом были разработаны принципы АВЛ деревьев. В АВЛ деревьях для каждой вершины дерева глубины обоих поддеревьев различаются не более чем на 1. Еще одним “продвинутым” видом деревьев является так называемые красно-чёрные деревья. АВЛ деревья обеспечивают более высокую сбалансированность дерева, но затраты на их поддержание выше. Поскольку на практике разница в сбалансированности между этими двумя видами деревьев не высока, чаще используются красно-чёрные деревья.

Красно-чёрные деревья (Red-Black Tree, RB-Tree)

Итак, одним из способов решения основной проблемы использования ДДП являются красно-чёрные деревья. Красно-чёрные (название исторически связано с игральными картами, поскольку из них легко делать простые модели) деревья (КЧД) – это ДДП, каждая вершина которых хранит ещё одно дополнительное логическое поле (color), обозначающее цвет: красный или чёрный. Фактически, в КЧД гарантируется, что уровни любых двух листьев отличаются не более, чем в два раза. Этого условия оказывается достаточно, чтобы обеспечить скоростные характеристики поиска, близкие к O(log2N). При вставке/замене производятся дополнительные действия по балансировке дерева, которые не могут не замедлить работу с деревом. При описании алгоритмов мы будем считать, что NIL – это указатель на фиктивную вершину, и операции (NIL).left, (NIL).right, (NIL).color имеют смысл. Мы также будем полагать, что каждая вершина имеет двух потомков, и лишь NIL не имеет потомков. Таким образом, каждая вершина становится внутренней (имеющей потомков, пусть и фиктивных), а листьями будут лишь фиктивные вершины NIL.

Свойства КЧД

Каждая вершина может быть либо красной, либо чёрной. Бесцветных вершин, или вершин другого цвета быть не может.

Каждый лист (NIL) имеет чёрный цвет.

Если вершина красная, то оба её потомка – чёрные.

Все пути от корня к листьям содержат одинаковое число чёрных вершин.

Пример КЧД с учётом наших положений приведен на рисунке 4. Учтите, что вершина 9 могла быть и красной, но в дальнейшем мы будем рассматривать только те деревья, у которых корень чёрный. Мы это сделаем для того, чтобы потомки корня могли иметь любой цвет.

Двоичные деревья поиска 

Рисунок 4.

Вращения

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

Двоичные деревья поиска 

Рисунок 5.

Как видно, вращения, перемещая вершины, не нарушают свойства упорядоченности.

В процедуре RBTLeftRotate предполагается, что node.right != NIL. В процедуре RBTRightRotate предполагается, что node.left != NIL.

RBTLeftRotate(Tree,node)

Begin

  nodeTemp = node.right;

  node.right = nodeTemp.left;

  If (nodeTemp.left != NIL) Then

    nodeTemp.left.nodeParent = node;

  nodeTemp.nodeParent = node.nodeParent;

  If (node.nodeParent == NIL) Then

    Tree.root = nodeTemp;

  Else

  Begin

    If (node == node.nodeParent.left) Then

      node.nodeParent.left = nodeTemp;

    Else

      node.nodeParent.right = nodeTemp;

  End

  nodeTemp.left = node;

  node.nodeParent = nodeTemp;

End

RBTRightRotate(Tree,node)

Begin

  nodeTemp = node.left;

  node.left = nodeTemp.right;

  If (nodeTemp.right != NIL) Then

    nodeTemp.right.nodeParent = node;

  nodeTemp.nodeParent = node.nodeParent;

  If (node.nodeParent == NIL) Then

    Tree.root = nodeTemp;

  Else

  Begin

    If (node == node.nodeParent.right) Then

     node.nodeParent.right = nodeTemp;

    Else

     node.nodeParent.left = nodeTemp;

  End

  nodeTemp.right = node;

  node.nodeParent = nodeTemp;

End

Добавление вершины в КЧД

Чтобы добавить вершину в КЧД, мы применяем процедуру TreeInsert для ДДП, красим вершину в красный цвет, а затем восстанавливаем свойства КЧД. Для этого мы перекрашиваем некоторые вершины и производим вращения.

1 RBTInsert(Tree,node)

 2 Begin

 3   TreeInsert(Tree,node);

 4   node.color = RED;

 5   While (node != Tree.root) and (node.nodeParent.color == RED) Do

 6   Begin

 7     If (node.nodeParent == node.nodeParent.nodeParent.left) Then

 8     Begin

 9       nodeTemp = node.nodeParent.nodeParent.right;

10       If (nodeTemp.color == RED) Then

11       Begin

12         node.nodeParent.color = BLACK;

13         nodeTemp.color = BLACK;

14         node.nodeParent.nodeParent.color = RED;

15         node = node.nodeParent.nodeParent;

16       End

17       Else

18       Begin

19         If (node == node.nodeParent.right) Then

20         Begin

21           node = node.nodeParent;

22           RBTLeftRorate(Tree,node);

23         End

24         node.nodeParent.color = BLACK;

25         node.nodeParent.nodeParent.color = RED;

26         RBTRightRotate(Tree,node.nodeParent.nodeParent);

27       End

28     End

29     Else

30     Begin

31       nodeTemp = node.nodeParent.nodeParent.left;

32       If (nodeTemp.color == RED) Then

33       Begin

34         node.nodeParent.color = BLACK;

35         nodeTemp.color = BLACK;

36         node.nodeParent.nodeParent.color = RED;

37         node = node.nodeParent.nodeParent;

38       End

39       Else

40       Begin

41         If (node == node.nodeParent.left) Then

42         Begin

43           node = node.nodeParent;

44           RBTRightRorate(Tree,node);

45         End

46         node.nodeParent.color = BLACK;

47         node.nodeParent.nodeParent.color = RED;

48         RBTLeftRotate(Tree,node.nodeParent.nodeParent);

49       End

50     End

51   End

52   Tree.root.color = BLACK;

53 End

Функция RBTInsert не так сложна, как кажется на первый взгляд. Рассмотрим её подробнее. После строк 3-4 выполняются все свойства КЧД, кроме, возможно, одного: у новой красной вершины может быть красный родитель. Такая ситуация (красная вершина имеет красного родителя) может сохраниться после любого числа итераций цикла. Внутри цикла рассматриваются 6 различных случаев, но три из них (строки 8-28) симметричны трём другим (строки 30-50), различие лишь в том, является ли родитель вершины node правым или левым потомком своего родителя (случаи разделяются в строке 7). Поэтому мы рассмотрим подробно только первые три случая (строки 8-28). Предположим, что во всех рассматриваемых КЧД корень чёрный, и будем поддерживать это свойство (строка 52). Поэтому в строке 5 node.nodeParent (красного цвета) не может быть корнем, и node.nodeParent.nodeParent != NIL. Операции внутри цикла начинаются с нахождения nodeTemp, “дяди” node, то есть вершины, имеющей того же родителя, что и node.nodeParent. Если nodeTemp – красная вершина, то имеет место случай 1, если черная, то 2 или 3. Во всех случаях вершина node.nodeParent.nodeParent – чёрная, так как пара node, node.nodeParent была единственным нарушением свойств КЧД.

Случай 1 (строки 12-15 и 34-37) показан на рисунке 6. Является ли вершина node правым или левым потомком своего родителя, значения не имеет.

Двоичные деревья поиска 

Рисунок 6.

Обе вершины (node и nodeTemp) – красные, а вершина node.nodeParent.nodeParent – чёрная. Перекрасим node.nodeParent и nodeTemp в чёрный цвет, а node.nodeParent.nodeParent – в красный. При этом число чёрных вершин на любом пути от корня к листьям остаётся прежним. Нарушение свойств КЧД возможно лишь в одном месте: вершина node.nodeParent.nodeParent может иметь красного родителя, поэтому надо продолжить выполнение цикла, присвоив node значение node.nodeParent.nodeParent.

В случаях 2 и 3 вершина nodeTemp – чёрная. Различаются случаи, когда вершина node является правым или левым потомком своего родителя. Если правым, то это случай 2 (строки 20-23 и 41-45). В этом случае производится левое вращение, которое сводит случай 2 к случаю 3, когда node является левым потомком своего родителя. Так как node и node.nodeParent – красные, после вращения количество чёрных вершин на путях от корня к листьям остается прежним.

Двоичные деревья поиска 

Рисунок 7.

Осталось рассмотреть случай 3: красная вершина node является левым потомком красной вершины node.nodeParent, которая, в свою очередь, является левым потомком node.nodeParent.nodeParent, правым потомком которой является nodeTemp. В этом случае достаточно произвести правое вращение и перекрасить две вершины. Цикл окончится, так как вершина node.nodeParent будет после этого чёрной.

Удаление вершины из КЧД

Удаление вершины немного сложнее добавления. Мы будем считать, что (NIL).color == BLACK, и будем считать операцию взятия цвета у указателя, равного NIL, допустимой операцией. Также мы будем считать допустимым присваивание (NIL).nodeParent, и будем считать данное присваивание имеющим результат. То есть при взятии значения (NIL).nodeParent мы получим ранее записанное значение. Функция RBTDelete подобна TreeDelete, но, удалив вершину, она вызывает процедуру RTBDeleteFixUp для восстановления свойств КЧД.

RBTDelete(Tree,node)

Begin

  If (node.left == NIL) or (node.right == NIL) Then

    nodeParent = node;

  Else

    nodeParent = TreeNext(node);

  If (nodeParent.left != NIL) Then

    nodeTemp = nodeParent.left;

  Else

    nodeTemp = nodeParent.right;

  nodeTemp.nodeParent = nodeParent.nodeParent;

  If (nodeTemp.nodeParent == NIL) Then

    Tree.root = nodeTemp;

  Else

  Begin

    If (nodeParent.nodeParent.left == nodeParent) Then

      nodeParent.nodeParent.left = nodeTemp;

    Else

      nodeParent.nodeParent.right = nodeTemp;

  End

  If (nodeParent != node) Then

  Begin

    node.key = nodeParent.key;

    node.color = nodeParent.color;

    { копирование дополнительных данных }

  End

  If (nodeParent.color == BLACK) Then

    RBTDeleteFixUp(Tree,nodeTemp);

  Return nodeParent;

End

Рассмотрим, как процедура RBTDeleteFixUp восстанавливает свойства КЧД. Очевидно, что если удалили красную вершину, то, поскольку оба ее потомка чёрные, красная вершина не станет родителем красного потомка. Если же удалили чёрную вершину, то как минимум на одном из путей от корня к листьям количество чёрных вершин уменьшилось. К тому же красная вершина могла стать потомком красного родителя.

1 RTBDeleteFixUp(Tree,node)

 2 Begin

 3   While (node != Tree.root) and (node.color == BLACK) Do

 4   Begin

 5     If (node == node.nodeParent.left)

 6     Begin

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: