2-3木を実装した - プログラマーのメモ書き

ボチボチこちらの『データ構造とアルゴリズム』を読んでるところです。

作者:杉原厚吉
共立出版

時間を見つけては興味のある内容を実装したりして遊んでます。で、今回は、平面走査法を実装してみたいなと思い立ち、まずはここで紹介されていた探索木の一つである 2-3木を実装してみました。

個人的には、実装していくだけでも十分楽しいんですが、それだけだと、アルゴリズムの本見たり、ネットを漁れば（最近だと ChatGPT に聞けば）いいだけの話なので、ここではそのあたりは深く触れず、実装時にやってみた Python の単体テストとか、木の可視化などについてを主にメモしておきます。

なお、実装時の環境は以下の通りでした。

WIndows 11 22H2 上の WSL2, Ubuntu 22.04.2
Python 3.11.4

こちらの記事のように Windows 上の VSCode から WSL にリモート接続して開発してます。

実装について

とはいえ、実装時に気になったところもあったので、それらについて簡単にメモっときます。

前述の本を参考に実装していったのですが、実際にコードを書いてみると困った点としては、

2-3 木の定義として、葉以外のノード（節点）は 2 つまたは 3 つの子要素を持っている
しかし、木を作成する際に、一つ目の葉を追加したときは、根の要素に対して、追加前は子要素が 0 個、追加後が 1 個
同様に、木を作成する際に、二つ目の葉を追加したときは、根の要素に対して、追加前は子要素が 1 個、追加後が 2 個

となるため、この部分だけを例外的に扱う必要がありました。まあ、考えてみれば葉が 1 個という状態もありえるんだから、考慮する必要があるのは当たり前ですよね。

あと、困ったというわけではないのですが、紹介されていたアルゴリズムでは、ある中間のノードは、

左側のサブツリー内のキーの最大値
中央のサブツリー内のキーの最大値

を持つとしていたのですが、値を直接持つと、先々平面走査法で扱う時にちょっと困りそうな印象があります（キーとして交点の座標を持つ必要があり、それが変化していくため）。なので、この部分をキーの最大値を直接持つのではなく、キーの最大値を持つノードへの参照を持つように変えてみました。

実装に興味がある方は、 GitHub にコードをアップしているのでそちらを参考にしてください。

単体テスト

久しぶりに Python でまとまったコードを書いてみたので、単体テストも作ってみました。まあ、厳密にはメソッド単位でのテストになっていないので単体テストか？という疑問がつく内容ですが、 2-3 木のクラスをテストする、という意味でここでは単体テストと呼んでます。

Python の単体テストは、下記などの記事を参考にして作ってみました。 unittest という標準モジュールを使えば、簡単にテストが作れるとのことです。

プロジェクトのフォルダの下に test というフォルダを作り、その中に test を定義するファイルを作成しています。

テストの作成

まず、今回作った 2-3 木のモジュール (TwoThreeTree.py) を使う際には、葉の要素がキーとなるオブジェクトを保持する形をとる際に、葉のクラスの派生クラスを作る形を想定しているため、そのための定義を test/TestClasses.py にまとめています。

from dataclasses import dataclass
import math
from TwoThreeTree import Leaf, Node

# テスト用の Node 要素
@dataclass
class NodeForTest:
    id: str     # id
    key: float  # キー

class MyLeaf(Leaf[NodeForTest]):

    def __init__(self, val: NodeForTest, parent: Node[NodeForTest] | None):
        super().__init__(val, parent, get_key, comp_key)

def get_key(v: NodeForTest) -> float:
    return v.key
def comp_key(v1: NodeForTest, v2: NodeForTest) -> int:
    if math.isclose(v1.key, v2.key):
        return 0
    if v1.key < v2.key:
        return -1
    else:
        return 1    
def myleaf_ctor(v: NodeForTest, parent: Node[NodeForTest]):
    return MyLeaf(v, parent)

で、このクラスを使う形で、テストを書いていきます。

テストは、 test_*.py のような名前のファイルに書く必要があります。たとえば、一般的な 2-3 木の操作に関するテストを test_TwoThreeTest_general.py というファイル名で作成します。

