メソッドも作成しています。メソッドのコードを少し解説します。一度呼び出されるごとにノードを1つ巡り、再帰的に呼び出されることで最後のノードまで巡ります。対して一致した部分と、一致しなかった部分を表します。続いて、現在のノードの情報と、残りの検索文字列を用いて、次のノードへの遷移を行います。再帰的に呼び出します。メソッドを実装していきます。パトリシア木における挿入処理は、分岐のないノードを省略するために、やや複雑な処理を必要とします。パトリシア木の挿入処理は、大きく2パターンに分けられます。1つ目は、挿入の際に既存のノードの変更が必要なもの。2つ目は、既存のノードの変更が必要ないものです。図を用いて説明していきます。「abc」が格納されているパトリシア木に「ab」というノードを追加するものです。この場合は、既存のノードの変更が必要な場合になります。この場合、新たな「ab」のノードは、「a」のノードと「abc」のノードの間に挿入されることになります。「ab」のノードを「a」のノードの下に挿入したとき、「a」のノードの遷移先は「abc」のノードから変更されることになります。変更する必要があります。既存のノードに変更が必要ない場合もあります。パターン2上の図は、先程のパトリシア木に「ba」という単語を追加するものです。この場合、以下の図のように、既存ノードを変更する必要なく挿入することができます。このようにパトリシア木では、単語を挿入する際に、ただノードを追加するだけでなく、既存のノードを変更する必要が生じる場合もあります。コードこれを踏まえて、insert()メソッドのコードを見ていきましょう。それぞれの変数の意味は、コメントに書いてあるとおりです。次に、条件分岐からノードを追加していきます。条件に当てはまる場合は、ノードを追加するだけでなく既存のノードの変更を必要とします。条件に当てはまる場合(rest_strがある場合)は、さらに新しいノードを付け加える必要があります。パトリシア木の実装(検索部分)続いて、検索部分の実装を行っていきます。実装が終わっているので、ここは簡単です。コードこちらがコードとなります。空のとき、つまり、ノードの文字列と検索文字列が完全に一致したときです。パトリシア木の実装(全体)ここまでで、パトリシア木を用いた辞書の実装が終わりました。すべてのコードをまとめたものが以下になります。None最後に、Patriciaクラスを利用して単語の登録、検索を行います。"シー")print(patricia.query("a"))print(patricia.query("abc"))print(patricia.query("bc"))print(patricia.query("abcd"))これを実行すると、以下のような結果になります。なっていることが分かります。終わりにお疲れ様でした!パトリシア木は、トライ木に比べるとやや複雑で理解しにくかったかもしれません。一度理解し使えるようになれば、高速でサイズの小さい使い勝手の良いデータ構造です。トライ木がわかっていればそこまで難しくないと思うので、ぜひチャレンジしてみてください。社長と一杯飲みながらお話してみたい方はこちらミツオカフリーランスエンジニア様の募集はこちらにゃんこ師匠その他、お問い合わせはこちらミツオカお気軽にお問い合わせください!せっかくなので、別の記事もぜひ読んでいって下さいね!一緒に働いてくれる仲間を募集しております!ライトコードでは、仲間を募集しております!当社のモットーは「好きなことを仕事にするエンジニア集団」「エンジニアによるエンジニアのための会社」。エンジニアであるあなたの「やってみたいこと」を全力で応援する会社です。ライトコードは現在、急成長中!だからこそ、あなたにお任せしたいやりがいのあるお仕事は沢山あります。「コアメンバー」として活躍してくれる、あなたからのご応募をお待ちしております!なお、ご応募の前に、「話しだけ聞いてみたい」「社内の雰囲気を知りたい」という方はこちらをご覧ください。「好きなことを仕事にするエンジニア集団」の(株)ライトコードのメディア編集部が書いている記事です。rightcodeエンジニア大募集中!私たちライトコードでは、エンジニアを募集しております。私服大歓迎のカジュアルな職場なので、お気軽にご応募ください!また、フリーエンジニアの方も募集しております。