Ich habe diese Klasse:Losing Referenzen in einem AVL-Baum
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
ich diesen Test machen:
a = AVLTree.new
[1,2,3,4,5].each do |v|
a.insert v
end
a.print_tree a.root
Meine erwartete Ausgabe ist
1 - 2(H0) - 4
null - 1(H1) - null
3 - 4(H1) - 5
null - 3(H2) - null
null - 5(H2) - null
, der den Baum represet unten:
2
/\
1 4
/\
3 5
Die Ausgabe, die ich habe, ist:
null - 1(H2) - null
den Code Debuggen, ich descovered, dass das Problem in meinem insert Verfahren auftritt, node = balance(node.left) jedes Mal, wenn ich die Linie nennen. Zu dieser Zeit verliere ich die Referenzen des Baumes.
Die balance Methode ist in meinen Tests ok. Zum Beispiel:
Wenn ich die 3 am Baum einzufügen, habe ich
1
\
2
\
3
und dann nenne ich das Gleichgewicht mit dem Knoten 1, der erwarteten Baum
2
/\
1 3
Die Logik empfängt, die Ich dachte: Jedes Mal, wenn ich einen Wert in den Baum einfüge, überprüfe ich sein Gleichgewicht und korrigiere es, falls nötig. Mit der Rekursivität meiner Methode insert werde ich den Baum nach oben überprüfen, beginnend einen Punkt über dem eingefügten Knoten. Im obigen Beispiel wird die Methode balance, wenn ich zu Knoten 1 gehe und sie ausgleiche, einen neuen Knoten mit der 2 wie die Wurzel dieses Unterbaums zurückgeben, wobei mein alter Knoten dies erhält.
Das passiert, aber aus irgendeinem Grund verlor der Wurzelknoten des AVL-Baums Verweise auf andere Knoten. Irgendwelche Idea, wie kann ich das beheben?