作者superme7 (Bonbodi)
看板C_and_CPP
標題[問題] 紅黑樹construct設root = nil遇到的問題
時間Tue Apr 27 21:17:26 2021
開發平台(Platform): (Ex: Win10, Linux, ...)
Win10
編譯器(Ex: GCC, clang, VC++...)+目標環境(跟開發平台不同的話需列出)
GCC
額外使用到的函數庫(Library Used): (Ex: OpenGL, ...)
無
問題(Question)：
RBT，Tree的construct把root = nil，Insert node 後 root 無法更新 依然指向nil
餵入的資料(Input)：
在int main 中
預的正確確結果(Expected Output)：
Black/5 Black/8 Red/11 Black/9
錯誤結果(Wrong Output)：
沒有顯示
程式碼(Code)：(請善用置底文網頁, 記得排版，禁止使用圖檔)
#include <iostream>
#include <string>
using namespace std;
class Node
{
public:
int key;
Node* p, * left, * right;
string color;
Node() :key(0), p(0), left(0), right(0), color("") {};
Node(int a) :key(a), left(0), right(0), p(0), color("") {};
};
class Tree
{
public:
Node* nil;
Node* root;
Tree()
{
nil = new Node;
nil->color = "black";
root = nil;
root->p = nil;
}
};
void left_Rotate(Tree t, Node* x)
{
Node* y = x->right;
x->right = y->left;
if (y->left != t.nil)
y->left->p = x;
if (x->p == t.nil)
t.root = y;
else if (x == x->p->left)
x->p->left = y;
else
x->p->right = y;
y->p = x->p;
y->left = x;
x->p = y;
}
void right_Rotate(Tree t, Node* x)
{
Node* y = x->left;
x->left = y->right;
if (y->right != t.nil)
y->right->p = x;
if (x->p == t.nil)
t.root = y;
else if (x->p->left == x)
y = x->p->left;
else
y = x->p->right;
y->p = x->p;
y->right = x;
x->p = y;
}
void InsertFixup(Tree t, Node* z)
{
while (z->p->color == "red")
{
if (z->p == z->p->p->left)
{
Node* y = z->p->p->right;
if (y->color == "red")
{
y->color = "black";
z->p->color = "black";
z->p->p->color = "red";
z = z->p->p;
}
else
{
if (z == z->p->right)
{
z = z->p;
left_Rotate(t, z);
}
z->p->color = "black";
z->p->p->color = "red";
right_Rotate(t, z->p->p);
}
}
else
{
Node* y = z->p->p->left;
if (y->color == "red")
{
y->color = "black";
y->p->p->color = "red";
z->p->color = "black";
z = z->p->p;
}
else
{
if (z == z->p->left)
{
z = z->p;
right_Rotate(t, z);
}
z->p->color = "black";
z->p->p->color = "red";
left_Rotate(t, z->p->p);
}
}
}
t.root->color = "black";
}
void Insert(Tree t, Node* z)
{
Node* y = t.nil;
Node* x = t.root;
while (x != t.nil)
{
y = x;
if (z->key < x->key)
x = x->left;
else
x = x->right;
}
z->p = y;
if (y == t.nil)
t.root = z;
else if (z->key < y->key)
y->left = z;
else
y->right = z;
z->color = "red";
z->left = t.nil;
z->right = t.nil;
InsertFixup(t, z);
}
void Inorder(Tree t, Node* z)
{
if (z != t.nil)
{
Inorder(t, z->left);
cout << z->color << "/" << z->key << " ";
Inorder(t, z->right);
}
}
int main()
{
Tree a;
Node* b = new Node(8);
Node* c = new Node(11);
Node* d = new Node(9);
Node* e = new Node(5);
Insert(a, b);
Insert(a, c);
Insert(a, d);
Insert(a, e);
Inorder(a,a.root);
return 0;
}
補充說明(Supplement)：
我在想root是不是還是指向nil，所以Inorder Print不出來
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.136.220 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1619529448.A.DB4.html
1F：推 LPH66: 對, 因為你的 Tree 是傳值傳進去的, 裡面更新沒有傳出來 04/28 02:41
2F：→ LPH66: 看你要傳它的指標還是要改成傳參考 04/28 02:41
3F：→ superme7: 對吼 謝謝L大 04/28 09:05