私は、主に平面ツリー構造のアイテムのインデックスとして使用する特定のデータ構造で多くの作業を行ってきました。これは、配列内のインデックスに等しい「深さ」にあると見なされる正の整数(またはバイトまたはロングなど)の配列で構成されます。この配列ベースのデータ構造に名前がありますか?
ツリー内のインデックスと考えると、ツリーのルートはインデックスとして空の配列を持ち、インデックスが{a, b... c}
のノードのN番目のサブノードはインデックス{a, b... c, N}
です。
一般的な操作では、配列の最後の数字を増減したり、前面または背面からいくつかの要素を削除したり、いくつかの要素を前面または背面に追加したりします。ツリーインデックスコンテキストでは、これらは、兄弟ノードを通って前方/後方に進むこと、サブツリー内のインデックスを見つけること、または親ノードのインデックスを見つけること、ツリーのルートが別のツリーに張り付いているときにインデックスを見つけること、それぞれ子孫ノードである。
私は最初にそれらをインデックスとして使用しましたが、データのシリアライズの高速化からコードを読みやすくするための新しい方法を発見し続けています。これは私には不思議に思っています、このデータ構造やそれ以外の場所で一般に使用されているようなものですか?もしそうなら、それは名前を持っていますか?私はこれで他に何ができるか見ることに興味があります。
(読みやすいものを維持するために取り残さエラーチェックとC#でのサンプル実装、)
class TreeIndex
{
public readonly int depth
{
get
{
return widths.Length;
}
}
public readonly int[] widths;
public TreeIndex()
{
widths = new int[0];
}
public TreeIndex(params int[] indices)
{
widths = indices;
}
public static implicit operator int(TagIndex ti)
{
return ti[ti.depth - 1];
}
public static operator TagIndex +(TagIndex ti, int i)
{
int[] newwidths = ti.widths.Clone();
newwidths[newwidths.Length - 1] += i;
return new TagIndex(newwidths);
}
public static operator TagIndex -(TagIndex ti, int i) { return ti + (-i); }
public static operator TagIndex <<(TagIndex ti, int i)
{
int[] newwidths = new int[ti.depth - i];
Array.Copy(ti.widths, newwidths, ti.depth - i);
return new TagIndex(newwidths);
}
public static operator TagIndex >>(TagIndex ti, int i)
{
int newwidths = new int[ti.depth - i];
Array.Copy(ti.widths, i, newwidths, 0, ti.depth - i);
return new TagIndex(newwidths);
}
public static operator TagIndex ^(TagIndex tia, TagIndex tib)
{
int newwidths = new int[tia.depth + tib.depth];
Array.Copy(tia.widths, newwidths, tia.depth);
Array.Copy(tib.widths, 0, newwidths, tia.depth, tib.depth);
return new TagIndex(newwidths);
}
}
データ構造としてオーバーロードされた演算子と特定のユースケースにもかかわらず、これは単なるリストです。 – user2357112
そうですか?私が考えている別個のデータ構造を構成するものが本当に明確ではない。私はコンテンツだけではなくオペレーションの観点からそれらを定義するようないくつかの同様の質問を見ましたが、これは間違っていますか? –