0
我有這個類：丟失參考
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樹的根節點失去對其他節點的引用。我該如何解決這個問題的任何想法？