再帰的メソッドの停止条件が適切なタイミングで機能しない

Question

私には特有の問題があります。私はいくつかの方法で二分探索木をコーディングしています：

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 

問題がupdate_subtrees_heightで発生します。このテストを検討：ステップによって

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 

ステップを、このテストを行います。

1）ツリー釜と、それを印刷（出力は私print_tree方法である）：

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

表します次のツリー：

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

2）ツリーから9を削除し、もう一度印刷してください。

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

として出力で示した、子供10（出力でHで表される）の高さは、私は私の再帰的なメソッドupdate_subtrees_height呼び出すとき、それは2と呼ばれている理由hapens 1である必要がある場合、0であります停止前の時間。しかし、私が9を取り除くことは、それを正しい子供、10に置き換えて、次にupdate_subtrees_heightにノード10を渡してその高さを減らすというものです。

この更新メソッドを呼び出すと、私は停止条件return if node.nil?を持っています。ノード10では、最初の反復で停止せず、高さを1に減らして（目的の結果）、node.rightを渡して再帰的にメソッドを呼び出します。私のnode.rightはゼロですが、メソッドは次の反復（！）で停止せず、ノード10の高さを再び減少させます（今度は0に、私が持っていた出力）。 3回目の反復では、メソッドは停止します。

この第3の繰り返しがなぜ発生するのか誰かが知っていますか？

Answer 1

あなたdelete_node方法にエラーがあります：

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 

は以下にそれを修正して、すべてが動作しますが！