1
I have the following problem: I’m making a Red-Black Tree in Python, and when I delete a root that has only one child, the problem happens, below follows my code
BLACK = 0
RED = 1
class No():
def __init__(self, valor, pai=None, esquerda=None, direita=None, cor=RED):
self.valor = valor
self.esquerda = esquerda
self.direita = direita
self.pai = pai
if pai == None:
self.cor = BLACK
else:
self.cor = cor
def filho_nao_nulo(self):
return (self.direita if self.direita != None else self.esquerda)
def remover(self, valor):
#global raiz
no = self
if no == None:
return None
if valor < no.valor:
no.esquerda.remover(valor)
elif valor > no.valor:
no.direita.remover(valor)
else:
#o nó encontrado só tem um filho
if no.direita != None or no.esquerda != None:
if no.cor == BLACK:
#se o nó é a raiz
if no.pai == None:
if no.esquerda == no.filho_nao_nulo():
no = no.esquerda
no.cor = BLACK
else:
no = no.direita
no.cor = BLACK
raiz = No(12)
raiz.direita = No(14, raiz)
raiz.remover(12)
On reaching the line
no = no.direita
the debug is that way:
When running this line, only the local variable "no" is changed, but the global "root" is not, both of which refer to the same memory address
the node has the memory address of the root right, as it should be done with the root, but the root is not changed.
The strange thing is that this only happens with the root, if the node, for example, was equal to the root.rightita.left, there would be no problem with any operation I wanted to do about that node, it would change both the local variable, and the global one.
I had a similar problem in the AVL tree.
The temporary solution I had was to declare the code
global raiz
at the beginning of the method, and change the root directly. But I read about, and saw that this is not a good practice. Could anyone help me ? Thank you.
Fill in the part that has the "#code block", because without it, you can’t reproduce the problem. And put the class part
No
necessary to this. Besides, your question seems to me to be legal.– Victor Stafusa
Okay, I’ll try to add all the code.
– Gabriel Henrique
I just added Victor, now you should be able to run the code.
– Gabriel Henrique
Important [Dit] question and reduce code to a [mcve] problem.
– Bacco
Okay, the code is now very dry and executable, but I believe that I can not remove the images, with them becomes much clearer what is happening in debug.
– Gabriel Henrique