バイナリツリーの作成

ルビーを学び始めたとき、言語をよりよく理解するために、バイナリツリーとその基本操作（挿入、削除、ウォーク、検索）を実装することにしました。 バイナリツリー。これは、条件演算子、ループ、クラスなど、言語の機能を理解するための良い練習です。 同時に、これは興味深い問題を解決する機会でもあります。 バイナリツリーアルゴリズムは、多くの書籍やインターネットで詳しく説明されています。

タスクを複雑にするために、html5とCanvasを使用してバイナリツリーのレンダリングも実装しました。 これにより、バイナリツリーの動作をより明確に理解できます。 ウェブサイトでデモを見ることができます 。

次に、バイナリツリーを構築するための基本的な方法の実装について簡単に説明します。

二分木または二分探索木

以下の実際のコードは、バイナリツリーのより具体的なバージョンであるバイナリ検索ツリー（BST）を実装しています。 バイナリツリーでは、各ノードには2つ以下の子があり、そのうちの1つは「左サブツリー」と呼ばれ、もう1つは「右サブツリー」でソートなしです。 バイナリ検索ツリーでは、すべてのノードが次のルールに反映されている順序で保存されます。

xがバイナリ検索ツリーのノードであり、yがxの「左サブツリー」である場合、y.key≤x.keyであるとします。 yがxの「右サブツリー」である場合、y.key≥x.key。

二分探索木を実装する

実装したツリーを操作するためのクラスは、次のように使用できます。

require "binarytree" tree = BinaryTree.new(40) tree.add(30) tree.add(100) tree.add(20) tree.add(35) tree.add(25) tree.add(34) puts "Tree nodes: #{tree.to_s}" => "20, 25, 30, 34, 35, 40, 100"
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このクラスは、数字、文字列、またはマッチングをサポートするネイティブルビータイプ（<=>）で使用できます

バイナリツリーにノードを追加する

バイナリツリーにノードを追加するためのコードを以下に示します。 このコードはまずルートノードがあるかどうかを確認し、ない場合は新しい値でルートノードを作成します。 すでにルートノードがある場合、最終ノードに到達するまでツリーのノードをスキャンします（上記のルールを使用）。 最終ノードに到達するとすぐに、新しいノードを指すように更新します。

 def add(new_value) if @root == nil @root = Node.new(new_value) @total_nodes = 1 return end current = @root while(true) if new_value >= current.value if current.right == nil current.right = Node.new(new_value) break else current = current.right end else if current.left == nil current.left = Node.new(new_value) break else current = current.left end end end @total_nodes += 1 end
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ウッドウォーキング

バイナリ検索ツリーの利点の1つは、そこに格納されている値を取得するのが非常に簡単であることです。 このプロセスは、「ソートされたツリーを歩く」と呼ばれます。 たとえば、100、50、200、および150の値を持つツリーがある場合、ソートされたツリーは50、100、150、および200の値を返します。ツリー内のウォーキングは、再帰関数を使用して実装できます。 ただし、再帰的な方法はエレガントですが、ツリーが大きい場合はあまり効果的ではありません。 私が実装したコードは再帰を使用していませんが、代わりにスタックとして配列を使用して、アクセスするノードを追跡します。 このソリューションは再帰ほどエレガントではありませんが、ツリーに数千のノードがある場合でもうまく機能します。

 def walk return nil if @root == nil node = @root stack = [] ignore_left = false while(true) #p "processing #{node.value.to_s}" if ignore_left #p "ignoring nodes to the left" ignore_left = false else if node.left != nil #p "moving to the left" stack << node node = node.left next end end yield node if node.right != nil #p "moving to the right" node = node.right next end break if stack.length == 0 #p "popping from the stack" node = stack.pop ignore_left = true end end
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この方法を実装している間に、最高のルビー機能の1つであるブロックの美しさとシンプルさを実感しました。 アルゴリズムが処理する次のノードを見つけると、呼び出しプログラムにそれを渡します。 これにより、ツリーを歩いて、各ノードで実行するアクションから完全に独立することができます。 たとえば、ノードごとに次のコードを作成できます。

 tree.walk { |node| puts "#{node.value}" }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この例では、ブロックは値を単純に「表示」しますが、バイナリツリーをレンダリングするコードを検討すると、より複雑な例が表示されます。

