ハッシュバイナリツリーのJava実装

私の友人は、プログラマーが次の2つの理由で行くと言います（これらが彼の言葉なのか、どこかに持っているのかわかりません）。ハッカーになりたいのか、ゲームを書きたいのか。 2番目のケース。 私は常にゲームの開発と、ゲームの人工知能を担当する部分に興味がありました。 私はパス検索アルゴリズムの研究に多くの時間を費やしました。 JavaでA *アルゴリズムの次のバージョンを実装すると、TreeSetおよびTreeMapコレクションに関連する興味深い状況に遭遇しました。

この記事全体で使用する2つの概念、つまり、平等の検索と比較の検索をすぐに紹介したいと思います。 等価検索とは、 equals メソッドとhashCodeメソッドを使用して要素を比較するコレクション内の検索を指します。 比較による検索、または比較に基づく検索、コレクション内の要素の検索を呼び出します。ここでは、メソッドcompareおよびcompareToを使用して要素を比較します。

A *アルゴリズムは2つのコレクションを使用して、ウェイポイントを保存します： オープンリストとクローズリスト 。 大まかに言って、ウェイポイントには3つの重要な属性があります：X座標、Y座標、およびメトリック関数の値-F。閉じたリストの場合、追加と検索の2つの操作のみを実行する必要があります。 リストを開くと、事態はもう少し複雑になります。 開いたリストでは、要素の追加と検索の操作に加えて、メトリック関数の値によって最小のポイントを見つける必要もあります。

閉じたリストの場合は、 HashSetを選択します。ここではすべてが明らかです。追加および検索操作の場合は、適切なハッシュ関数を作成しておくと便利です。 オープンリストのコレクションを選択するのは困難です。 閉じたリストのようにHashSetを選択すると、挿入、検索、削除の操作に対して最適な漸近的な動作が得られます-O（1）、ただし、最小の検索はO（n）で実行されます。 TreeSetまたはTreeMapを選択すると、挿入と検索にO（log（n））が使用されますが、最小値の検索と削除にはすべて同じO（log（n））が使用されます。 ここでさまざまなコレクションの漸近を参照してください。

TreeMapとTreeSetに関連するもう1つの重要な詳細は、これらのコレクションでのすべての操作が比較を使用することです。 したがって、ポイントの座標を考慮して検索に関心がある場合、最小値を見つけるためにメトリック関数の値を使用します。これにより、この値が変更されたポイントに対して操作が実行されない可能性があるという事実につながります。 さらに、新しい値を挿入すると、誤って構築されたツリーを取得できます。同じ座標を持つポイントを比較し、これをコンパレータで考慮すると、ツリーに新しい値を挿入することはできません。

検索アルゴリズムの各反復でメトリック関数の値による最小要素の検索が実行される一方で、要素はオープンリストにそれほど頻繁に追加されないため、バイナリツリーに基づくコレクションを使用することは理にかなっています。 これは、オープンリストへの追加がクローズドリスト内の同様の（座標内の）要素の存在に依存するという事実によるものです。この要素は時間とともに成長し、その中にポイントが増えますリスト。 しかし、 HashSetコレクションの利点も持ちたいです。

タスクを一般化することにしました。 一連のフィールドがあるデータ構造を定義します。 また、特定の構造の2つの要素の等価関係を決定するフィールドもあれば、順序関係を決定するフィールドもあります（言い換えると、equalsメソッドとhashCodeメソッドはオブジェクトの同じフィールドを使用し、compareメソッドとcompareToメソッドは他方を使用します）。
目的： O（1）の漸近的な振る舞いで等式に基づいて要素を検索する操作が実行されるデータ構造を実装し、操作と比較と等式を考慮して挿入と削除の操作を実行し、最小要素が木の根になるように二分木を構築する。

