logo

TechCodeview

Знайомство з червоно-чорним деревом

Двійкові дерева пошуку є фундаментальними структура даних, але їх продуктивність може погіршитися, якщо дерево стає незбалансованим. Червоні чорні дерева є типом збалансоване бінарне дерево пошуку які використовують набір правил для підтримки балансу, забезпечуючи логарифмічну складність часу для таких операцій, як вставлення, видалення та пошук , незалежно від початкової форми дерева. Червоні чорні дерева самобалансуються, використовуючи просту схему кольорового кодування для коригування дерева після кожної модифікації.

Червоно-чорне дерево



Зміст

Що таке червоно-чорне дерево?

А Червоно-чорне дерево є самобалансуванням двійкове дерево пошуку де кожен вузол має додатковий атрибут: колір, який може бути будь-яким червоний або чорний . Основна мета цих дерев — підтримувати баланс під час вставок і видалень, забезпечуючи ефективний пошук даних і маніпуляції.

Властивості червоно-чорних дерев

А Червоно-чорне дерево мають такі властивості:



тверда обкладинка проти м’якої обкладинки
  1. Колір вузла : кожен вузол або червоний, або чорний .
  2. Коренева властивість : Корінь дерева завжди чорний .
  3. Червона власність : червоні вузли не можуть мати червоних дочірніх вузлів (жоден шлях не має двох послідовних червоних вузлів).
  4. Чорна власність : Кожен шлях від вузла до його нащадкових нульових вузлів (листів) має однакову кількість чорний вузлів.
  5. Властивість листа : Усі листи (вузли NIL) є чорний .

Ці властивості гарантують, що найдовший шлях від кореня до будь-якого листка не більш ніж удвічі довший за найкоротший шлях, зберігаючи баланс дерева та ефективну продуктивність.

Приклад червоно-чорного дерева

ціле число Java

The Правильне червоно-чорне дерево на зображенні вище гарантує, що кожен шлях від кореневого вузла до кінцевого вузла має однакову кількість чорних вузлів. У цьому випадку є один (за винятком кореневого вузла).



The Неправильне червоне чорне дерево не дотримується червоно-чорних властивостей, як два червоних вузла прилягають один до одного. Інша проблема полягає в тому, що один із шляхів до кінцевого вузла не має нульових чорних вузлів, тоді як два інших містять чорний вузол.

Чому червоно-чорні дерева?

Більшість операцій BST (наприклад, пошук, макс., мінім., вставка, видалення... тощо) займають O(h) час, де h — висота BST . Вартість цих операцій може стати O(n) для перекошеного Бінарне дерево. Якщо ми переконаємося, що висота дерева залишається O(log n) після кожної вставки та видалення ми можемо гарантувати верхню межу O(log n) для всіх цих операцій. Висота червоно-чорного дерева завжди O(log n) де n – кількість вузлів у дереві.

пан ніАлгоритмЧасова складність
1.ПошукO(log n)
2.ВставкаO(log n)
3.ВидалитиO(log n)

Порівняння з Дерево AVL :

Дерева AVL більш збалансовані порівняно з червоно-чорними деревами, але вони можуть спричиняти більше обертань під час вставки та видалення. Отже, якщо ваша програма включає часті вставки та видалення, то слід віддати перевагу червоно-чорним деревам. І якщо вставки та видалення відбуваються рідше, а пошук є більш частою операцією, то Дерево AVL слід віддавати перевагу над червоно-чорним деревом.

Як червоно-чорне дерево забезпечує баланс?

Простий приклад для розуміння балансування полягає в тому, що ланцюжок із 3 вузлів неможливий у червоно-чорному дереві. Ми можемо спробувати будь-яку комбінацію кольорів і перевірити, чи всі вони порушують властивість червоно-чорного дерева.

Правильна структура червоно-чорного дерева з трьома вузлами

Цікаві факти про Червоно-чорне дерево:

  • The чорний Висота червоно-чорного дерева — це кількість чорних вузлів на шляху від кореневого вузла до листового вузла. Листові вузли також зараховуються чорний вузлів. Отже, червоно-чорне дерево висоти ч має висота чорного>= h/2 .
  • Висота червоно-чорного дерева с п вузлів є h<= 2 журнал 2 (n + 1) .
  • Усі листи (НІЛ) є чорний .
  • The чорний глибина вузла визначається як кількість чорних вузлів від кореня до цього вузла, тобто кількість чорних предків.

