Рубрики

Красно-Черное Дерево | Набор 3 (Удалить)

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

Красно-Черное Дерево Введение
Красная вставка черного дерева

Вставка против удаления:
Как и вставка, изменение цвета и вращение используются для сохранения красно-черных свойств.

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

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

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

Шаги удаления
Ниже приведены подробные инструкции по удалению.

1) Выполните стандартное удаление BST . Когда мы выполняем стандартную операцию удаления в BST, мы всегда заканчиваем тем, что удаляем узел, который является либо листовым, либо имеет только один дочерний элемент (для внутреннего узла мы копируем преемник, а затем рекурсивно вызываем delete для преемника, преемник всегда является листовым узлом или узел с одним ребенком). Таким образом, нам нужно обрабатывать только случаи, когда узел является листовым или имеет одного потомка. Пусть v будет удаляемым узлом, а u будет дочерним, который заменяет v (Обратите внимание, что u равно NULL, когда v является листом, а цвет NULL считается черным).

2) Простой случай: если либо u, либо v красный, мы помечаем замененный дочерний элемент как черный (без изменения высоты черного). Обратите внимание, что и u, и v не могут быть красного цвета, так как v является родительским для u, и два последовательных красных не допускаются в красно-черном дереве.

3) Если и u, и v черные .

3.1) Цвет U как двойной черный. Теперь наша задача сводится к тому, чтобы преобразовать этот двойной черный в один черный. Обратите внимание, что если v является листом, то u равно NULL и цвет NULL считается черным. Таким образом, удаление черного листа также вызывает двойной черный.

3.2) Выполните следующие действия, пока текущий узел u имеет двойной черный цвет и он не является корневым. Пусть родной брат узла будет s .
…. (a): Если родной брат s черный, и хотя бы один из его детей — красный , выполните ротацию (и). Пусть красное дитя s будет r . Этот случай может быть разделен на четыре случая в зависимости от положений s и r.

………… .. (i) Левый левый регистр (s — левый дочерний элемент своего родителя, а r — левый дочерний элемент s или оба дочерних элемента s красного цвета). Это зеркало правого и правого случая показано на диаграмме ниже.

………… .. (ii) Левый правый регистр (s — левый потомок своего родителя, а r — правый потомок). Это зеркало правого левого регистра показано на диаграмме ниже.

………………………………………………………………………………………………………………………………………………………………………………………………………………… (iii). Правильный правый случай (s — правильный ребенок от своего родителя, а r — правильный ребенок от s, или оба ребенка s красного цвета)

………… .. (iv) Правый левый регистр (s — правый потомок своего родителя, а r — левый потомок s)

… .. (b): Если родной брат черный, а оба его потомка черные , выполните перекрашивание и повторите для родителя, если родитель черный.

В этом случае, если родитель был красным, то нам не нужно было повторяться для prent, мы можем просто сделать его черным (красный + двойной черный = один черный)

… .. (c): если брат красного цвета , выполните вращение, чтобы переместить старого брата вверх, перекрасить старого брата и родителя. Новый брат всегда черный (см. Диаграмму ниже). Это в основном преобразует дерево в случай черного брата (по очереди) и приводит к случаю (а) или (б). Этот случай может быть разделен на два случая.
………… .. (i) Левый регистр (s — левый потомок своего родителя). Это зеркало правого и правого случая показано на диаграмме ниже. Вращаем вправо родительский р.
………… .. (iii) Правильный случай (s является правым потомком своего родителя). Мы оставили повернуть родительский р.

3.3) Если u — корень, сделайте его черным и верните его (высота черного дерева в целом уменьшается на 1).

ниже реализация C ++ вышеупомянутого подхода:

#include <iostream>
#include <queue>

using namespace std;

  

enum COLOR { RED, BLACK };

  

class Node {

public:

  int val;

  COLOR color;

  Node *left, *right, *parent;

  

  Node(int val) : val(val) {

    parent = left = right = NULL;

  

    // Узел создается во время вставки

    // Узел красный при вставке

    color = RED;

  }

  

  // возвращает указатель на дядю

