Двоичные деревья поиска (BST) и Красно-чёрные деревья (RBT)

1. Двоичное дерево поиска (BST)

Свойство BST: Для любого узла $x$, ключи в левом поддереве $\le x.key$, а ключи в правом поддереве $\ge x.key$.

Удаление узла $z$ из BST (3 случая):

2. Красно-чёрное дерево (Red-Black Tree)

Красно-чёрное дерево — сбалансированное двоичное дерево поиска, гарантирующее высоту $h \le 2 \log_2(n + 1)$ за счет 5 свойств:

// Левый поворот вокруг узла x
void leftRotate(Node*& root, Node* x) {
    Node* y = x->right;
    x->right = y->left;
    if (y->left != nullptr) 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->parent = y;
}