У меня есть этот класс:Losing ссылки в дереве AVL
class AVLTree
class Node
attr_accessor :value, :height
attr_accessor :left, :right
def initialize(value, height)
@value = value
@height = height
end
end
attr_accessor :root
def initialize
@root = Node.new(nil, 0)
end
# Right rotation of the tree
def right_rotation(node = @root)
begin
root = node.left
node.left = root.right
root.height = node.height
root.right = node
update_subtrees_height(root.right, root.height)
update_subtrees_height(root.left, root.height)
rescue Exception => e
puts "Tree not able to do a right rotation: #{e.message}"
puts e.backtrace.inspect
end
root
end
# Left rotation of the tree
def left_rotation(node = @root)
begin
root = node.right
node.right = root.left
root.height = node.height
root.left = node
update_subtrees_height(root.right, root.height)
update_subtrees_height(root.left, root.height)
rescue Exception => e
puts "Tree not able to do a left rotation: #{e.message}"
puts e.backtrace.inspect
end
root
end
# Update the height of the elements of a sub-tree and all other sub-tree of its side
def update_subtrees_height(node, height)
return if node.nil?
node.height = height + 1
update_subtrees_height(node.left, node.height)
update_subtrees_height(node.right, node.height)
end
def balance_factor(node = @root)
leftSize = node.left.nil? ? 0 : deepest_node(node.left).height
rightSize = node.right.nil? ? 0 : deepest_node(node.right).height
rightSize - leftSize
end
def balance(node = @root)
balanceFactor = balance_factor(node)
return node if balanceFactor <= 1 && balanceFactor >= -1
if balanceFactor > 1
if balance_factor(node.right) < 0
node.right = right_rotation(node.right)
node = left_rotation(node)
else
node = left_rotation(node)
end
else
if balance_factor(node.left) > 0
node.left = right_rotation(node.left)
node = left_rotation(node)
else
node = right_rotation(node)
end
end
end
def print_tree(node = @root)
return if node.nil?
puts "#{node.left.nil? ? 'null' : node.left.value} - #{node.nil? ? 'null' : node.value}(L#{node.height}) - #{node.right.nil? ? 'null' : node.right.value}"
print_tree(node.left)
print_tree(node.right)
end
def deepest_node(node = @root, deepest = @root)
return deepest if node.nil?
if node.height > deepest.height then deepest = node else deepest end
right = deepest_node(node.left, deepest)
left = deepest_node(node.right, deepest)
right.height > left.height ? right : left
end
def insert(value, node = @root)
case value <=> node.value
when -1
if node.left.nil?
node.left = Node.new(value, node.height + 1)
else
insert(value, node.left)
node = balance(node.left)
end
when 1
if node.right.nil?
node.right = Node.new(value, node.height + 1)
else
insert(value, node.right)
node = balance(node)
end
else
node.value = value
end
end
end
Я делаю этот тест:
a = AVLTree.new
[1,2,3,4,5].each do |v|
a.insert v
end
a.print_tree a.root
Мой ожидается выход на
1 - 2(H0) - 4
null - 1(H1) - null
3 - 4(H1) - 5
null - 3(H2) - null
null - 5(H2) - null
кто represet дерево ниже:
2
/\
1 4
/\
3 5
Вывод, что у меня есть:
null - 1(H2) - null
отладки кода, я descovered, что проблема возникает в моем insert методе, каждый раз, когда я называю линию node = balance(node.left). В это время я теряю ссылки на дерево.
Метод balance в моих тестах. Например:
Когда я вставить 3 на дереве, у меня есть
1
\
2
\
3
, а затем я вызвать баланс с узлом 1, получая ожидаемое дереву
2
/\
1 3
Логика, Я думал: каждый раз, когда я вставляю значение в дерево, я проверю его баланс и исправлю его, если это необходимо. С рекурсивностью моего метода insert я проверю дерево вверх, начиная с одной точки выше от вставленного узла. В приведенном выше примере, когда я перехожу к узлу 1 и балансирую его, метод balance вернет новый узел с 2, как корень этого поддерева, и мой старый узел получит это.
Это происходит, но по какой-то причине корневой узел дерева AVL потерял ссылки на другие узлы. Любая идеология, как я могу это исправить?