  Node *uncle() {

    // Если нет родителя или дедушки, то нет дяди

    if (parent == NULL or parent->parent == NULL)

      return NULL;

  

    if (parent->isOnLeft())

      // дядя справа

      return parent->parent->right;

    else

      // дядя слева

      return parent->parent->left;

  }

  

  // проверяем, остался ли узел дочерним от родителя

  bool isOnLeft() { return this == parent->left; }

  

  // возвращает указатель на брата

  Node *sibling() {

    // родной нуль, если нет родителя

    if (parent == NULL)

      return NULL;

  

    if (isOnLeft())

      return parent->right;

  

    return parent->left;

  }

  

  // перемещаем узел вниз и перемещаем данный узел на его место

  void moveDown(Node *nParent) {

    if (parent != NULL) {

      if (isOnLeft()) {

        parent->left = nParent;

      } else {

        parent->right = nParent;

      }

    }

    nParent->parent = parent;

    parent = nParent;

  }

  

  bool hasRedChild() {

    return (left != NULL and left->color == RED) or

           (right != NULL and right->color == RED);

  }

};

  

class RBTree {

  Node *root;

  

  // влево поворачивает данный узел

  void leftRotate(Node *x) {

    // новый родитель будет правым потомком узла

    Node *nParent = x->right;

  

    // обновляем корень, если текущий узел является корнем

    if (x == root)

      root = nParent;

  

    x->moveDown(nParent);

  

    // соединяем x с левым элементом нового родителя

    x->right = nParent->left;

    // соединяем левый элемент нового родителя с узлом

    // если не ноль

    if (nParent->left != NULL)

      nParent->left->parent = x;

  

    // соединяем нового родителя с x

    nParent->left = x;

  }

  

  void rightRotate(Node *x) {

    // новый родитель будет левым потомком узла

    Node *nParent = x->left;

  

    // обновляем корень, если текущий узел является корнем

    if (x == root)

      root = nParent;

  

    x->moveDown(nParent);

  

    // соединяем x с правым элементом нового родителя

    x->left = nParent->right;

    // соединяем правый элемент нового родителя с узлом

    // если не ноль

    if (nParent->right != NULL)

      nParent->right->parent = x;

  

    // соединяем нового родителя с x

    nParent->right = x;

  }

  

  void swapColors(Node *x1, Node *x2) {

    COLOR temp;

    temp = x1->color;

    x1->color = x2->color;

    x2->color = temp;

  }

  

  void swapValues(Node *u, Node *v) {

    int temp;

    temp = u->val;

    u->val = v->val;

    v->val = temp;

  }

  

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

  void fixRedRed(Node *x) {

    // если x является корневым цветом, он черный и возвращает

    if (x == root) {

      x->color = BLACK;

      return;

    }

  

    // инициализируем родителя, дедушку, дедушку

    Node *parent = x->parent, *grandparent = parent->parent,

         *uncle = x->uncle();

  

    if (parent->color != BLACK) {

      if (uncle != NULL && uncle->color == RED) {

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

        parent->color = BLACK;

        uncle->color = BLACK;

        grandparent->color = RED;

        fixRedRed(grandparent);

      } else {

        // Остальное выполнить LR, LL, RL, RR

        if (parent->isOnLeft()) {

          if (x->isOnLeft()) {

            // для левого и правого

            swapColors(parent, grandparent);

          } else {

            leftRotate(parent);

            swapColors(x, grandparent);

          }

          // для левого левого и левого правого

          rightRotate(grandparent);

        } else {

          if (x->isOnLeft()) {

            // для правого левого

            rightRotate(parent);

            swapColors(x, grandparent);

          } else {

            swapColors(parent, grandparent);

          }

  

          // для правого, правого и правого левого

          leftRotate(grandparent);

        }

      }

    }

  }

  

  // найти узел, у которого нет левого потомка

  // в поддереве данного узла

  Node *successor(Node *x) {

    Node *temp = x;

  

    while (temp->left != NULL)

      temp = temp->left;

  

    return temp;

  }

  

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