Основні операції з червоно-чорним деревом:

Основні операції з червоно-чорним деревом включають:

тернарний оператор java
  1. Вставка
  2. Пошук
  3. Видалення
  4. Обертання

1. Вставка

Вставлення нового вузла в червоно-чорне дерево передбачає двоетапний процес: виконання стандартного вставка бінарного дерева пошуку (BST). , з наступним усуненням будь-яких порушень властивостей Red-Black.

Етапи вставки

  1. Вставка BST : Вставте новий вузол, як у стандартний BST.
  2. Виправити порушення :
    • Якщо батьком нового вузла є чорний , жодні властивості не порушуються.
    • Якщо батько є червоний , дерево може порушувати Red Property, що вимагає виправлень.

Усунення порушень під час вставки

Після вставки нового вузла як a червоний вузол, ми можемо зіткнутися з кількома випадками залежно від кольорів батьківського вузла та дядька (брата батьківського вузла):

  • Випадок 1: дядько Рудий : Перефарбуйте батька та дядька чорний , а дідусь і бабуся до червоний . Потім перемістіться вгору по дереву, щоб перевірити наявність подальших порушень.
  • Випадок 2: дядько чорний :
    • Підвипадок 2.1: Node є правим дочірнім елементом : Виконайте поворот ліворуч на батьківському.
    • Підвипадок 2.2: вузол є лівим дочірнім елементом : Виконайте поворот праворуч на бабусі та дідусі та перефарбуйте належним чином.

2. Пошук

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

Етапи пошуку

  1. Почніть із кореня : Почніть пошук із кореневого вузла.
  2. Обійти дерево :
    • Якщо цільове значення дорівнює значенню поточного вузла, вузол знайдено.
    • Якщо цільове значення менше значення поточного вузла, перейдіть до лівого дочірнього вузла.
    • Якщо цільове значення більше, ніж значення поточного вузла, перейдіть до правого дочірнього елемента.
  3. Повторіть : Продовжуйте цей процес, доки не буде знайдено цільове значення або не досягнуто вузла NIL (вказує, що значення немає в дереві).

3. Видалення

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

Етапи видалення

  1. Видалення BST : видаліть вузол за допомогою стандартних правил BST.
  2. Fix Double Black :
    • Якщо чорний вузол буде видалено, може виникнути подвійний чорний стан, який потребує спеціальних виправлень.

Усунення порушень під час видалення

Коли чорний вузол видаляється, ми вирішуємо проблему подвійного чорного на основі кольору рідного вузла та кольорів його дочірніх елементів:

  • Випадок 1: рідний брат червоний : Обертання батьківського елемента та перефарбування рідного і батьківського елементів.
  • Випадок 2: брат чи сестра чорношкірий :
    • Підвипадок 2.1: Діти брата чи сестри чорношкірі : перефарбуйте брата та поширте подвійний чорний вгору.
    • Підвипадок 2.2: принаймні один із дітей брата чи сестри червоний :
      • Якщо дальня дитина брата або сестри червона : Виконайте обертання на батьківському та братському елементі та перефарбуйте належним чином.
      • Якщо дитина рідного брата або сестри червона : Поверніть рідного брата та його дочірнього елемента, а потім обробіть, як описано вище.

4. Обертання

Обертання є основними операціями для підтримки збалансованої структури червоно-чорного дерева (RBT). Вони допомагають зберегти властивості дерева, гарантуючи, що найдовший шлях від кореня до будь-якого листа не більше ніж вдвічі перевищує довжину найкоротшого шляху. Ротації бувають двох видів: ліві повороти і праві повороти.

1. Обертання вліво

Обертання вліво у вузлі 𝑥 x рухається 𝑥 x вниз ліворуч і праворуч дочірнє 𝑦 і до прийняти 𝑥 x місце.

Візуалізація лівого повороту 
Before Rotation:  x      y   /    a b  After Left Rotation:  y  /   x b  /  a>

Кроки повороту вліво:

  1. встановити і бути правильною дитиною x .
  2. рухатися і ліве піддерево до x праве піддерево.
  3. Оновити батьківський елемент x і і .
  4. оновлення x батько, на якого потрібно вказати і замість x .
  5. встановити і залишив дитину x .
  6. оновлення x батькові і .

