Программа C для вставки красного черного дерева

01.01.2020Бинарное дерево поиска

Следующая статья является продолжением статьи, обсуждаемой здесь .

При вставке дерева AVL мы использовали вращение как инструмент для балансировки после того, как вставка вызвала дисбаланс. В красно-черном дереве мы используем два инструмента для балансировки.

1) Перекраска
2) Вращение

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

Цвет узла NULL считается ЧЕРНЫМ.

Позвольте x быть недавно вставленным узлом.
1) Выполните стандартную вставку BST и сделайте цвет вновь вставленных узлов красным.

2) Если x — корень, измените цвет x на ЧЕРНЫЙ (высота черного дерева целиком увеличивается на 1).

3) Выполните следующие действия, если цвет родительского элемента x не ЧЕРНЫЙ или x не является корневым.
…. а) Если дядя х красный ( красный родитель должен быть черным из свойства 4 )
……. (I) Измените цвет родителя и дяди на ЧЕРНЫЙ.
…… .. (ii) цвет прародителя как красный.
…… .. (iii) Измените прародителя x = x, повторите шаги 2 и 3 для нового x.

…. б) Если дядя х черный , то может быть четыре конфигурации для х, родителя х ( р ) и прародителя х ( г ) (это похоже на дерево AVL )
…… .. i) Левый левый регистр (p — левый потомок g, а x — левый потомок p)
…… .. б) Левый Правый случай (р левый ребенок г и х прав ребенка р)
…… .. iii) Правый правый случай (Зеркало случая а)
…… .. iv) Правый левый кейс (Зеркало кейса c)

Ниже приведены операции, которые должны быть выполнены в четырех случаях, когда дядя ЧЕРНЫЙ.

Все четыре случая, когда дядя ЧЕРНЫЙ

Левый левый корпус (см. G, p и x)

Левый и правый регистр (см. G, p и x)

Правый правый регистр (см. G, p и x)

Правый левый регистр (см. G, p и x)

Примеры вставки

Ниже приведен код C ++.

/ ** C ++ реализация для вставки красно-черного дерева

Этот код принят из кода, предоставленного

Динеш Хандельвал в комментариях ** /

#include <bits/stdc++.h>

using namespace std;

enum Color {RED, BLACK};

struct Node

{

int data;

bool color;

Node *left, *right, *parent;

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

Node(int data)

{

this->data = data;

left = right = parent = NULL;

this->color = RED;

}

};

// Класс для представления красно-черного дерева

class RBTree

{

private:

Node *root;

protected:

void rotateLeft(Node *&, Node *&);

void rotateRight(Node *&, Node *&);

void fixViolation(Node *&, Node *&);

public:

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

RBTree() { root = NULL; }

void insert(const int &n);

void inorder();

void levelOrder();

};

// Рекурсивная функция для обхода порядка уровней

void inorderHelper(Node *root)

{

if (root == NULL)

return;

inorderHelper(root->left);

cout << root->data << " ";

inorderHelper(root->right);

}

/ * Утилита для вставки нового узла с заданным ключом

в BST * /

Node* BSTInsert(Node* root, Node *pt)
{

/ * Если дерево пустое, вернуть новый узел * /

if (root == NULL)

return pt;

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

if (pt->data < root->data)

{

root->left = BSTInsert(root->left, pt);

root->left->parent = root;

}

else if (pt->data > root->data)

{

root->right = BSTInsert(root->right, pt);

root->right->parent = root;

}

/ * вернуть (неизмененный) указатель узла * /

return root;

}

// Сервисная функция для прохождения порядка уровней

void levelOrderHelper(Node *root)