私の目的のために、座標を考慮してポイントをオープンリストに保存する必要があるため、衝突が発生しないように、開通性マップのサイズに基づいてハッシュ関数を一意に決定できるため、コレクション内の要素の最大数を定数として設定することにしました。



考え方は非常に簡単です。コレクションの要素をハッシュに基づいて配列に入れ、すぐに同じ要素をバイナリツリーに入れます。 要素をツリーノードにパックするには、内部クラスが必要です。

private static class Node<V extends Comparable<V>> { private Node parent; private Node left; private Node right; private int k = 0; private final V data; public Node(V data) { this.data = data; this.parent = null; this.left = null; this.right = null; } } 

タイプVはコレクションの要素を定義し、Comparableクラスを拡張して、ツリーを構築するために比較できるようにする必要があります。

クラスには、左右の子孫へのポインタに加えて、先祖へのポインタがあります。 これは、ツリーから要素を削除するプロセスを最適化するために行われます-削除された要素の前駆体は、ルートからツリーをバイパスして削除アルゴリズムから除外でき、要素の配列を使用して検索できます。 名前がkのフィールドには、サブツリーノードが左の子で連続して増加するノードでない場合、その数が含まれます。


コレクション内には、ツリーのルートへのポインタとコレクションの要素の配列があり、空のセルと、追加された要素の値（またはオブジェクトインスタンスへのポインタの値）がデータフィールドに格納されるNodeクラスのインスタンスに格納されます。

 public abstract class HashTree<E extends Comparable<E>> { private Node root = null; private Node[] nodes; public HashTree(int capacity) { this.nodes = new Node[capacity]; } public abstract int getElementHash(E element); … } 

タイプVと同様に、 タイプEはコレクションアイテムを定義します。 デフォルトでは、コレクションは空なので、ルート要素へのポインターはnullであり、配列もnull値で埋められます 。 ハッシュコードの計算をオーバーライドできる抽象getElementHashメソッドを持つ抽象クラス。

次にメソッドに移ります。 AddElementメソッド：

 public void addElement(E element) { int index = getElementHash(element); if (nodes[index] != null) { return; } Node<E> node = new Node<>(element); nodes[index] = node; this.root = connectNodes(this.root, node); } 

このメソッドでは、追加する要素のハッシュコードを取得します。 データとして新しい要素を持つ新しいツリーノードを作成し、それをツリーと配列に追加します。ハッシュコードは配列のインデックスを定義します。 配列への要素の挿入には漸近線O（1）があり、ツリーへの挿入にはO（対数（n））があり、全漸近線はO（対数（n））です。