Псевдокод повороту вліво:

Обертання вліво 
// Utility function to perform left rotation void leftRotate(Node* x) {  Node* y = x->справа;  x->праворуч = y->ліворуч;  if (y->left != NIL) { y->left->parent = x;  } y->parent = x->parent;  if (x->parent == nullptr) { root = y;  } else if (x == x->parent->left) { x->parent->left = y;  } else { x->parent->right = y;  } y->left = x;  x->батьківський = y; }>

2. Обертання вправо

Правий поворот у вузлі 𝑥 x рухається 𝑥 x вниз праворуч і його лівий дочірній елемент 𝑦 і до прийняти 𝑥 x місце.

bash else if
Візуалізація повороту вправо: 
Befor Right Rotation:   x  /  y  /   a b After Right Rotation:  y  /   a x  /  b>

Кроки обертання вправо:

  1. встановити і бути лівою дитиною x .
  2. рухатися і є правильне піддерево до x ліве піддерево.
  3. Оновити батьківський елемент x і і .
  4. оновлення x батько, на якого потрібно вказати і замість x .
  5. встановити і має право дитини x .
  6. оновлення x батько до і .

Псевдокод обертання вправо:

C++ 
// Utility function to perform right rotation void rightRotate(Node* x) {  Node* y = x->зліва;  x->ліворуч = y->праворуч;  if (y->right != NIL) { y->right->parent = x;  } y->parent = x->parent;  if (x->parent == nullptr) { root = y;  } else if (x == x->parent->right) { x->parent->right = y;  } else { x->parent->left = y;  } y->праворуч = x;  x->батьківський = y; }>

Коли виконувати обертання?

Обертання в червоно-чорних деревах зазвичай виконуються під час вставок і видалень, щоб зберегти властивості дерева. Нижче наведено сценарії ротацій:

1. Усунення порушень після вставки

Коли вставляється новий вузол, він завжди забарвлюється в червоний колір. Це може спричинити порушення властивостей Red-Black Tree, зокрема:

  • Корінь повинен бути чорний .
  • Червоний вузли не можуть мати червоний дітей.

Аналіз випадків для виправлення вставок:

  • Випадок 1: перефарбування та поширення вгору
    • Якщо і батько, і дядько нового вузла є обома червоний , перефарбувати батьків і дядька до чорний , а дідусь і бабуся до червоний . Потім рекурсивно застосуйте виправлення до бабусі та дідуся.
  • Випадок 2: обертання та перефарбування
    • Якщо дядько нового вузла є чорний і новий вузол є правим дочірнім елементом лівого дочірнього елемента (або навпаки), виконайте обертання, щоб перемістити новий вузол угору та вирівняти його.
    • Якщо дядько нового вузла є чорний і новий вузол є лівим дочірнім елементом лівого дочірнього елемента (або правим від правого), виконайте обертання та змініть колір батьківського та дідуся, щоб виправити порушення.

2. Виправлення порушень після видалення

Після видалення дерево може потребувати виправлення, щоб відновити властивості:

  • Коли чорний вузол видаляється або червоний вузол замінюється чорним вузлом, може виникнути подвійна чорна ситуація.

Аналіз випадків для виправлення видалень:

динамічний масив у java
  • Випадок 1: рідний брат червоний
    • Знову розфарбуйте рідного і батьківського елементів і виконайте обертання.
  • Випадок 2: Чорний брат і сестра з темношкірими дітьми
    • Змініть колір брата на червоний і перенесіть проблему до батьківського.
  • Випадок 3: брат чи сестра є темношкірими і мають принаймні одну руду дитину
    • Поверніть і змініть колір, щоб вирішити проблему з подвійним чорним.

Реалізація Red-Black Tree:

Ось детальна реалізація червоно-чорного дерева, включаючи функції вставки, пошуку та обертання:

C++ 
#include  using namespace std; // Node structure for the Red-Black Tree struct Node {  int data;  string color;  Node *left, *right, *parent;  Node(int data)  : data(data)  , color('RED')  , left(nullptr)  , right(nullptr)  , parent(nullptr)  {  } }; // Red-Black Tree class class RedBlackTree { private:  Node* root;  Node* NIL;  // Utility function to perform left rotation  void leftRotate(Node* x)  {  Node* y = x->справа;  x->праворуч = y->ліворуч;  if (y->left != NIL) { y->left->parent = x;  } y->parent = x->parent;  if (x->parent == nullptr) { root = y;  } else if (x == x->parent->left) { x->parent->left = y;  } else { x->parent->right = y;  } y->left = x;  x->батьківський = y;  } // Допоміжна функція для виконання повороту вправо void rightRotate(Node* x) { Node* y = x->left;  x->ліворуч = y->праворуч;  if (y->right != NIL) { y->right->parent = x;  } y->parent = x->parent;  if (x->parent == nullptr) { root = y;  } else if (x == x->parent->right) { x->parent->right = y;  } else { x->parent->left = y;  } y->праворуч = x;  x->батьківський = y;  } // Функція для виправлення властивостей червоно-чорного дерева після // вставки void fixInsert(Node* k) { while (k != root && k->parent->color == 'RED') { if (k->parent == k->parent->parent->left) { Node* u = k->parent->parent->right; // дядько if (u->color == 'RED') { k->parent->color = 'BLACK';  u->колір = 'ЧОРНИЙ';  k->parent->parent->color = 'RED';  k = k->батько->батько;  } else { if (k == k->parent->right) { k = k->parent;  Повернути вліво(k);  } k->parent->color = 'ЧОРНИЙ';  k->parent->parent->color = 'RED';  rightRotate(k->parent->parent);  } } else { Node* u = k->parent->parent->left; // дядько if (u->color == 'RED') { k->parent->color = 'BLACK';  u->колір = 'ЧОРНИЙ';  k->parent->parent->color = 'RED';  k = k->батько->батько;  } else { if (k == k->parent->left) { k = k->parent;  праворуч(k);  } k->parent->color = 'ЧОРНИЙ';  k->parent->parent->color = 'RED';  leftRotate(k->parent->parent);  } } } root->color = 'ЧОРНИЙ';  } // Допоміжна функція обходу порядку void inorderHelper(Node* node) { if (node ​​!= NIL) { inorderHelper(node->left);  cout<< node->даних<< ' ';  inorderHelper(node->праворуч);  } } // Допоміжна функція пошуку Node* searchHelper(Node* node, int data) { if (node ​​== NIL || data == node->data) { return node;  } якщо (дані< node->дані) { return searchHelper(node->left, data);  } return searchHelper(node->right, data);  } public: // Конструктор RedBlackTree() { NIL = new Node(0);  NIL->колір = 'ЧОРНИЙ';  NIL->left = NIL->right = NIL;  корінь = NIL;  } // Вставити функцію void insert(int data) { Node* new_node = new Node(data);  new_node->left = NIL;  new_node->right = NIL;  Node* parent = nullptr;  Вузол* поточний = корінь;  // Вставка BST while (current != NIL) { parent = current;  якщо (новий_вузол->дані< current->дані) { current = current->left;  } else { current = current->right;  } } new_node->parent = parent;  if (parent == nullptr) { root = new_node;  } else if (новий_вузол->дані< parent->дані) { parent->left = new_node;  } else { parent->right = new_node;  } if (new_node->parent == nullptr) { new_node->color = 'BLACK';  повернення;  } if (new_node->parent->parent == nullptr) { return;  } fixInsert(новий_вузол);  } // Обхід порядку void inorder() { inorderHelper(root); } // Функція пошуку Node* search(int data) { return searchHelper(root, data);  } }; int main() { RedBlackTree rbt;  // Вставка елементів rbt.insert(10);  rbt.insert(20);  rbt.insert(30);  rbt.insert(15);  // Inorder traversal cout<< 'Inorder traversal:' << endl;  rbt.inorder(); // Output: 10 15 20 30  // Search for a node  cout << '
Search for 15: '  << (rbt.search(15) != rbt.search(0))  << endl; // Output: 1 (true)  cout << 'Search for 25: '  << (rbt.search(25) != rbt.search(0))  << endl; // Output: 0 (false)  return 0; }>