  Node *BSTreplace(Node *x) {

    // когда у узла 2 ребенка

    if (x->left != NULL and x->right != NULL)

      return successor(x->right);

  

    // когда лист

    if (x->left == NULL and x->right == NULL)

      return NULL;

  

    // когда одинокий ребенок

    if (x->left != NULL)

      return x->left;

    else

      return x->right;

  }

  

  // удаляет указанный узел

  void deleteNode(Node *v) {

    Node *u = BSTreplace(v);

  

    // True, когда u и v оба черные

    bool uvBlack = ((u == NULL or u->color == BLACK) and (v->color == BLACK));

    Node *parent = v->parent;

  

    if (u == NULL) {

      // U - NULL, поэтому v - лист

      if (v == root) {

        // v - root, делая root пустым

        root = NULL;

      } else {

        if (uvBlack) {

          // вы и v оба черные

          // v - лист, исправить двойное черное на v

          fixDoubleBlack(v);

        } else {

          // U или V красный

          if (v->sibling() != NULL)

            // брат не нулевой, сделай его красным

            v->sibling()->color = RED;

        }

  

        // удаляем v из дерева

        if (v->isOnLeft()) {

          parent->left = NULL;

        } else {

          parent->right = NULL;

        }

      }

      delete v;

      return;

    }

  

    if (v->left == NULL or v->right == NULL) {

      // у v есть 1 ребенок

      if (v == root) {

        // v - root, присваиваем значение u v и удаляем u

        v->val = u->val;

        v->left = v->right = NULL;

        delete u;

      } else {

        // Отсоединяем v от дерева и поднимаем

        if (v->isOnLeft()) {

          parent->left = u;

        } else {

          parent->right = u;

        }

        delete v;

        u->parent = parent;

        if (uvBlack) {

          // вы и v оба черные, исправьте двойной черный у вас

          fixDoubleBlack(u);

        } else {

          // красный или красный, черный цвет

          u->color = BLACK;

        }

      }

      return;

    }

  

    // у v есть 2 потомка, поменяйте местами значения с преемником и recurse

    swapValues(u, v);

    deleteNode(u);

  }

  

  void fixDoubleBlack(Node *x) {

    if (x == root)

      // Достигнут корень

      return;

  

    Node *sibling = x->sibling(), *parent = x->parent;

    if (sibling == NULL) {

      // Никакого родства, двойной черный оттолкнут

      fixDoubleBlack(parent);

    } else {

      if (sibling->color == RED) {

        // родной красный

        parent->color = RED;

        sibling->color = BLACK;

        if (sibling->isOnLeft()) {

          // левый регистр

          rightRotate(parent);

        } else {

          // правильный случай

          leftRotate(parent);

        }

        fixDoubleBlack(x);

      } else {

        // брат черный

        if (sibling->hasRedChild()) {

          // хотя бы 1 красный ребенок

          if (sibling->left != NULL and sibling->left->color == RED) {

            if (sibling->isOnLeft()) {

              // слева налево

              sibling->left->color = sibling->color;

              sibling->color = parent->color;

              rightRotate(parent);

            } else {

              // правый левый

              sibling->left->color = parent->color;

              rightRotate(sibling);

              leftRotate(parent);

            }

          } else {

            if (sibling->isOnLeft()) {

              // лево право

              sibling->right->color = parent->color;

              leftRotate(sibling);

              rightRotate(parent);

            } else {

              // верно-верно

              sibling->right->color = sibling->color;

              sibling->color = parent->color;

              leftRotate(parent);

            }

          }

          parent->color = BLACK;

        } else {

          // 2 черных ребенка

          sibling->color = RED;

          if (parent->color == BLACK)

            fixDoubleBlack(parent);

          else

            parent->color = BLACK;

        }

      }

    }

  }

  

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

