はじめに
この記事では、記事[ 1 ]で説明されている問題に対するバイナリ検索ツリーの実装を紹介します。 そこで説明されている問題では、「スイーピングライン」アルゴリズムが使用されます。このアルゴリズムには、ツリーのルートから子ノードおよびリーフに移動するだけでなく、リーフに沿って極端なリーフ（左または右）から移動できるバイナリツリーが必要です。 タスクは非常に単純に思えたので、私は長い間既製の実装を探し始めず、自分でやることに決めました。 同時に、彼は追加のタスクを設定しました-外部からツリーに新しいシートを追加するタスク。
理論のビット
理論はほとんどありません。 情報のほとんどは、ウィキペディアで入手できます[ 2 ]。 つまり、ストーリーの主題は、各要素が2つの子を持つことができるツリーのようなデータ構造です。 私の場合、[ 2 ]で設定されたタスクの結果である、正確に2つの子が存在します。 それ以外の場合、ノードはリーフになります。 彼には子供がいません。 ツリーに新しい要素を追加すると、値が最も近いシートに下降します。 見つかった葉は、1つの親と2つの子で構成されるツリーに置き換えられます。 親は、新しい要素とツリーで置き換えられた葉の値の算術平均に等しい値を受け取ります。 子-これは新しい要素であり、置き換えられたシートです。その位置（左または右）は、どの要素の値が低いかによって異なります。 値が小さいノードは左側にあります。 サブツリーを追加する場合、指定された3つの要素（親子関係）の間にリンクを追加/更新する必要があります。
上で述べた降下は、「より少なく、左右」の原則にも基づいて行われます。 ノードの値は、新しい要素の値と比較されます。 新しい値がノードの値よりも小さい場合は左に進み、そうでない場合（> =）右に移動します。 この仕組みについては、次のセクションで説明します。
その結果、互いに接続されたリーフとノードのソートされたセット（「親子」、「左」、「右」）を取得します。 次に、1つのシートから別のシート（右側または左側の隣のシート）への遷移を整理する必要があります。 私はこのロジックを最もいじらなければなりませんでした。 写真で説明することをお勧めします（次のセクションを参照）。
イラストのツリーロジック
アイテムを追加することから始めましょう。 ツリーが空の場合、新しい要素がルートになります。 それ以外の場合は、ノードの1つではなくサブツリーを作成します。 図 図1は、最初の2つの要素の追加を示しています。
図1.新しいアイテムを挿入する
ツリーがいっぱいになったら、たとえば左から右に葉を歩くことができます。 図 図2にツリーの例を示します。 黒い矢印は、あるシートから別のシート（右側の隣のシート）への移行を示します。
図2.「葉に沿った」遷移
葉を移動する機能が必要なのはなぜですか？ ボロノイ図を作成するタスクでは、ツリーの葉は「アーチ」に対応します。 3つのアーチの各シーケンスに対して、「サークルイベント」が発生する可能性があります。 したがって、アーチに沿って移動できる必要があります。 線形二重リンクリストのように、ツリーの葉で。 最初に、この機会を機能的な再帰によってのみ実装することにしました。 図からわかるように 2、最も困難な瞬間は「7-> 8」の形式の遷移でした。 再帰のみを使用する場合、「7」と「6.75」の間の永久サイクルに陥りました。 正しい子ではない最初の親（この場合、「7」から「6」への移行）に移行するサイクルを追加することで問題を解決しました。 右端のシート（「15」）から渡されると、前述のサイクルはツリー全体のルートにつながります。その後、Ruby表記で「nil」が取得され、右側の隣人の検索が終了します。
コード
ノードクラスはNodeです。
class Node attr_accessor :val, :parent, :left, :right def initialize( val, parent=nil, left=nil, right=nil) @val = val @parent, @left, @right = parent, left, right end def root? return @parent.! end def leaf? (@left || @right).! end def left? return true unless @parent if @parent.left return self.equal?(@parent.left) else return false end end def right? return true unless @parent if @parent.right return self.equal?(@parent.right) else return false end end def to_s res = "l:" if @left res << "#{@left.val.to_s} s:#{@val.to_s} r:" else res << "nil s:#{@val.to_s} r:" end if @right res << @right.val.to_s else res << "nil" end res end def Node.get_left_neighbour(node, up_dir = true) return nil unless curr if up_dir node = curr.parent if curr.right? return Node.get_left_neighbour(curr.left, false) if curr.left return Node.get_left_neighbour(node.left, false) else while node && node.left? node = node.parent end return node ? Node.get_left_neighbour(node.parent.left, false) : nil end else return curr if curr.leaf? return Node.get_left_neighbour(curr.left, false) unless curr.right return Node.get_left_neighbour(curr.right, false) end end def Node.get_right_neighbour(curr, up_dir = true) return nil unless curr if up_dir node = curr.parent if curr.left? return Node.get_right_neighbour(curr.right, false) if curr.right return Node.get_right_neighbour(node.right, false) else while node && node.right? node = node.parent end return node ? Node.get_right_neighbour(node.parent.right, false) : nil end else return curr if curr.leaf? return Node.get_right_neighbour(curr.right, false) unless curr.left return Node.get_right_neighbour(curr.left, false) end end end
" ：val ,: parent ,: left ,: right "-パブリックプロパティ。 したがって、ノードの値、その親へのリンク、および左右の子孫へのリンク。
" root？、leaf？ "-ノードがツリーまたはリーフのルートである場合、 "true"を返します。
" left？、right？ "-ノードが左または右の子の場合、 "true"を返します。
" to_s "-ノードとその子孫の文字列表現を返します。
" Node.get_left_neighbor（node、up_dir） and Node.get_right_neighbor（node、up_dir） "-現在のノードの左または右の隣人を返します。 なぜなら 関数は再帰的に呼び出され、パラメーター「 up_dir 」が存在します。 デフォルト値「true」は、ツリーを上に移動することを意味します。 ワークシートに対して呼び出される場合、このパラメーターにはデフォルト値が必要です。
ツリークラス「 BTree 」。
class BTree attr_accessor :root, :processor def initialize(root=nil, &processor) @root, @processor = nil, processor end def insert(val) unless @root @root = Node.new(val) else @processor.call(val, root) end self end def BTree.most_left(node) return node unless node.left return BTree.most_left(node.left) end def BTree.most_right(node) return node unless node.right return BTree.most_right(node.right) end def print_leafs iterator = BTree.most_left(@root) puts "Most left:", iterator.to_s until iterator.! iterator = Node.get_right_neighbour(iterator,true) puts format("Right neigh: %s", iterator.to_s) end end end
" ：root ,: processor "-パブリックプロパティ。 ツリーのルートと、ツリーに要素を挿入する手順への参照。
「 insert（val） 」は、バイナリツリーに値を挿入する手順のラッパー関数です。
" BTree.most_left（node）; BTree.most_right（node） "-ルートがパラメーターとして渡されたノードであるツリーの最後のシートを返す静的関数。
「 print_leafs 」-すべてのシートをコンソールに左から右に表示します。
木材の使用。
tree = BTree.new do |val, node| iterator = node until iterator.leaf? iterator = (val < iterator.val) ? iterator.left : iterator.right end if val < iterator.val iterator.left = Node.new(val) iterator.right = Node.new(iterator.val) else iterator.right = Node.new(val) iterator.left = Node.new(iterator.val) end iterator.val = (val + iterator.val)/2.0 iterator.left.parent, iterator.right.parent = iterator, iterator puts iterator.to_s end tree.insert(10).insert(1).insert(8).insert(7).insert(7.5).insert(5).insert(3).insert(15).insert(12).insert(11) tree.print_leafs
コードの最後のブロックでは、ツリーが作成され、ツリーに新しい値を挿入するプロシージャが作成されます。 最後の2行は、ツリーに値を連続して挿入し、葉を印刷します。 すべてが単純なようです。
おわりに
もちろん、コードは未加工ですが、動作します。 将来的にWPFを使用してツリーを描画できるように、プラットフォーム.Net + DLR（IronRuby）で作成しました。 このコードは、純粋なRubyとSilverlightの両方に簡単に移植できると思います。
ネットワークにはおそらく同様の実装が多数ありますが、ボロノイ図に関するシリーズの中で、実装を提示することにしました。 さらに、ツリーのロジックは特定のタスクに適合しています。 後で他の人の落とし穴につまずかないように、実際にアルゴリズム[ 1 ]の個々の瞬間を実際に自分で確認することが重要です。
ご清聴ありがとうございました！ あなたのコメント...
参照資料
1. 動き「ボロノイ」
2. バイナリツリー