from dataclasses import dataclass
import unittest
from TwoThreeTree import Leaf, Node, TwoThreeTree
from test.TestClasses import MyLeaf, NodeForTest, comp_key, get_key, myleaf_ctor

class TestTwoThreeTree(unittest.TestCase):
    """典型的な 2-3 木に関するテスト
    """

    @classmethod
    def setUpClass(cls):
        print("2-3 tree test setup")

        # 2-3木を作成してテスト
        cls.tht: TwoThreeTree = TwoThreeTree[MyLeaf, NodeForTest](get_key, comp_key, myleaf_ctor)

    @classmethod
    def tearDownClass(cls):
        pass

    def test_create_tree_1(self):
        TestTwoThreeTree.tht.insert(NodeForTest("01", 2.0))

        self.assertEqual(2, TestTwoThreeTree.tht.size)
        self.assertEqual(1, TestTwoThreeTree.tht.leafSize)
        self.assertEqual(2, TestTwoThreeTree.tht.height)
（後略）

こんな感じです。

まず、 unittest.TestCase を継承したクラスを作ります。この中の、 test_* のような名前のメソッド一つ一つがテストになります。テストはメソッド名のアルファベット順に実行されます。

テスト前に実行したい処理およびテスト後に実行したい処理は

setup / tesrDown
setUpClass / tearDownClass

に記述します。

前者の 2 つのメソッドは、テストメソッドが呼ばれる前後に毎回呼ばれます。一方、後者のメソッドは、クラスメソッドで、上記のクラス全体で最初と最後の一度だけ呼ばれる形になります。

上記の例だと、何もない 2-3 木に順番に葉の追加を行って、その結果を確認したいので、クラスメソッドを利用しています。

テストメソッド内で、対象となる処理を行ったあと、確認したい内容を assertEqual というメソッドで比較していきます。上記の例だと、

2-3 木の総ノード数（size）
葉の数（leafSize）
木の高さ（hheight）

を確認しています。テストによっては確認する内容は変わると思いますが、 assertxxxx というメソッドがいろいろと用意されているので、それらを使ってテストを組み立て行きます。

結構簡単ですね。

テストの実行

テストを実行するには、コマンドラインから実行します。

(.venv) mor@DESKTOP-DE7IL4F:~/tmp$ python -m unittest test/test_TwoThreeTree_general.py 
2-3 tree test setup
................
----------------------------------------------------------------------
Ran 16 tests in 0.001s

OK
(.venv) mor@DESKTOP-DE7IL4F:~/tmp$

問題がなければ、こんな感じに OK と表示されます。

ただ、これだと、テスト数が増えてくるといちいちコマンドラインで実行するのが大変になってきます。同じことを VSCode からやるには、

VSCodeとpytestでPythonコードをテスト&デバッグする｜CO-WRITE

などを参考にして、構成を行ってやります（構成方法はリンク先の記事を参考にしてください）。なお、参考までに、設定後の .settings.json は

{
    "python.testing.unittestArgs": [
        "-v",
        "-s",
        "./test",
        "-p",
        "test_*.py"
    ],
    "python.testing.pytestEnabled": false,
    "python.testing.unittestEnabled": true
}

となってました。

問題なく構成ができたのち、 VSCode のフラスコのアイコンを選択すると、

のようにテストが一覧で表示されます。

で、テストにカーソルを合わせると

のように『テストの実行』アイコンが表示されるので、これをクリックするとテストが実行できます。

もし、テスト失敗があると、上記のように赤で×印で教えてくれます。これは結構便利ですね。

木の可視化

単体テストを書いてテストするのは、これはこれで大事なんですが、木（グラフなど）を扱ってると、どうも本当にこれでいいのかピンときません。もちろん、アルゴリズムとして処理の途中の動作も確認して追いかけてはいるのですが、なかなか追いかけるのも大変です。

ということで、せっかく Python で実装していることもあるので、木を可視化する方法として簡単にできるものがないか調べてみると、 Python から Graphviz を利用するための graphviz パッケージがあることがわかりました。ということで、 graphviz パッケージを利用して、木の状態を Graphviz 経由で出力するメソッドを追加してみます。

こうすることで、テスト時の木の変化を視覚的に追いかけることができるようになりますね。

具体的に、 Python から Graphviz を使うには