{

if (root == NULL)

return;

std::queue<Node *> q;

q.push(root);

while (!q.empty())

{

Node *temp = q.front();

cout << temp->data << " ";

q.pop();

if (temp->left != NULL)

q.push(temp->left);

if (temp->right != NULL)

q.push(temp->right);

}

void RBTree::rotateLeft(Node *&root, Node *&pt)

{

Node *pt_right = pt->right;

pt->right = pt_right->left;

if (pt->right != NULL)

pt->right->parent = pt;

pt_right->parent = pt->parent;

if (pt->parent == NULL)

root = pt_right;

else if (pt == pt->parent->left)

pt->parent->left = pt_right;

else

pt->parent->right = pt_right;

pt_right->left = pt;

pt->parent = pt_right;

}

void RBTree::rotateRight(Node *&root, Node *&pt)

{

Node *pt_left = pt->left;

pt->left = pt_left->right;

if (pt->left != NULL)

pt->left->parent = pt;

pt_left->parent = pt->parent;

if (pt->parent == NULL)

root = pt_left;

else if (pt == pt->parent->left)

pt->parent->left = pt_left;

else

pt->parent->right = pt_left;

pt_left->right = pt;

pt->parent = pt_left;

}

// Эта функция исправляет нарушения, вызванные вставкой BST

void RBTree::fixViolation(Node *&root, Node *&pt)

{

Node *parent_pt = NULL;

Node *grand_parent_pt = NULL;

while ((pt != root) && (pt->color != BLACK) &&

(pt->parent->color == RED))

{

parent_pt = pt->parent;

grand_parent_pt = pt->parent->parent;

/ * Дело: А

Родитель pt остается дочерним от Grand-parent of pt * /

if (parent_pt == grand_parent_pt->left)

{

Node *uncle_pt = grand_parent_pt->right;

/* Дело 1

Дядя pt тоже красный

Требуется только перекраска * /

if (uncle_pt != NULL && uncle_pt->color == RED)

{

grand_parent_pt->color = RED;

parent_pt->color = BLACK;

uncle_pt->color = BLACK;

pt = grand_parent_pt;

}

else

{

/ * Дело: 2

pt является правым потомком своего родителя

Требуется вращение влево * /

if (pt == parent_pt->right)

{

rotateLeft(root, parent_pt);

pt = parent_pt;

parent_pt = pt->parent;

}

/ * Дело: 3

pt остается дочерним элементом своего родителя

Требуется вращение вправо * /

rotateRight(root, grand_parent_pt);

swap(parent_pt->color, grand_parent_pt->color);

pt = parent_pt;

}

/ * Дело: B

Родитель pt является правым потомком Grand-parent of pt * /

else

{

Node *uncle_pt = grand_parent_pt->left;

/* Дело 1

Дядя pt тоже красный

Требуется только перекраска * /

if ((uncle_pt != NULL) && (uncle_pt->color == RED))

{

grand_parent_pt->color = RED;

parent_pt->color = BLACK;

uncle_pt->color = BLACK;

pt = grand_parent_pt;

}

else

{

/ * Дело: 2

pt остается дочерним элементом своего родителя

Требуется вращение вправо * /

if (pt == parent_pt->left)

{

rotateRight(root, parent_pt);

pt = parent_pt;

parent_pt = pt->parent;

}

/ * Дело: 3

pt является правым потомком своего родителя

Требуется вращение влево * /

rotateLeft(root, grand_parent_pt);

swap(parent_pt->color, grand_parent_pt->color);

pt = parent_pt;

}

root->color = BLACK;

}

// Функция для вставки нового узла с данными

void RBTree::insert(const int &data)

{

Node *pt = new Node(data);

// Сделать нормальную вставку BST

root = BSTInsert(root, pt);

// исправить нарушения Red Black Tree

fixViolation(root, pt);

}

// Функция для выполнения порядка и обхода порядка

void RBTree::inorder() { inorderHelper(root);}

void RBTree::levelOrder() { levelOrderHelper(root); }

// Код драйвера

int main()

{

RBTree tree;

tree.insert(7);

tree.insert(6);

tree.insert(5);

tree.insert(4);

tree.insert(3);

tree.insert(2);

tree.insert(1);

cout << "Inoder Traversal of Created Tree\n";

tree.inorder();

cout << "\n\nLevel Order Traversal of Created Tree\n";

tree.levelOrder();

return 0;

}

Выход:

Inoder Traversal of Created Tree
1  2  3  4  5  6  7  

Level Order Traversal of Created Tree
6  4  7  2  5  1  3

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

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

Программа C для вставки красного черного дерева

0.00 (0%) 0 votes