RB Tree не работает для * некоторых * несортированных массивов - PullRequest
Новая
       68

RB Tree не работает для * некоторых * несортированных массивов

0 голосов
/ 21 марта 2020 
if(node.parent.parent.parent.right == node.parent.parent):
                            tnode = self.LR(node.parent.parent)
                            node.parent.parent.parent.right = tnode

Это часть кода, которая приводит к ошибке. Скажем, вставленные узлы 5,12,10, а затем это приводит к ошибке во время выполнения. Вставка 5,10,12 будет работать, однако. (10,8,12 работает, хотя).

Возвращенная ошибка: 

File "Solution.py", line 132, in Balance
    if(node.parent.parent.parent.right == node.parent.parent):
AttributeError: 'NoneType' object has no attribute 'right'

Может кто-нибудь помочь мне исправить это? Код уже слишком большой, и я запутался.

1 Ответ

0 голосов
/ 21 марта 2020

Во-первых, убедитесь, что вы действительно имели в виду «node.parent.parent.parent», так как обычные правила ребалансировки RB требуют только, чтобы родитель и дедушка были проверены на любом данном этапе.

Если вы на самом деле действительно означает node.parent.parent.parent, чтобы убедиться, что он не равен нулю, прежде чем проверять "right".

...