五分木探索は可能ですか

Question

アルゴリズムとかあまり良くわかっていない初心者です。

普通、二分木探索といえば”値”と”値”を比較して、

左に、値が小さいもの
右に、値が大きいもの

を置くと思うのですが、今、例えば時間のような”範囲”と”範囲”を比較たくて、

左に、　　　　”範囲１”が完全に”範囲２”より左にあるもの
左真ん中に、　重なっていて”範囲１”が”範囲２”よりちょっと左に出ているもの
真ん中に、　　完全に”範囲１”と”範囲２”が覆いかぶさっているもの
右真ん中に、　重なっていて”範囲１”が”範囲２”よりちょっと右に出ているもの
右に、　　　　”範囲１”が完全に”範囲２”より右にあるもの

というように五分木みたいにすることは可能ですか？

###補足
######探索する関数
戻り値：空
引数：リスト（そのリストに、範囲を追加していく）、ある値（時刻など）または　ある範囲（時間など）（範囲の始まりと終わりの値を引数にする）
※範囲や値は一つの数直線上にあるものとします
内容：
・引数の値（時刻など）を含む”範囲”を引数のリストに追加
・引数の範囲（など）を含む”範囲”をリストに追加

というようなものを作りたいです。

Comments

[Zuishin]

可能か不可能かで言えば可能ですが、意味のある木にはならないと思います。

[raccy]

五分とは限らないけどB木のこと？

[hayataka2049]

可能ですが……何ですか？（接続助詞でタイトルが終わっています）

[rimokonTenko_mo]

@rrccy B木を知らなかったので、調べてみました。多分、それだと思います。ありがとうございました。

[rimokonTenko_mo]

@hayataka2049「が」→「か」の間違いでした。直しておきます。

[raccy]

質問を見直してみましたが、やりたいことがB木とは違う気がします。B木も二分木と同じで単純な大小比較可能なものが対象だからです。

最終的に「何を探索したい」のかです。より具体的な例を出して、どういうモノを探索したいかを書いてください。「ある値を含む範囲の内、その範囲が最も狭く、同じ狭さなら最小値が小さいもの」というように探索で求めるもの具体性がないと適したアルゴリズムであるのかどうかすら判断できません。

[rimokonTenko_mo]

すみませんでした。探索したいものや方法を追記しました。

[Zuishin]

自分専用の覚書ではなく、他人が読んでわかるように書いてください。

[Zuishin]

わかりました。
https://teratail.com/questions/220365
の続きですね。

ここで私が書いた案は、一日で終わる予定が多すぎて使い物にならなかったので忘れてください。

[rimokonTenko_mo]

それに関して、予定が重ならないようにして、始まる時間だけで、比較するようにしました。また、予定の取得は、ArrayListを始まる時間が順番になるように予定を入れて、直接インデックスを2で割っていく二分探索にしました。そして、範囲の始まりと終わりを求められるようにインデックスを返すようにしました。

Answer 1

勝手用語をタイトルにつけても適切な回答はつかない気がします

左に、　　　　”範囲１”が完全に”範囲２”より左にあるもの

左真ん中に、　重なっていて”範囲１”が”範囲２”よりちょっと左に出ているもの
真ん中に、　　完全に”範囲１”と”範囲２”が覆いかぶさっているもの
右真ん中に、　重なっていて”範囲１”が”範囲２”よりちょっと右に出ているもの
右に、　　　　”範囲１”が完全に”範囲２”より右にあるもの

提示された範囲では、単純に条件を比較して、分類するだけなので、どのように組んでも良いです。
考え方やサンプルはご自身が示したとおり「時間の範囲比較」で検索すると色々出てきます。
数直線上の比較であれば、なんの言語でも実装は容易なので、実装後不明点を再整理し質問し直したほうが知りたいことに対してピンポイントな回答がつくかと思います。

Comments

[rimokonTenko_mo]

また調べて考えてみます。ありがとうございました。