二分木を描く方法

バイナリツリーレンダリングアルゴリズムは、各ノードを配置する座標とノードの交差方法を計算する必要があることを除いて、ツリーウォーキングアルゴリズムとほぼ同じです。 座標の計算は興味深い仕事でした。



主なアルゴリズムは次のとおりです。

• 指定された座標でルートノードを描画します
• ルートノードの左から左のサブツリーを描画します
• ルートノードの右側に正しいサブツリーを描画します

 def draw_node(root, x, y, block) return if root == nil block.call(root, x, y, x, y) draw_left(root.left, x, y, block) if root.left != nil draw_right(root.right, x, y, block) if root.right != nil end
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

左サブツリーの座標を計算するために、左サブツリーの右側にある子の数を計算します。 結果の数値は、x軸に沿った負の変位に使用します。 さらに、左および右のサブツリーに対してこのメ​​ソッドを再帰的に呼び出します。

 def draw_left(node, parent_x, parent_y, block) if node.right != nil count = 1 + children_count(node.right) else count = 0 end x = parent_x - @x_distance - (count*@x_distance) y = parent_y + @y_distance block.call(node.value, x, y, parent_x, parent_y) draw_left(node.left, x, y, block) if node.left != nil draw_right(node.right, x, y, block) if node.right != nil end
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

適切なサブツリーについては、同じことを行いますが、逆も同様です。

 def draw_right(node, parent_x, parent_y, block) if node.left != nil count = 1 + children_count(node.left) else count = 0 end x = parent_x + @x_distance + (count*@x_distance) y = parent_y + @y_distance block.call(node.value,x,y, parent_x, parent_y) draw_left(node.left, x, y, block) if node.left != nil draw_right(node.right, x, y, block) if node.right != nil end
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

walkメソッドのように、レンダリングのメソッドは実際には何も描画せず、オブジェクトの表示の座標のみを示します。 次の例は、コンソール内の座標を持つツリーの構築を示しています。

 require "binarytree" require "binarytreedrawer" tree = BinaryTree.new tree.add(100) tree.add(50) tree.add(150) tree.add(25) tree.add(75) tree.add(125) tree.add(175) drawer = BinaryTreeDrawer.new(tree) drawer.draw(0,0, Proc.new { |value, x, y, px, py| puts "Value #{value} at (#{x}, #{y})" }) => Value 100 at (0, 0) => Value 50 at (-40, 30) => Value 25 at (-60, 60) => Value 75 at (-20, 60) => Value 150 at (40, 30) => Value 125 at (20, 60) => Value 175 at (60, 60)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Webページにバイナリツリーをレンダリングする実際の例

座標があれば、グラフィックプログラムを使用してツリーを描画できます。 このWebアプリケーションでは、描画用のサーフェスとしてHTML 5 CanvasといくつかのJSメソッドを使用します。 以下は、JS呼び出しを生成してツリーを描画する方法の簡単な例です。

 drawer = BinaryTreeDrawer.new(@tree) drawer.draw(0, 0, Proc.new { |value, x, y, px, py| circles << "draw_circle(centerX + #{x}, offsetY + #{y}, 5);" lines << "draw_line(centerX + #{x}, offsetY + #{y}, centerX + #{px}, offsetY + #{py});" labels << "draw_label(centerX + 7 + #{x}, offsetY+5+#{y}, \"#{value}\");" })
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このコードは、JavaScriptメソッドの呼び出しで3つの配列（円、線、ラベル）を作成するだけです。 これらの配列は後でWebページに挿入され、クライアント側でツリーを描画します。

ソースコードとデモ

デモをご覧になりたい場合は、 http：//binarytree.heroku.comにアクセスして、ランダムデータでバイナリツリーを生成するか、独自のデータセットでバイナリツリーを描画できます。



バイナリツリーの実装に関するすべてのソースとデモサイトは、 GitHubに投稿されています 。