  void levelOrder(Node *x) {

    if (x == NULL)

      // возвращаем, если узел нулевой

      return;

  

    // очередь за уровнем порядка

    queue<Node *> q;

    Node *curr;

  

    // нажать х

    q.push(x);

  

    while (!q.empty()) {

      // пока q не пусто

      // удаление очереди

      curr = q.front();

      q.pop();

  

      // выводим значение узла

      cout << curr->val << " ";

  

      // толкаем детей в очередь

      if (curr->left != NULL)

        q.push(curr->left);

      if (curr->right != NULL)

        q.push(curr->right);

    }

  }

  

  // рекурсивно печатает

  void inorder(Node *x) {

    if (x == NULL)

      return;

    inorder(x->left);

    cout << x->val << " ";

    inorder(x->right);

  }

  

public:

  // конструктор

  // инициализируем root

  RBTree() { root = NULL; }

  

  Node *getRoot() { return root; }

  

  // ищет заданное значение

  // если найден, возвращает узел (используется для удаления)

  // else возвращает последний узел при обходе (используется при вставке)

  Node *search(int n) {

    Node *temp = root;

    while (temp != NULL) {

      if (n < temp->val) {

        if (temp->left == NULL)

          break;

        else

          temp = temp->left;

      } else if (n == temp->val) {

        break;

      } else {

        if (temp->right == NULL)

          break;

        else

          temp = temp->right;

      }

    }

  

    return temp;

  }

  

  // вставляет данное значение в дерево

  void insert(int n) {

    Node *newNode = new Node(n);

    if (root == NULL) {

      // когда root равен null

      // просто вставляем значение в корень

      newNode->color = BLACK;

      root = newNode;

    } else {

      Node *temp = search(n);

  

      if (temp->val == n) {

        // возвращаем, если значение уже существует

        return;

      }

  

      // если значение не найдено, поиск возвращает узел

      // где значение должно быть вставлено

  

      // подключаем новый узел к правильному узлу

      newNode->parent = temp;

  

      if (n < temp->val)

        temp->left = newNode;

      else

        temp->right = newNode;

  

      // исправить красный красный voilaton, если существует

      fixRedRed(newNode);

    }

  }

  

  // служебная функция, которая удаляет узел с заданным значением

  void deleteByVal(int n) {

    if (root == NULL)

      // Дерево пусто

      return;

  

    Node *v = search(n), *u;

  

    if (v->val != n) {

      cout << "No node found to delete with value:" << n << endl;

      return;

    }

  

    deleteNode(v);

  }

  

  // выводит порядок дерева

  void printInOrder() {

    cout << "Inorder: " << endl;

    if (root == NULL)

      cout << "Tree is empty" << endl;

    else

      inorder(root);

    cout << endl;

  }

  

  // выводит порядок уровня дерева

  void printLevelOrder() {

    cout << "Level order: " << endl;

    if (root == NULL)

      cout << "Tree is empty" << endl;

    else

      levelOrder(root);

    cout << endl;

  }

};

  

int main() {

  RBTree tree;

  

  tree.insert(7);

  tree.insert(3);

  tree.insert(18);

  tree.insert(10);

  tree.insert(22);

  tree.insert(8);

  tree.insert(11);

  tree.insert(26);

  tree.insert(2);

  tree.insert(6);

  tree.insert(13);

  

  tree.printInOrder();

  tree.printLevelOrder();

  

  cout<<endl<<"Deleting 18, 11, 3, 10, 22"<<endl;

  

  tree.deleteByVal(18);

  tree.deleteByVal(11);

  tree.deleteByVal(3);

  tree.deleteByVal(10);

  tree.deleteByVal(22);

  

  tree.printInOrder();

  tree.printLevelOrder();

  return 0;

}

Выход:

Inorder: 
2 3 6 7 8 10 11 13 18 22 26 
Level order: 
10 7 18 3 8 11 22 2 6 13 26 

Deleting 18, 11, 3, 10, 22
Inorder: 
2 6 7 8 13 26 
Level order: 
13 7 26 6 8 2 

Ссылки:
https://www.cs.purdue.edu/homes/ayg/CS251/slides/chap13c.pdf
Введение в алгоритмы 3-е издание Клиффорд Стейн, Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Красно-Черное Дерево | Набор 3 (Удалить)

0.00 (0%) 0 votes