Posted by どうも。
最近やりたいことが多くて困ってます。OYです。
早速ですがタイトルの2分探索木を紹介しようかと。説明といっても全容を明かすと流石に文字数なのであんま厳密な説明をする気はないです。いちおう遊びレベルで軽くノードのモデル、ツリーモデル、探索メソッドだけ書いたので最後に添付します。（ささっと書いただけなのであんま石投げないでくださいな）
2分探索木ってそもそもなんぞや
2分木というデータ構造の派生で、高速にデータを探すことができます。
どんな構造しとるんや
基本的には2分木と同じで最大2つに枝分かれしている木構造なんですが、各ノードが
・キーとなる値と実データを保持している
・枝分かれの右側はキーとなる値が大きい
・枝分かれの左側はキーとなる値が小さい
という特徴を持っています。
構造は分かったけどなんでそれで高速に探索できるんや
ここから先はアルゴリズムの話になります。O記法みたいなのは人によってはかえって分かりづらくなるかもなのであえて使わないです。
まず、2分探索木の探索アルゴリズムは下記の手順となります。
- キーを入力する。
- (最初は根)ノードのキー値と入力キーを比較する。
- 入力の方が大きければポインタ(現在指しているノード)を右へ、小さければ左へ移動する。キー値が一致すれば実データを、それ以上探索できない場合はNIL(null)を返却。
- キー値が一致するか移動先がなくなるまで2と3を繰り返す。
つまり、右か左かの選択を行うたびに選択しなかった方のノード分だけ探索にかかるコストが削減されます。(ここが重要)
アルゴリズムの世界では最悪実行時間(最悪のケースでどれだけ時間がかかるか)という概念があります。例えばサイズnの単純な配列の中から特定のデータを探すには最悪a*n回のステップを要します。(aは定数)
では、2分探索木で、先ほど説明した手順で、あるデータを探すのにかかる最悪実行時間はどのようになるのでしょうか。
・・・
答えは、木の高さによります。
木が一切2分していない場合は先の例で挙げた単純な配列とほとんど何も変わらずa*n回のステップを要しますが、木が完全に2分している(＝高さが最小)場合はa*log2(n)程度のステップで済みます。(aは定数)
これがどのくらいの差をもたらすかといいますと、例えばn=10億の場合、10億=1000^3≒2^30より、log2(10億)は大体30くらいとなります。
ようするに、木をほぼ完全に2分させるような挿入が実現できさえすれば圧倒的に高速な探索が実現できるようになるわけです。すごいですねー
説明はここまでにしようかなと。興味を持った方は2色木とかいろいろ調べてみると面白いですよ。
おまけ：探索とかのソース（javaファイル添付できないっぽいんでソースそのまんまぺたり。読みにくいのでコピペするなりしてください。あとキーとか実データの型とかはなんでもいいです。）
import java.util.Comparator;
import lombok.Data;
@Data
public class BinaryTree {
public BinaryTree(){
this.root = null;
}
/**比較関数を設定する場合のコンストラクタ（まあKeyがIntegerならまず不要）*/
public BinaryTree(Comparator<Integer> comparator){
this();
this.comparator = comparator;
}
/**根ノード*/
protected Node<Integer,String> root;
/**独自な比較関数（まあKeyがIntegerならまず不要）*/
protected Comparator<Integer> comparator;
/**
* 二分木を探索し、入力キーに紐づけられた実データを返却する
*
* @param キーとなる値
* @return 実データ、またはnull(見つからなかった場合)
*/
public String search(Integer point){
Node<Integer,String> current = root;
while(current != null){
//入力値が現在のポインタが示す値と一致する場合
if(point == current.getPoint()){
return current.getData();//実データ返却
//入力値が現在のポインタが示す値より大きい場合
}else if(point<current.getPoint()){
current = current.getLeft();//ポインタを左へ
//入力値が現在のポインタが示す値より小さい場合
}else{
current = current.getRight();//ポインタを右へ
}
}
return null;//探索し終わっても値が見つからなかった場合null返却
}
@Data
public static class Node<Integer,String>{
public Node(Integer point, String data, Node<Integer,String> left, Node<Integer,String> right){
this.point = point;
this.data = data;
this.left = left;
this.right = right;
}
/**こいつが格納してる数値*/
protected Integer point;
protected Node<Integer,String> left;
protected Node<Integer,String> right;
/**実データ*/
protected String data;
}
}