RemoveElementメソッド：

 public E removeElement(E element) { int index = getElementHash(element); Node node = nodes[index]; if (node == null) { return null; } nodes[index] = null; E data = (E) node.data; Node l = getElemInArray(node.left); Node r = getElemInArray(node.right); if (l != null) { l.parent = null; } if (r != null) { r.parent = null; } l = connectNodes(l, r); if (node.parent == null) { this.root = l; if (this.root != null) { this.root.parent = null; } return data; } int p = getElementHash((E) node.parent.data); if (nodes[p] != null) {//    , //   ,    if (nodes[p].left == node) { nodes[p].left = null; } if (nodes[p].right == node) { nodes[p].right = null; } } connectNodes(nodes[p], l); return data; } 

ここでは、削除する要素のハッシュコードを使用して、削除するツリーのノードを配列から抽出します。 削除するノードの祖先を使用して、要素を削除します。その間、サブツリーを2回呼び出す必要があり、最悪の場合の各操作は漸近的な動作-O（log（n））を持ちます。 結果として、メソッドには漸近線O（log（n））があります。

connectNodesメソッドは、単一のノードとサブツリーの両方を結合します。 さらに、バインディングは比較を使用して行われます。 したがって、最小の要素は常にツリーの最上部にあります。

ConnectNodesメソッド：

 private Node connectNodes(Node parent, Node node) { if (node == null) { return parent; } if (parent == null) { return node; } else { if (compare(node, parent) < 0) { return connectNodes(node, parent); } Node cur = parent; Node n = node; while (cur != null) { if (cur.left == null) { cur.left = n; n.parent = cur; cur.k++; break; } if (cur.right == null) { if (compare(n, cur.left) <= 0) { cur.right = cur.left; cur.left = n; n.parent = cur; cur.k++; break; } else { cur.right = n; n.parent = cur; cur.k++; break; } } if (compare(n, cur.left) <= 0) { Node tmp = cur.left; cur.left = n; n.parent = cur; cur.k++; cur = n; n = tmp; continue; } if (compare(n, cur.right) < 0 && compare(n, cur.left) > 0) { cur.k++; if (cur.right.k < cur.left.k) { Node tmp = cur.right; cur.right = n; n.parent = cur; cur = n; n = tmp; } else { cur = cur.left; } continue; } if (compare(n, cur.left) > 0) { cur.k++; cur = cur.left.k < cur.right.k ? cur.left : cur.right; } } return parent; } 

connectNodesメソッドには特別な注意を払う必要があります。 新しい要素の追加は、ルートおよび新しい要素に関連してこのメ​​ソッドを使用して実行されます。 ツリーは空ではないと考えます。


4つのケースが考えられます。

1. 新しい要素はルートよりも小さい。
2. 新しいアイテムは左の子よりも小さいです。
3. 新しい要素は左の子孫よりも大きいが、右の子よりも小さい。
4. 新しいアイテムは右の子よりも大きくなります。

事例1
この状況では、親が新しい要素の左の子になり、親がツリーのルートである場合、新しい追加された要素はそれぞれ新しいルートになります。


事例2
次の2つのオプションがあります。右の子が定義され、右の子が定義されていません。 左の子孫が定義されていない場合、左の子孫は新しいノードにとってより重要であると見なされます。 どちらの場合も、新しい要素は親の左の子になり、左（追加する前は左の子でした​​）が右の子になります。 ただし、2番目のケースでは、古い右の子孫の右を新しい右の子孫の左に結合する必要があります。 左から右への結合は、説明した場合と同じ規則に従って行われます。


事例3
この場合、右側のサブツリーよりもノードが少ない場合、左側のサブツリーを移動して新しいノードを追加するか、右側のサブツリーの右側を挿入したノードノードに置き換えて右側のサブツリーの右側を追加します。


事例4
この場合、ノードが少ないサブツリーに沿って遷移が実行されます。 ノードの数は、フィールドkに蓄積されます。


次に、 connectNodesメソッドの漸近的な動作を推定します 。 最良の場合、子孫のないノードが降順でツリーに追加されると、漸近線はO（1）になります。この場合、新しい要素を祖父母の代わりに配置するからです。 ノードを子孫に関連付け、先祖よりも小さくすることについて話している場合は、ノードのサブツリーを調べる必要があります。 ケース2の場合、パラグラフa）では漸近的動作はO（1）であり、パラグラフb）では、挿入されたノードのサブツリーを再度通過する必要があります。
ノードのフィールドkは、1番目以外のすべての場合に増加することに注意してください。これは、ツリーが対称的に満たされるように行われますが、左サブツリーの昇順に違反することはありません。

ツリーを通る通路の複雑さを評価するには、その高さを評価するだけで十分です。 ツリーの高さは、目的の漸近的な動作になります。 別の問題は、左側のサブツリー上のシーケンスの長さの存在です。 そのようなサブツリーの存在を考慮すると、最悪の場合、バインディングの漸近的挙動は、バインドしたいサブツリーとのバインディングの漸近的挙動と考えることができ、最良の場合はO（1）（2の場合）となります。


ノードを接続するとき、ツリー内のノードを扱うため、サブツリーの高さはツリー自体の高さを超えないと見なすことができます。 したがって、バイナリツリー全体の高さを推定したら、connectNodesメソッドの漸近的な動作を取得します。 挿入するサブツリーの選択は、ノードのフィールドk （連続的に増加するノードを除いてサブツリーのサイズを格納し、1つのノードとしてカウントされます）に基づいて選択されるという事実により、ツリーは前のノードを埋めた後にのみ次のレベルを埋める傾向があります（もちろん例外です）上記の場合1）。 したがって、ツリーは次のようになります。


したがって、nがツリー内のノードの数である場合、 $$$n = \ sum_ {i = 0} ^ h 2 ^ i$。 それから、木の高さ $$$h = \ log_ {2}（n + 1）-1$。 したがって、 connectNodesメソッドの漸近的な動作はO（log（n））です。

要素はツリーではなく、ハッシュコードに基づいた配列で検索できるため、検索操作には漸近O（1）が含まれます。 また、ツリーはバイナリとして編成されているため、ルートには常に最小要素が含まれており、最小値の検索の漸近的動作はO（1）です。 最小要素の削除には漸近線O（log（n））があることに注意してください。これは、 connectNodesメソッドを使用してルートから開始してツリーを再編成する必要があるためです。

一見、実装されたコレクション内の最小要素を削除する操作は、 HashSetコレクションよりも漸近性が悪くなりますが、最小要素を削除する前に最初に見つける必要があることを忘れないでください。このためには、漸近線O（n）で操作を実行する必要があります。 したがって、HashSetコレクションの最小要素を削除する操作の最終的な漸近的な動作は、-O（n）という形式になります。

前述のように、コレクション内の要素の存在の確認は、要素のハッシュコードによって決定されたインデックスにある配列の要素のnullの確認に基づいて実行されます 。 検証は、 containsメソッドによって実行され、O（1）の漸近的な動作をします。

 public boolean contains(E element) { int index = getElementHash(element); return nodes[index] != null; } 

また、ハッシュコードに基づいて、 getElementメソッドを使用して、同じ漸近線で同じかどうかが同時に検索されます。

 public E getElement(E element) { return (E) nodes[getElementHash(element)].data; } 

実装されたコレクションには欠陥がないわけではありません。 より多くのメモリが必要であり、衝突のないハッシュ関数が必要です。また、要素の列挙を実装するにはツリートラバーサルを実装する必要がありますが、これも楽しみではありませんが、このコレクションは他の目的を対象としています。 主な利点は、最適な漸近性を使用して、異なる基準に従って同じタイプの要素を検索できることです。 私のタスクに適用されたように、それは座標に基づいた平等の検索と、メトリック関数の値の比較に基づいた最小要素の検索でした。

最後に、 LinkedHashMap 、 TreeSet、およびHashSetコレクションと比較したパフォーマンスのコレクションのテスト結果を示します。 すべてのコレクションには、 整数型の1000個の値が入力され、入力されたコレクションでは、次の一連の操作が実行されました。

1. コレクションに新しいアイテムを配置します。
2. コレクション内の特定の値を持つ要素の存在を確認します（チェックは、コレクション内にある要素とコレクション内にない要素に対して2回実行されました）。
3. 要素を比較することによる検索と削除は最小限です。
4. パラグラフ1で追加されたアイテムの削除。

テスト結果を表に示します。

収集	繰り返し回数	費やした時間
LinkedHashMap	10,000,000	1985±90ミリ秒
ツリーセット	10,000,000	1190±25ミリ秒
ハッシュセット	1,000,000	4350±100ミリ秒
ハッシュツリー	10,000,000	935±25ミリ秒

その結果、 LinkedHashMapに比べてHashTreeコレクションの速度が2倍以上高く、 TreeSetに比べて1.27倍高速です （ HashSetを考慮することはまったく意味がありません）。 このチェックは、4GBのRAMとAMD Phenom（tm）II X4 940プロセッサー、OS-32ビットWindows7 Professionalを搭載したマシンで実行されました。