1
我從Thomas H Cormen的書「算法介紹」以及其他紅黑樹的僞代碼中找到了僞代碼。紅黑樹插入和固定來自有問題的僞代碼
插入的僞代碼，並插入修復位於here
我得到這條線一賽格故障：試圖插入「8」時，利用下面的測試數據插入修復功能內while(n->parent->color == 'r')：
測試數據：
i 5
i 7
i 1
i 8
i 3
我相信這是由於n的父母可能不存在？但我不能確定如何相應地更改代碼，而無需完全搞砸了的僞代碼：
這裏是我的插入：
void insert_fix(node * n)
{
node * y;
if(n->parent)
{
while(n->parent->color == 'r')
{
if(n->parent == n->parent->parent->left)
{
y = n->parent->parent->right;
if(y->color == 'r')
{
n->parent->color = 'b';
y->color = 'b';
n->parent->parent->color = 'r';
n = n->parent->parent;
}
else
{
if(n == n->parent->right)
{
n = n->parent;
rotate_left(n);
}
n->parent->color = 'b';
n->parent->parent->color = 'r';
}
}
else
{
y = n->parent->parent->left;
if(y->color == 'r')
{
n->parent->color = 'b';
y->color = 'b';
n->parent->parent->color = 'r';
n = n->parent->parent;
}
else
{
if(n == n->parent->left)
{
n = n->parent;
rotate_right(n);
}
n->parent->color = 'b';
n->parent->parent->color = 'r';
}
}
}
}
root->color = 'b';
}
這裏是我的插入修復：
void insert_fix(node * n)
{
node * y;
if(n->parent)
{
while(n->parent->color == 'r')
{
if(n->parent == n->parent->parent->left)
{
y = n->parent->parent->right;
if(y->color == 'r')
{
n->parent->color = 'b';
y->color = 'b';
n->parent->parent->color = 'r';
n = n->parent->parent;
}
else
{
if(n == n->parent->right)
{
n = n->parent;
rotate_left(n);
}
n->parent->color = 'b';
n->parent->parent->color = 'r';
}
}
else
{
y = n->parent->parent->left;
if(y->color == 'r')
{
n->parent->color = 'b';
y->color = 'b';
n->parent->parent->color = 'r';
n = n->parent->parent;
}
else
{
if(n == n->parent->left)
{
n = n->parent;
rotate_right(n);
}
n->parent->color = 'b';
n->parent->parent->color = 'r';
}
}
}
}
root->color = 'b';
}
*要要清楚，我在上面的while循環中添加了額外的if語句，這樣如果節點是根節點，就不會發生任何事情，但它並沒有像我希望的那樣解決我的問題。
良好的措施，我寫了旋轉左，右功能有所不同基於關閉的信息，我發現在互聯網上，我認爲他們是很好寫的：
void rotate_right(node *n)
{
node* left = n->left;
swap_nodes(n, left);
n->left = left->right;
if(left->right != NULL)
left->right->parent = n;
left->right = n;
n->parent = left;
}
void rotate_left(node *n)
{
node* right = n->right;
swap_nodes(n, right);
n->right = right->left;
if(right->left != NULL)
right->left->parent = n;
right->left = n;
n->parent = right;
}
void swap_nodes(node* oldNode, node* newNode)
{
if(oldNode->parent == NULL)
root = newNode;
else
{
if(oldNode == oldNode->parent->left)
oldNode->parent->left = newNode;
else
oldNode->parent->right = newNode;
}
if(newNode != NULL)
newNode->parent = oldNode->parent;
}
同樣，我覺得我真正的代碼準確地跟隨僞代碼，但我無法弄清楚我錯過的部分。
讓我知道！謝謝！