Переваги червоно-чорних дерев:

  • Збалансований: Червоно-чорні дерева самобалансуються, тобто вони автоматично підтримують баланс між висотою лівого та правого піддерев. Це гарантує, що в найгіршому випадку операції пошуку, вставки та видалення займають O(log n).
  • Ефективний пошук, вставка та видалення: Завдяки своїй збалансованій структурі червоно-чорні дерева забезпечують ефективну роботу. У гіршому випадку пошук, вставка та видалення займають O(log n) часу.
  • Простий у виконанні: Правила підтримки властивостей Red-Black Tree відносно прості та зрозумілі для реалізації.
  • Широко використовуваний: Червоно-чорні дерева є популярним вибором для реалізації різних структур даних, таких як карти, набори та черги пріоритетів.

Недоліки червоно-чорних дерев:

  • Більш складний, ніж інші збалансовані дерева: Порівняно з більш простими збалансованими деревами, такими як дерева AVL, червоно-чорні дерева мають складніші правила вставки та видалення.
  • Постійні накладні витрати: Підтримка властивостей Red-Black Tree додає невеликі накладні витрати на кожну операцію вставки та видалення.
  • Не оптимальний для всіх випадків використання: Незважаючи на ефективність для більшості операцій, червоно-чорні дерева можуть бути не найкращим вибором для програм, де потрібні часті вставки та видалення, оскільки постійні накладні витрати можуть стати значними.

Застосування червоно-чорних дерев:

  • Реалізація карт і наборів: Червоно-чорні дерева часто використовуються для реалізації карт і наборів, де ефективний пошук, вставка та видалення є вирішальними.
  • Пріоритетні черги: Червоно-чорні дерева можна використовувати для реалізації пріоритетних черг, де елементи впорядковуються на основі їх пріоритету.
  • Файлові системи: Червоно-чорні дерева використовуються в деяких файлових системах для керування структурами файлів і каталогів.
  • Бази даних в пам'яті: Червоно-чорні дерева іноді використовуються в базах даних у пам’яті для ефективного зберігання та отримання даних.
  • Розробка графіки та ігор: Червоно-чорні дерева можна використовувати в графіці та іграх розвитку для таких завдань, як виявлення зіткнень і пошук шляху.

Часті запитання (FAQ) про Red-Black Tree:

1. Що таке червоно-чорне дерево?

Червоно-чорне дерево — це самобалансуюче бінарне дерево пошуку, яке підтримує баланс між висотами лівого та правого піддерев. Це гарантує, що в найгіршому випадку операції пошуку, вставки та видалення займають O(log n). Червоно-чорні дерева широко використовуються в різних програмах, де потрібні ефективні структури даних.

2. Як червоно-чорне дерево підтримує рівновагу?

Червоно-чорні дерева зберігають свій баланс, дотримуючись певних правил щодо кольорів вузлів (ЧЕРВОНОГО або ЧОРНОГО) і зв’язків між ними. Ці правила гарантують, що дерево залишається збалансованим і що різниця у висоті між лівим і правим піддеревами становить не більше 1.

3. Які переваги використання червоно-чорного дерева?

  • Збалансований: Червоно-чорні дерева самобалансуються, забезпечуючи ефективні операції пошуку, вставки та видалення.
  • Ефективний: Вони пропонують O(log n) часову складність для більшості операцій.
  • Простий у виконанні: Правила збереження властивостей Red-Black Tree відносно прості.
  • Широко використовуваний: Вони є популярним вибором для реалізації різних структур даних і алгоритмів.

4. Які недоліки використання червоно-чорного дерева?

  • Порівняно з більш простими збалансованими деревами, такими як дерева AVL, червоно-чорні дерева мають складніші правила вставки та видалення.
  • Підтримка властивостей Red-Black Tree додає невеликі накладні витрати на кожну операцію вставки та видалення.
  • Для програм із частими вставками та видаленнями інші збалансовані деревоподібні структури можуть бути більш придатними.

5. У чому поширене застосування червоно-чорних дерев?

  • Реалізація карт і наборів
  • Пріоритетні черги
  • Файлові системи
  • Бази даних в пам'яті
  • Розробка графіки та ігор (виявлення зіткнень, пошук шляху)
  • Визначення та значення червоно-чорного дерева в DSA
  • Самобалансуючі бінарні дерева пошуку
  • Червоне чорне дерево проти дерева AVL
  • Яка різниця між Heap і Red-Black Tree?
  • Вставка в червоно-чорне дерево
  • Видалення в Red-Black Tree
  • Червоно-чорні дерева | Вставка зверху вниз