Python でデータ構造の木について

疑問 1. Node class と Tree class をそれぞれ個別に定義するか、それとも Tree class でのみで定義するか。

結論:Tree class でのみで定義するべき。

ほとんどの初心者向けのサンプルコードは Tree class のみでの実装である。初心者向けじゃないコードは読んだことがない..使い分けみたいなのがあったりするのだろうか。いまいちよくわからない。

学生時代にも地味に疑問に思っていたけど、木とかめんどくさいしと思ってあまり深く考えたことなかった...

木クラスとノードクラスを分ける実装
How can I implement a tree in Python? Are there any built in data structures in Python like in Java?

◯ Tree class のみだった場合の懸念: 木の属性を保存できない。

例えば、木に名前をつけたいとか、木の最大の深さを定義したり、木に含まれる要素数、木の要素の最大の値を保存するような場合である。

木の最大の深さを定義するのは、木の高さを定義するのと同等である。なので、最初に木の高さをノードに与えてやれば良い。木の高さが 0 になったら、木が葉に達したと判断すれば良い。

self.child_tree = Tree(height= self.height - 1)

木に含まれる要素数、木の要素の最大の値を保存するなら、大抵木の更新に合わせて、この手の値も更新が必要になるので各ノードごとに再帰的に下位側の値を計算、保存しておけばい良い。

node class と tree class を分けたところでメリットはない。

名前のような木全体で共通の属性をつけたいのなら、分割したクラスが必要かもしれないが...

◯ Tree と Node class を分けた場合の懸念:処理が複雑になる。

1)クラスが増えることである。stackoverflow の記事は tree と node を分けた実装が記されている。

2)読むとわかるがdef method(self, node, ...)というように self に加えて node を引数に与えないとならない。これが若干可読性を下げている。

特に self を引数に持つのに self を使わない、冗長な引数を取得してしまっている。これが違和感の原因にもなっている。

◯ まとめ

色々考えたけど、よほど大規模なものを作らない限り、木は tree class と node class として分ける必要はないのかなと。

疑問 2. クラス名は Node class か Tree class か

答え: Tree class

なぜなら method で insert やら delete を tree に対して定義しているから。ある特定の node にだけに対して insert したり、あるいは delete しているわけではない。

疑問 3. 変数名は tree か root か

答え: tree だ。

# x
root = Tree()

#o
tree = Tree()

たまに C サンプルコードでこう言うコードを見かける。

static struct node *root = NULL;

ルートのポインタという表現である。これが結構誤解の元で、確かに見ようによっては 要素 root <= 集合 node だけど。root を根に持つ Tree 要素 <= Tree 集合でもある。したがって、 root は木として扱える。木へのポインタとして表現してもらえれば理解を妨げなかったか。

static struct node *tree = NULL;

◯ list について

同様なことが list でも言えるか.. list と node のクラスを分けるかどうかでも... ノード node としての根 root への参照は、表現としては間違っていないが、木 tree として変数にもたせた方が可読性が良いのではないだろうか。