Код вставки красно-черного дерева
Я пытаюсь написать реализацию красно-черного дерева для своего собственного обучения, и я смотрю на это уже несколько дней.
Может ли кто-нибудь помочь мне выяснить, как я могу заставить дела с двойным вращением работать правильно? Если вы замечаете что-то еще, что отстой, пока вы просматриваете фрагменты, не стесняйтесь, чтобы я чувствовал себя идиотом.
Ваша помощь ценится.
Функция ребалансировки
int impl_rbtree_rebalance (xs_rbtree_node *node)
{
check_mem(node);
xs_rbtree_node *p = node->parent;
if (!p) return 0;
if (p->color == BLACK) return 0;
xs_rbtree_node *gp = p->parent;
if (!gp) return 0;
xs_rbtree_node *uncle;
int is_parent_left_child;
/* check if parent is left or right child */
if (p == gp->left) {
uncle = gp->right;
is_parent_left_child = 1;
} else {
uncle = gp->left;
is_parent_left_child = 0;
}
if (uncle && uncle->color == RED) {
p->color = uncle->color = BLACK;
gp->color = RED;
} else { /* uncle is black */
if (gp->parent == NULL) return 0;
if (node == p->left) {
if (is_parent_left_child == 0) {
/* Double rotation logic */
} else {/* parent is left child */
gp->color = RED;
gp->left->color = BLACK;
impl_rbtree_rr(&gp);
}
} else { /* node is right child */
if (is_parent_left_child == 1) {
/* Double rotation logic */
} else { /* parent is right child */
gp->color = RED;
gp->right->color = BLACK;
impl_rbtree_rl(&gp);
}
}
}
return 0;
}
Соответствующие функции
xs_rbtree_node *impl_rbtree_node_alloc (xs_rbtree_node *parent, void *val)
{
xs_rbtree_node *n = malloc(sizeof(xs_rbtree_node));
n->parent = parent;
n->val = val;
n->left = n->right = NULL;
n->color = (parent == NULL) ? BLACK : RED;
return n;
}
void rbtree_insert (xs_rbtree_ *tree, void *val)
{
check_mem(tree);
check_mem(val);
tree->root = impl_rbtree_insert(tree->cmp, NULL, tree->root, val);
tree->root->color = BLACK;
}
xs_rbtree_node *impl_rbtree_insert (xs_tree_cmp cmp, xs_rbtree_node *parent, xs_rbtree_node *node, void *val)
{
check_mem(cmp);
check_mem(val);
if (!node) {
node = impl_rbtree_node_alloc(parent, val);
} else if (cmp(node->val, val) < 0) {
/* node->val < val */
check_mem(node);
node->right = impl_rbtree_insert(cmp, node, node->right, val);
impl_rbtree_rebalance(node->right);
} else if (cmp(node->val, val) > 0) {
/* node->val > val */
check_mem(node);
node->left = impl_rbtree_insert(cmp, node, node->left, val);
impl_rbtree_rebalance(node->left);
}
/* ignoring values that are equal */
return node;
}
Функции вращения
#include <xs/base/bstree.h>
void impl_tree_rr(xs_tree_node **node)
{
check_mem(*node);
check_mem((*node)->left);
xs_tree_node *k1, *k2;
k2 = *node;
k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k1->parent = k2->parent;
k2->parent = k1;
*node = k1;
}
void impl_tree_rl(xs_tree_node **node)
{
check_mem(*node);
check_mem((*node)->right);
xs_tree_node *k1, *k2;
k2 = *node;
k1 = k2->right;
k2->right = k1->left;
k1->left = k2;
k1->parent = k2->parent;
k2->parent = k1;
*node = k1;
}
void impl_tree_drr(xs_tree_node **node)
{
check_mem(*node);
impl_tree_rl(&((*node)->left));
impl_tree_rr(node);
}
void impl_tree_drl(xs_tree_node **node)
{
check_mem(*node);
impl_tree_rr(&((*node)->right));
impl_tree_rl(node);
}
Определения RBT
typedef struct xs_rbtree_node xs_rbtree_node;
typedef struct xs_rbtree_ xs_rbtree_;
typedef enum { RED, BLACK } impl_rbtree_color;
struct xs_rbtree_node {
xs_rbtree_node *left;
xs_rbtree_node *right;
xs_rbtree_node *parent;
void *val;
impl_rbtree_color color;
};
struct xs_rbtree_ {
xs_rbtree_node *root;
xs_tree_cmp cmp;
};
0 ответов
Двойное вращение в красно-черных деревьях довольно сложно по сравнению с деревьями AVL, причина в существовании родительских указателей, которые существуют в деревьях RB. Пока мы вращаем деревья, нам нужно также настроить родительские указатели. Продемонстрирую это на примере. Дерево ниже - это исходное дерево
20 / \ 10 30 / \ 3 15 / \ 12 18
И вот идет повернутый вправо
10 / \ 3 20 / \ 15 30 / \ 12 18Мы наблюдаем там 2 вещи. 1. Изменен рут. 2. Изменились родительские указатели для 3 узлов ( 10, 20, 15) т.е. для нового корня, старого корня и правого потомка нового корня. Это будет верно для всех случаев правого вращения. Это сделано для того, чтобы убедиться, что обход по порядку остается неизменным после того, как произойдет поворот.
Теперь посмотрим, как мы шаг за шагом вращаемся.
public Node rotateRight() {
if(root.left == null) {
System.out.println("Cannot be rotated Right");
} else {
Node newRoot = root.left; // Assign new root.
Node orphaned = newRoot.right; // Store ref to the right child of new root.
newRoot.parent = root.parent; // new root parent point to old root parent.
root.parent = newRoot; // new root becomes parent of old root.
newRoot.right = root; // old root becomes right child of new root
root.left = orphaned;
if (orphaned != null) {
orphaned.parent = root;
}
root = newRoot;
}
return root;
}
Попробуйте сделать это на бумаге пару раз, тогда будет проще. Надеюсь это поможет.
Возвращаясь к RB Trees. Вышеупомянутая реализация будет применяться к обоим поворотам, которые мы делаем в процессе балансировки. (Давайте возьмем правильный правильный случай)
Когда у нас есть 3 поколения узлов, дедушка, отец и ребенок, которые вставлены. 1. Когда у нас есть конфигурация RR или LL, не меняем цвета. 2. С RL и LR мы вращаем дедушку, мы меняем цвета дедушки и отца, но при повороте родителя мы не пытаемся менять цвета. Намерение просто вывести их в конфиги RR или LL.
a. We need to see if the grandpa is right or left child of its parent and assign the root accordingly. b. If the grandpa has no parent means we are doing rotation at the level of tree's root, then we reassign the root of the tree.
Фрагмент моей реализации дерева RB.
temp is the new node which is added.
// if new node is the right child AND parent is right child
else if(temp.parent.right == temp && grandPa!=null && grandPa.right == temp.parent) {
// If becomes a right-right case
Boolean isLeft = isLeftChild(grandPa);
if(isLeft == null) {
// Grandpa has no parent, reassign root.
root = rotateLeft(grandPa,true);
}
else if(isLeft) {
grandPa.parent.left = rotateLeft(grandPa,true);
} else {
grandPa.parent.right = rotateLeft(grandPa,true);
}
}