алгоритм — Реализация красного черного дерева в C ++ с использованием глобального указателя

Question

алгоритм — Реализация красного черного дерева в C ++ с использованием глобального указателя

У меня проблемы с обновлением моего глобального указателя в следующем коде,

#include <iostream>

using namespace std;

struct RB{
RB()=default;
RB(int clr):color(clr) { }
int color;
RB *p,*left,*right;
int key;
};

RB *Tnil=new RB(0);
RB *T=Tnil;
void insert(RB *T,RB *z)
{
RB *y=Tnil;
RB *x=T;
while(x!=Tnil)
{
y=x;
if(z->key<y->key)
x=x->left;
else
x=x->right;
}
z->p=y;
if(y==Tnil)
T=z;
else if(z->key<y->key)
y->left==z;
else
y->right=z;
z->right=Tnil;
z->left=Tnil;
z->color=1;
}

void print(RB *T)
{
if(T==Tnil)
return;
print(T->left);
cout<<T->key;
print(T->right);
}

int main()
{
for(int i=1;i<10;++i)
{
RB *x=new RB;
x->key=i;
insert(T,x);

}
print(T);
}

Проблема в том, что сравнение y==Tnil в моем insert Функция оценивается как ложная, когда я ожидал, что это будет правдой. После завершения функции, T снова становится равным Tnilв результате ничего не вставляется. Любая помощь?

0

algorithm c++red-black-tree

Решение

Другие решения

Вы хотите обновить глобальный T.
Поэтому вы должны передать ссылку на глобальный T для вставки:

замещать

пустотная вставка (RB * T, RB * z)

с

пустотная вставка (RB * & T, RB * z)

(в противном случае обновляется только копия глобального указателя T)

Также как упомянуто ComicSansMS в вашем примере

y->left==z

должен быть заменен

y->left=z

Лучший,

Джек

2

Источник

Accepted Answer

Ваше имя испорчено.

У вас есть две переменные с именем Tодин в глобальном масштабе, а другой в качестве параметра insert, Поэтому назначение T=z; в insert на самом деле не работает с глобальной переменной T но по параметру и, следовательно, не имеет побочных эффектов вне функции.

Как правило, старайтесь избегать однобуквенных имен переменных, таких как T, z а также x, Они затрудняют чтение вашего кода и могут легко скрывать ошибки, подобные этой. Кроме того, избегайте выполнения нелокализованных обновлений внутри функций. Обновление глобальных переменных из функций просто требует таких проблем. Лучшим подходом было бы иметь insert вместо этого верните указатель на новый узел верхнего уровня.

0