Stopp-Bedingung der rekursiven Methode funktioniert nicht zur richtigen Zeit

Question

Ein eigenartiges Problem tritt bei mir auf. Ich bin Codierung einen binären Suchbaumes mit einigen Methoden:

class BinarySearchTree 
    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 

def insert(value) 
    node = @root 
    loop do 
    case value <=> node.value 
    when -1 
     if node.left.nil? 
     node.left = Node.new(value, node.height + 1) 
     break 
     else 
     node = node.left 
     end 
    when 1 
     if node.right.nil? 
     node.right = Node.new(value, node.height + 1) 
     break 
     else 
     node = node.right 
     end 
    else 
     node.value = value 
     break 
    end 
    end 
end 

def delete(value, node = @root) 
    return if node.nil? 
    if value == node.value 
    node = delete_node(node) 
    elsif value < node.value 
    node.left = delete(value, node.left) 
    elsif 
    node.right = delete(value, node.right) 
    end 
    node 
end 

def delete_node(node) 
    if node.left.nil? && node.right.nil? 
    node = nil 
    elsif node.left.nil? || node.right.nil? 
    if node.left.nil? 
     node = node.right 
     update_subtrees_height(node, -1, {left: false, right: true}) 
    else 
     node = node.right end 
     update_subtrees_height(node, -1, {left: true, right: false}) 
    else 
    #TODO 
    end 
    node 
end 

def update_subtrees_height(node, value, options = {left: true, right: true}) 
    return if node.nil? 
    node.height = node.height + value 
    update_subtrees_height(node.left, value, options) if options[:left] 
    update_subtrees_height(node.right, value, options) if options[:right] 
end 

# For debug 
def print_tree(node = @root) 
    return if node.nil? 
    puts "#{node.left.nil? ? 'null' : node.left.value} - #{node.nil? ? 'null' : node.value}(H#{node.height}) - #{node.right.nil? ? 'null' : node.right.value}" 
    print_tree(node.left) 
    print_tree(node.right) 
end 
end 

Das Problem tritt in den update_subtrees_height. Betrachten Sie diesen Test:

bTree = BinarySearchTree.new 

[8,7,9,10].each do |v| 
    bTree.insert(v) 
end 

bTree.print_tree bTree.root 
bTree.root = bTree.delete(9) 
bTree.print_tree bTree.root 

Schritt für Schritt dieser Test funktioniert:

1) Buil dem Baum und ausdrucken (die Ausgabe ist von meiner print_tree-Methode):

7 - 8(H0) - 9 
null - 7(H1) - null 
null - 9(H1) - 10 
null - 10(H2) - null 

Das entspricht der folgende Baum:

8  # Height 0 
/\ 
7 9 # Height 1 
     \ 
     10 # Height 2 

2) Löschen Sie die 9 aus dem Baum und drucken Sie sie erneut:

7 - 8(H0) - 10 
null - 7(H1) - null 
null - 10(H0) - null 

Wie gezeigt in der Ausgabe, die Höhe des Kindes 10 (dargestellt mit einem H in der Ausgabe) 0 ist, wann sollte 1 sein, dass hapens warum, wenn ich meine rekursive Methode update_subtrees_height nennen, es zwei genannt Zeiten vor dem Stop. Aber was ich tue, die 9 entfernend, ersetze es mit seinem rechten Kind, dem 10, und dann rufe ich update_subtrees_height an, den Knoten 10 passierend, um seine Höhe zu verringern.

Bei dieser Update-Methode habe ich die Stopp-Bedingung return if node.nil?. Mit dem Knoten 10 höre ich nicht bei der ersten Iteration auf, erniedrige seine Höhe auf 1 (das gewünschte Ergebnis) und rufe die Methode rekursiv auf und überlasse node.right. Mein node.right ist null, aber die Methode stoppt nicht bei der nächsten Iteration (!), Wodurch die Höhe des Knotens 10 wieder verringert wird (diesmal auf 0, die Ausgabe, die ich hatte). Bei der dritten Iteration stoppt die Methode.

Jemand hat eine Idee, warum diese dritte Iteration passiert?

Answer 1

Es ist ein Fehler in Ihrer delete_node Methode:

def delete_node(node) 
    if node.left.nil? && node.right.nil? 
    node = nil 
    elsif node.left.nil? || node.right.nil? 
    if node.left.nil? 
     node = node.right 
     update_subtrees_height(node, -1, {left: false, right: true}) 
    else 
     node = node.right end 
#      ^^^ 
     update_subtrees_height(node, -1, {left: true, right: false}) 
    else 
    #TODO 
    end 
    node 
end 

Fix an folgenden und alle arbeiten!

def delete_node(node) 
    if node.left.nil? && node.right.nil? 
    node = nil 
    elsif node.left.nil? || node.right.nil? 
    if node.left.nil? 
     node = node.right 
     update_subtrees_height(node, -1, {left: false, right: true}) 
    else 
     node = node.right 
     update_subtrees_height(node, -1, {left: true, right: false}) 
    end 
    else 
    #TODO 
    end 
    node 
end