Ctrlalt: /* Ссылки */

2023-04-26T23:12:40Z

Ссылки

← Предыдущая версия		Версия от 23:12, 26 апреля 2023
Строка 121:		Строка 121:

	Теория:		Теория:
	:* [https://neerc.ifmo.ru/wiki/index.php?title=Красно-черное_дерево neerc.ifmo.ru/wiki — Красно-черное_дерево]		* [https://neerc.ifmo.ru/wiki/index.php?title=Красно-черное_дерево neerc.ifmo.ru/wiki — Красно-черное_дерево]
	:* [https://disk.yandex.ru/i/~~GtHnyXUHVF3arg~~ Вставка в красно-чёрное дерево]		* [https://disk.yandex.ru/i/7LKoFkz7vP7-8A Вставка в красно-чёрное дерево]
	:* [https://algs4.cs.princeton.edu/lectures/keynote/33BalancedSearchTrees.pdf algs4.cs.princeton.edu — Balanced Search Trees]		* [https://algs4.cs.princeton.edu/lectures/keynote/33BalancedSearchTrees.pdf algs4.cs.princeton.edu — Balanced Search Trees]
	Демонстрация:		Демонстрация:
	:* [https://www.cs.usfca.edu/~galles/visualization/RedBlack.html www.cs.usfca.edu — Red/Black Tree]		* [https://www.cs.usfca.edu/~galles/visualization/RedBlack.html www.cs.usfca.edu — Red/Black Tree]
	Код:		Код:
	:* [https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/RedBlackBST.java kevin-wayne/algs4/RedBlackBST.java]		* [https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/RedBlackBST.java kevin-wayne/algs4/RedBlackBST.java]

Ctrlalt: Новая страница: «== Правила == * Каждый узел является красным или чёрным. * Корень и (воображаемые) nullptr-потом...»

2021-05-21T10:12:56Z

Новая страница: «== Правила == * Каждый узел является красным или чёрным. * Корень и (воображаемые) nullptr-потом...»

Новая страница

== Правила ==
* Каждый узел является красным или чёрным.
* Корень и (воображаемые) nullptr-потомки листьев — чёрные.
* Родитель красного узла обязан быть чёрным (потомок и родитель не могут быть красными одновременно, не может быть двух красных узлов подряд);
* Все простые пути пути от любой вершины до любого листа в её поддереве содержат одинаковое количество чёрных узлов.

== Код ==
class RBTree {
struct Node {
int key;
Node *l = nullptr, *r = nullptr, *p = nullptr;
char color = 'R';

Node *other(Node *n) {
return l == n ? r : l;
}
} *root = nullptr;

bool find(Node *node, int key) const {
if (!node)
return false;
if (key == node->key)
return true;
return find(key < node->key ? node->l : node->r, key);
}

void rotateLeft(Node *x) {
Node *y = x->r;
x->r = y->l;
if (y->l)
y->l->p = x;
y->p = x->p;
if (!x->p)
root = y;
else if (x == x->p->l)
x->p->l = y;
else
x->p->r = y;
y->l = x;
x->p = y;
}

void rotateRight(Node *x) {
Node *y = x->l;
x->l = y->r;
if (y->r)
y->r->p = x;
y->p = x->p;
if (!x->p)
root = y;
else if (x == x->p->r)
x->p->r = y;
else
x->p->l = y;
y->r = x;
x->p = y;
}

void fix(Node *me) {
if (me->color == 'B')
return;

Node *dad = me->p;
if (dad && dad->color == 'B')
return;

Node *grandDad = dad->p, *uncle = grandDad ? grandDad->other(dad) : nullptr;
if (uncle && uncle->color == 'R') {
dad->color = uncle->color = 'B';
grandDad->color = 'R';
return;
}

if (me == dad->r && dad == grandDad->l) {
rotateLeft(dad);
return fix(me->l);
}

if (me == dad->l && dad == grandDad->r) {
rotateRight(dad);
return fix(me->r);
}

dad->color = 'B';
grandDad->color = 'R';
if (me == dad->l) {
rotateRight(grandDad);
} else {
rotateLeft(grandDad);
}
}

void insert(Node *&node, int key) {
if (!node) {
node = new Node({ key });
return;
}
if (key < node->key) {
insert(node->l, key);
node->l->p = node;
fix(node->l);
} else {
insert(node->r, key);
node->r->p = node;
fix(node->r);
}
}

public:
bool find(int key) const {
return find(root, key);
}

void insert(int key) {
insert(root, key);
root->color = 'B';
}
};

== Ссылки ==

Теория:
:* [https://neerc.ifmo.ru/wiki/index.php?title=Красно-черное_дерево neerc.ifmo.ru/wiki — Красно-черное_дерево]
:* [https://disk.yandex.ru/i/GtHnyXUHVF3arg Вставка в красно-чёрное дерево]
:* [https://algs4.cs.princeton.edu/lectures/keynote/33BalancedSearchTrees.pdf algs4.cs.princeton.edu — Balanced Search Trees]
Демонстрация:
:* [https://www.cs.usfca.edu/~galles/visualization/RedBlack.html www.cs.usfca.edu — Red/Black Tree]
Код:
:* [https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/RedBlackBST.java kevin-wayne/algs4/RedBlackBST.java]

Красно-чёрное дерево - История изменений

Ctrlalt: /* Ссылки */

Ctrlalt: Новая страница: «== Правила == * Каждый узел является красным или чёрным. * Корень и (воображаемые) nullptr-потом...»